Categories
Singapore Math Olympiad

Problem on Permutation | SMO, 2011 | Problem No. 24

Try this beautiful problem from Singapore Mathematics Olympiad, SMO, 2011 based on Permutation.

Permutation Problem (SMO Entrance)


A \(4 \times 4\) Sudoku grid is filled with digits so that each column , each row and each of the four \( 2 \times 2\) sub grids that composes the grid contains all of the digits from 1 to 4. For example

Sudoku - Permutation Problem
  • 288
  • 155
  • 160
  • 201

Key Concepts


Permutations & Combinations

Sudoku

Set Theory

Check the Answer


Answer: 288

Singapore Mathematical Olympiad

Challenges and Thrills – Pre – College Mathematics

Try with Hints


If you really get stuck in this problem here is the first hint to do that:

At 1st let’s consider the sub grids of \( 2 \times 2\) filled with 1-4 ( 1, 2 , 3 ,4)

If a,b,c,d are all distinct , and there are no other numbers to place in x . If {a,b} = {c,d} then again a’,b’,c,d are all distinct , and no other number can be possible for x’.

We need to understand that the choices we have ,

{a,a’} = {1,2} , {b,b’} = {3,4}, {c,c’} = {2,4} and {d,d’} = {1,3}

Among these choices \( 2^4 = 16 \) choices 4 of them are impossible – {a,b} = {c,d} = {1,4} or {2,3} and

{a,b} = {1,4} and {c,d} = {2,3} and {a,b} = {2,3} and {c,d} = {1,4}

Try rest….

Now for each remaining case a’,b’,c’ and d’ are uniquely determined so

{x} = {1,2,3,4} – {a,b} \(\cup\) {c,d}

{y} = {1,2,3,4} – {a,b} \(\cup\) {c’,d’}

{x’} = {1,2,3,4} – {a’,b’} \(\cup\) {c,d}

{y’} = {1,2,3,4} – {a’,b’} \(\cup\) {c’,d’}

In final hint :

There are 4! = 24 permutation in the left top grid we can find. So total 12 * 24 = 288 possible 4\(\times\) 4 Sudoku grids can be found.

Subscribe to Cheenta at Youtube


Categories
IIT JAM Statistics ISI M.Stat PSB Probability

Venny Venny AMy GMy | ISI MStat 2016 PSB Problem 3

This problem is a very basic and cute application of set theory, Venn diagram and AM GM inequality to solve the ISI MStat 2016 PSB Problem 3.

Problem – Venn diagram and AM GM inequality

For any two events \(A\) and \(B\), show that
$$
(\mathrm{P}(A \cap B))^{2}+\left(\mathrm{P}\left(A \cap B^{c}\right)\right)^{2}+\left(\mathrm{P}\left(A^{c} \cap B\right)\right)^{2}+\left(\mathrm{P}\left(A^{c} \cap B^{c}\right)\right)^{2} \geq \frac{1}{4}
$$

Prerequisites

Solution

Draw the Venn Diagram

venn diagram and am gm inequality problem

P(region Red) = \(Y\)

P(region Blue) = \(Z\)

P(region Grey) = \(W\)

P(region Brown) = \(X\)

Observe that \( W + X + Y + Z = 1\). \( W, X, Y, Z \geq 0\).

Now, Calculate Given Probability of Sets in terms of \( W, X, Y, Z \).

\({P}(A \cap B) = Z\).

\({P}\left(A \cap B^{c}\right) = Y\).

\({P}\left(A^{c} \cap B\right) = W\).

\( {P}\left(A^{c} \cap B^{c}\right) = X\).

The Final Inequality

\( W, X, Y, Z \geq 0\).

\( W + X + Y + Z = 1\).

Observe that \( 3(W^2 + X^2 + Y^2 + Z^2) = (W^2+X^2) + (W^2+Y^2) + (W^2+Z^2) + (X^2+Y^2) + (X^2+Z^2) + (Y^2+Z^2)\).

\( 3(W^2 + X^2 + Y^2 + Z^2) \geq 2WX + 2WY + 2WZ + 2XY + 2XZ + 2YZ \) by AM – GM Inequality.

\( \Rightarrow 4(W^2 + X^2 + Y^2 + Z^2) \geq (W + X + Y + Z)^2 = 1\).

\( \Rightarrow (W^2 + X^2 + Y^2 + Z^2) \geq \frac{1}{4} \).

Hence,

$$
(\mathrm{P}(A \cap B))^{2}+\left(\mathrm{P}\left(A \cap B^{c}\right)\right)^{2}+\left(\mathrm{P}\left(A^{c} \cap B\right)\right)^{2}+\left(\mathrm{P}\left(A^{c} \cap B^{c}\right)\right)^{2} \geq \frac{1}{4}
$$