The Monty Hall puzzle

In a game show there are three doors. Behind two doors is a goat and behind the other door is a car. As a contestant, you want to win the car. Now, the hosts asks you to choose a door. Then the host goes ahead and opens one of the other two doors  which has a goat behind it. Now, he gives you an option to switch your choice. Should you switch?

It is important to mention that the host:  1) never opens the chosen door 2) always opens the door which has a goat behind it. 

Initially we have no information about the winning door. All the doors have equal 1/3 probability of being the winning door. Once, the host opens a door which has a goat behind we get more information. The inference we can draw based on the nature of the host is that the door which was left unopened is likely to have the car behind it, otherwise the host could have chosen that door instead. It is more clear from an extension of this question, where say there are 1000 doors with 999 having goat behind them. The host this time opens all except the chosen and one other door. Think, why would the host leave just this one door from the 999 possible doors. There are two possibilities 1) You chose the right door initially but chances of that are rather low .001, considering your choice is uniform random initially.  In this case the host could have chosen any door and switching will make you lose. 2) You chose the wrong door initially, the chances of which are 0 .999. In this case host has no choice but to leave the door with car behind untouched, In this case, switching will make you win. So, notice that if you do 1000 random runs, then in expectation 999 times you will make the wrong choice initially and switching will make you win, 999/1000 times. On the other hand, 1/1000 switching will make you lose. For three doors, it is the same argument for 3 doors: switching will make you win 2/3 times. 

We can make this analysis more rigorous, by defining some random variables. Let 1,2,3 denote the door numbers. Following are random variables for this process: Your initial choice (YC), host's choice (HC) and the door with car behind it (DC). Note, YC, HC and DC \in {1,2,3). Let's say that the car is deterministically behind door 1 i.e.

P(DC=1) = 1

 Considering the initial choice of player to be uniform random 

P(YC=1) = P(YC=2)=P(YC=3)= 1/3

As host's choice depends on player's choice HC is not independent of YC.  If you choose door 1 i.e. the winning door, host can choose any of  the other two doors with equal probability.

P(HC=2|YC=1) = P(HC=3|YC=1) = 1/2

Based on nature of the host we know:
1) The host will never choose the door with the car behind it:

P(HC=1|YC=*) = 0

2) The host will never choose the door that you have chosen:

                                                                  P(HC=x|YC=x) = 0

If you choose the wrong door, the host has no choice

P(HC=3|YC=2) = 1 and P(HC=2|YC=3) = 1

Let's calcualte, P(YC=DC|HC) which is the probability of your initial choice being the winner given the hosts choice. For our simplified case we have assumed DC=1 deterministically, hence we need to compute P(YC=1|HC). As these are not independent, P(YC=1|HC) \neq P(YC=1) staraight away. But by bayes rule, 

P(YC=1|HC) = P(HC|YC=1)P(YC=1)/(P(HC|YC=1)P(YC=1)+...+P(HC|YC=3)P(YC=3))

From previous computation of conditionals, P(YC=1|HC=1)  = 0.  

                                               P(YC=1|HC=2) = 1/2*1/3/(1/3*(1+1/2))  = 1/3 

This is the probability of winning without switching. You will win on switching if your initial choice was wrong i.e. P(YC\neqDC|HC) = P(YC=2|HC)+P(YC=3|HC). For HC = 2, this is just

                                               P(YC=3|HC=2) = 1*1/3/(1/3*3/2) = 2/3

For HC = 3,

                                              P(YC=2|HC=3) = 1*1/3/(1/3*3/2) = 2/3

Puzzle #6: Probability of centre of square inside circle

Select two points uniformly randomly inside a square. What is the probability that the center of the square will lie inside the circle drawn with these two points as ends of diameter?

Source: Rishab Vaid

Puzzle #5: Save the king

Problem: There are 500 barrels of wine and exactly one of them is poisoned. The king wants to identify the poisoned barrel but he is ready to sacrifice only 4 prisoners. They have 4 days to find the poisoned barrel. The poison has the property that after consuming it one can die anytime in the next 24hrs. Give the strategy to find the poisoned barrel.

