Categories

Problem on Probability from SMO, 2012 | Problem 33

Try this beautiful problem from Singapore Mathematics Olympiad, SMO, 2012 based on Probability.

Problem – Probability (SMO Entrance)

Two players A and B play rock – paper – scissors continuously until player A wins 2 consecutive games. Suppose each player is equally likely to use each hand – sign in every game . What is the expected number of games they will play?

• 12
• 15
• 16
• 20

Key Concepts

Probability

Permutation Combination

Challenges and Thrills – Pre – College Mathematics

Try with Hints

We can start with a general case :

Two players are playing a series of games of Rock – Paper – scissors. There are a total of K games played. Player 1 has a sequence of moves denoted by string A and similarly player 2 has string B. If any player reaches the end of their string, they move back to the start of the string. The task is to count the number of games won by each of the player when exactly K games are being played.

To start with this particular problem let’s set an expectation as k.

If A doesnot win , so the probability will be = $\frac {no of event}{total event} = \frac {2}{3}$

so game will be restarted.

Try to find out the rest of the cases…………..

Continue from the 1st hint :

Again case 2: If A wins at first and then losses so again the probability will be $\frac {1}{3} \times \frac {2}{3}$. again new game will start.

Last case : A wins in consecutive two games the probability will be $\frac {1}{3} \times \frac{1}{3}$

Do the rest of the sum……..

The total number of games that they will play :

K = $\frac {2}{3} \times (K+1) \times \frac {2}{9} (K+2) \times \frac {1}{9} \times 2$

Now solve this equation and at the end E will be 12. [Check it yourself]

Categories

Let’s Permute | ISI MStat 2018 PSB Problem 3

This problem is an easy application of the basic algorithmic ideas to approach a combinatorics problem using permutation and combination and basic counting principles. Enjoy this problem 3 from ISI MStat 2018 PSB.

Problem

Consider all permutations of the integers $1,2, \ldots, 100$ . In how many
of these permutations will the $25^{th}$ number be the minimum of the
first 25 numbers and the $50^{th}$ number be the minimum of the first 50
numbers?

Solution

Whenever you are counting, think in terms of algorithms or steps in which you will do the task given in the problem and count each of the steps. Now the conjunction in between the steps ( and $\cap$ , or $\cup$ ) will show you the way.

Steps

Select the first 50 numbers. Fix the minimum element. Out of the 49 other elements, select the first 25 numbers. Fix the minimum element of these 25 numbers. Then permute the rest.

AND for each of these selections of two sets (Multiplication Principle),

Step 2

Once you select the three sets, the minimum of each of these sets is already fixed. So, for each of these sets, you have to permute the other first 24 numbers (1 – 24) and the next 24 numbers (from 26 – 49) and the other 50 numbers (50 – 100).

You can do that in $24! \times 24! \times 50!$ ways.

Therefore, you can do the whole task in ${100 \choose 50} \times { 49 \choose 25 } \times 24! \times 24! \times 50!$ ways.

Food for Thought

• Do the problem for $2n$ numbers.
• Do the problem if you want to fix the minimum $k$ numbers in each set out of $2n$ numbers.
• Do the problem if you want to fix the minimum $n$ numbers in each set out of $2n$ numbers. Does it match your expectation?
• Generalize and Degeneralize and make your own problem out of this. Comment it below. We will update it here if we think the problem is appropriate.
Categories

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

• 288
• 155
• 160
• 201

Key Concepts

Permutations & Combinations

Sudoku

Set Theory

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.