Source: Shahbaz  also CSE blog

Puzzle #4: Stop the roll

Problem: You are in a dicey situation. You friend gave you a dice and asked you to keep rolling till you get a sum of 100 or more. Now,you have to tell the most probable number at which you are going to stop.

Solution: You will stop at or before 105. Now, trick is to think backwards. You can get 105, only if you ever reach 99. Similarly, you can get 104, only from 99 or 98. You can get to 100, from maximum previous sums i.e. 94, 95, 96, 97, 98 and 99. Therefore, 100 is the most probable stopping point.  P(105) = P(105|99).P(99) = P(99)/6 . Similiarly, P(104) = (P(99)+P(98))/6, ...P(100)  = (P(94)+...+P(99))/6

Source: Rishab

Maths puzzle #3- XOR magic

Problem: You are given a set of n numbers, C = { c_1, c_2, ..., c_n}and you have to find the minimum size of subset of C from which you can create the given n numbers by only doing xor operations on the elements of the subset.

Solution: One starts by thinking about the properties of XOR. There are only a few properties that I know, like x + y + x = y ( I'll represent XOR by + through out the post). So, I have to find a subset V = { v_1, v_2,...,v_k} such that a_i1*v_1+a_i2*v_2+...+a_ik*v_k = c_i, for all elements of C and a_ij are either 0 or 1. This looks similat to c_i being linear combination of V. So, we check if there is a vector space with XOR as the addition operation and voilà, if a euclidean vector space is over the field Z_2, then addition operation is x+y % 2 which is the definition of XOR. So, now all we need to find is the rank of matrix [c_1 c_2 ...c_n] . To find the rank reduced matrix by elementary operations (gauss elimination)

Source: Rishab Vaid  who read it perhaps on Topcoder

Maths puzzle #2 - Divisibility by 100

Given any 51 integers, prove that there exist two integers a, b such that a^2 - b^2  is divisible by 100

Solution: Start thinking by why only 51? If we divide any number by 50 it will give 50 possible remainders, which means there are two integers a, b which give the same remainder. So, a = 50q1+r and b = 50q2+r where 0<= r < 50.

a^2 - b^2 = (a-b)*(a+b) = 50(q1-q2) * 2(25(q1+q2)+r), hence divisibility by 100

Source: Manish asked me this problem, who was in turn asked by Rustam, who read it in Mathematical circles: the russian experience

Maths Puzzle #1

Source: CSE blog

Question: A random permutation of integers from 1 to N is arranged in a circle. Prove that there exist k consecutive integer with sum >= k(n+1)/2

Observation: In several puzzles where a comment has to be made about the sum, it is worthwhile to look at the average. Here we ask the question what is the average of each group of k-integers? We know the sum of 1 to n is  n(n+1)/2. But in our case every number is part of multiple groups, for ex: number at kth position from start is part of group number 1,2,....k. So every number appears k times, making total sum of all the k-integer groups to be k*n*(n+1)/2. As there are total of n such groups (again count!), average sum of these n groups is k*(n+1)/2, implying there exist a group with value greater than equal to k*(n+1)/2

A stronger statement can also be made if n/k is an integer. There are (n/k) disjoint groups of size at least k. These (n/k) groups can be identified by mentioning the start position. Example, if we start at element 1, the n/k groups will start from 1, k+1, 2k+1,... ((n/k)-1)*k+1. Total sum of these (n/k) groups is n(n+1)/2, thus average sum of each group is n(n+1)/(2*(n/k)) = k(n+1)/2, thus there is at least one group among these n/k groups with sum >= n(k+1)/2

If instead of starting at 1, we start at two, we will get a entirely different set of n/k groups of size k each. In this way we can continue till the start point is k. Thus there will be k different groups of size k each such that there is sum is >=k(n+1)/2

Average trick works in several other puzzles as well. Kaizad rustomji gave me some of those which I'll post later.