Four Men and Eight Hats

Problem: There are four men and eight hats (five black hats and three red hats). Each man will wear one hat, but he can't see which hat he is wearing, instead he can only see the hats the other three persons are wearing. Then each man is asked to guess which hat he is wearing (black or red?). The first man said he can't decide. The second man said he also can't decide. The third man, again, said he can't decide. Then it is the turn of the last man, can he or can't he make the right guess?

Solution: The key is to understand what "a man can't decide" exactly means. Let's name the four men, A, B, C, D. When A can't decide, it must be true that B, C, D are NOT all wearing red hats. Since there are only three red ones, if B, C, D are all wearing red hats, A can be sure that he is wearing a black hat. Let's use the same way to analyze B's situation. When B can't decide, it must be true that C, D are NOT both wearing red hats.  Then let's exam C.  When C can't decide, it must be true than D is NOT wearing a red hat. Then based on the all the information, D can be sure he is wearing a black hat.

String Reduction

Problem:  A string that only contains three types of letters :"a", "b", "c". Our goal is to reduce the string. If two different letters are adjacent to each other, we can reduce the two letters into another letter. The rule is like this: if we encounter "ab" (or "ba"), we reduce to "c";   if we encounter "bc" (or "cb"), we reduce to "a";  if we encounter "ca" (or "ac"), we reduce to "b". If two adjacent letters are the same, we can't reduce them. We need to find an optimal way to reduce the string as much as possible.

For example, for string "acbb", if we try to reduce "ac"first, we get "bbb". But, if we reduce "cb" first, we get "aab" and we can further make "aab" => "ac" => "b". The latter approach gives us an optimal reduction.

Solution: Here what really matters is the numbers of letter "a", "b" and "c". Let us name them as num_a, num_b and num_c. If two of them are zero, we can't reduce that string. Otherwise, we can reduce the string into a string that has a length of 1 or 2. If num_a, num_b and num_c are all even or odd,  we can reduce to a string with length 2; If not, we can reduce to a string with length 1.

Then how to do the reduction? The detail is as follow:

1. if the string has a length of 3 and contains one "a", one "b" and one "c", whatever order of the three letter are in, we can only reduce the string into a string with length 2; if the string has a length of 2 and contains two different letters, we can only reduce the string into a string with length 1. Let us regard these two cases as base cases.
2. for a general case, we have num_a "a" , num_b  "b" and num_c  "c". After every reduction, the sum of num_a, num_b and num_c will decrease by 1, since we substitue two letters with one letter.  
3. Then at each round, which two adjacent letters we choose to reduce? We try to find an adjacent pair that contains a letter which has the highest count. For example, if now, we have 3 "a", 4 "b" and 6 "c" in the string, we choose an adjacent pair that contains "c"since num_c = max(num_a, num_b, num_c) . Can we find such pair? definitely we can. If there are multiple such pairs, choose a random one. Then after we reduce this pair, num_c--, max(num_a, num_b, num_c) may decrease by 1, remain unchanged, or increase by 1. However, since max(num_a, num_b, num_c) is up-bounded by num_a + num_b + num_c. num_a + num_b + num_c is decreasing after every round, then max(num_a, num_b, num_c) will also decrease if we look at a long wrong. Therefore, by using our strategy,  max(num_a, num_b, num_c) will eventually decrease to 1, which means we are encounter the base cases in step 1.
4. Then when the string will be reduced to a length of 1 and when to a length of 2? We observe that is num_a, num_b and num_c are all even, then after one transformation, they will become all odd; similarly, if there are originally all odd, after one transformation, they will become all even. Then according to the analysis in step 3), we know at the end, the max(num_a, num_b, num_c) will eventually decrease to 1. But, they should still be all odd at that time (since "1" is odd). Therefore, at the very end, we will have num_a = 1, num_b = 1 and num_c =1, which will  eventually lead to a string of length 2. It is easy to prove that if num_a, num_b and num_c are  not all even or odd, the string will be reduced to length 1.
5. if num_a, num_b and num_c are  not all even or odd, there must be only two cases: a) two of the counters are odd and one is even b) two of the counters are even and one is odd.  For example, if num_b is odd, num_a and num_c are both even. The string actually will eventually be reduced to  "b".
6. if num_a, num_b and num_c are all even or odd, there might be multiple different final forms.

General Monty Hall Problem and Information Theory

Problem: There are three doors and only there is one door behind which there is a prize.You first select a door, then the host of the game will open one door behind which there is no prize (he can't open the door you had selected). Then you are given the choice to switch the door or not. This is the typical Monty Hall problem people talk about. The general form is that n doors with only one door behind which there is a prize. The host of the game will open m doors (m<n-1) behind which there are no prize. Then you are given the choice to switch to another door.

Solution: The most most important observation about this problem is that "probability" is actually not about "randomness", but about information. How much information we have will influence the probability".  Now let's first look at the basic form of the Monty Hall problem.

• assume you chose door A, the probability that you had made the correct choice, P(A),  is 1/3. Assume the host opened the door C (the case for door B is the same), let us denote this action as O. The probability, P(A|O), which means the probability that you had made the correct choice given the host opened the door C, is what we are interested in. Actually P(A|O) = P(A) = 1/3, since unless you move the prize, there is no way you can change the odds of your original choice.
• Besides, we can systematically calculate P(A|O). According to Bayes's theorem, P(A|O) = P(O|A)*P(A)/P(O). We know P(A) = 1/3. P(O|A) should equal 1/2, since if A is the right answer, B and C are both empty doors. The the probability for the host to open door C is simply 1/2. Then we need to calculate P(O). 
• P(O) = P(O|A)*P(A) + P(O|B)*P(B) + P(O|C)*P(C). It is easy to know, P(O|C) = 0, also  P(O|A)*P(A) =1/6. We have P(O|B) = 1. The reason is that we had already chosen A, but B is the right answer, so the only choice for the host is C. Therefore, P(O) = 1/6+1*1/3 = 1/2. Then we have P(A|O) = 1/3.
• Then the probability to win if we switch is P(B|O) = P(O|B)*P(B)/P(O) = 1*1/3 / (1/2) =2/3, so we need to switch!

Now let's try to tackle the general problem.

• The probability to win if we stick to the original choice (assume it is A again), P(A) = 1/n, also we have P(A|O) = 1/n.
•  The probability to win if we switch, P(S|O) = P(We switch to the correct door | Our original choice is wrong) = (1/(n-m-1))*(1-1/n) = ((n-1) / (n-m-1))*1/n). It is easy to know P(S|O)  > P(A|O), so we still need to switch.
• Thinking in the way of information theory, after host reveal some empty doors, we are given more information. These information will change the probability distribution!

See Also: Monty hall and Bayesian probability theory,  The Monty Hall problem -- over easy

Paint a Cube with Three Colors

Problem: Given a cube, each face can be painted with one of the three colors. Calculate the ways the cube can be colored.

Solution: The problem can be solved by enumeration. While a more formal way is to use Burside's Lemma. Generally we need to understand the symmetry of the permutation on cubes. The main ideas of this method are listed as follows:

1. find the permutation groups of a cube, the easiest one is the identity permutation (just don't change). Then for the six faces, we have 1->1, 2->2 ... and 6->6. So for this permutation, there are 6 circles and the length of each circle is 1. Therefore we have a1^6, where a1 means the sub group that with circle length 1. "6" means there are 6 such circles.
2. then we can rotate along the axis that penetrates the centers of two opposite faces for 90 degree. If we do this, we have a1^2*a4, since two face unchanged, and the rest 4 form a circle. We have 6 such rotations. Therefore at the end we have 6*a1^2*a4.
3. then we can rotate along the axis that penetrates the centers of two opposite faces for 180 degree. If we do this, we have a1^2*a2^2.We have 3 such rotations. Therefore at the end we have 3*a1^2*a2^2.
4. then we can rotate the two opposite vertices (diagonal). We will have a3^2, since three faces that share one vertex are in one circle. We have 8 such rotations. Therefore at the end we have 8*a3^2.
5. then we can rotate along the axis that penetrates the middle points of two parallel edges that are not in the same face for 180 degree. We will have 6*a2^3 at the end.
6. so totally we have 1+6+3+8+6 = 24ways of permutations. So the cycle index (the ways to paint the cube) = 1/24*(a1^6+6*a1^2*a4+3*a1^2*a2^2+8*a3^2+6*a2^3). Since a1=a2=...=a6, we have cycle index =  1/24*(a^6+3*a^4+12*a^3+8*a^2). 
7. when a = 3, we have cycle index = 57.

Estimate 3^100

Problem: estimate the value of 3^100.

Solution: A so called "72" rule will be used. The rule states if the percentage of annual GDP increase is a, it takes 72/a years to double the GDP. So 3^100 = 9^50 = 10^50/1.1^50 = 10^50/(1.1*1.1^(7*7)) = 10^50/(1.1*2^7) = 10^50/140 = 1000/140 *10^47 = 7*10^47. Another way is to leverage 3^9 = 20000.

Lights and Switches

Problem: Four lights in a room and four switches outside the room that control the light. You can only enter the room to check if the lights are on. If you are outside, you don't know. How to know the mapping from switches to lights by just entering the room once?

Solution: The key is to find two binary classifier, then we can encode 4 lights. One classifier is On/Off. The other is Cold/Hot. So we can turn on two switches for a while, let the lights become hot. Then turn off one of them. Then turn on one of the the rest two switches.Then rush into the room to check. There must be four different statuses: On and Hot, Off and Hot, On and Cold, Off and Cold.

Shoot the Car

Problem: There is a infinite road. At t0, a car is at coordinate a. It will move towards either left or right (you don't know) at a constant speed b. You don't know the value of a and b. You just know they are integers. You have a gun and at t1, t2, ... tn, ..., you can shoot at any coordinate on the road. Can you find a way to finally shoot the car within finite time?

Solution: Since a and b will be finite, so the search space is finite. Naively, you can try to traverse a matrix M*N. At each tick, you try to shoot at M[i] + t*N[j]. If you fail to shoot the car after traversal, expand the matrix and traverse the part you haven't visited.

While more elegant way is try to order the states you want to search. We can start from (0,0), then (1,0) -> (1,1) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (-1, -1) -> (0, -1) -> (1, -1) -> (2, 0) -> .... Just start from the center and swirl!

A Coin, First Throw Get Head, Bet the Second Thow

Problem: A coin (you don't know it is a fair one or biased one), in the first throw, you got a "head". What will you bet for the second throw and what is the probability to win?

Solution: This is a conditional probability problem. Assume the probability to get head is p. f(p) is a uniform distribution. P(H2/H1) = P(H2H1)/P(H1) = int_{p^2*f(p)*dp} / int_{p*f(p)*dp} = (1/3) / (1/2) = 2/3.

4 Locks on a Treasure Chest

Problem: A round treasure chest has 4 locks. The distance between any adjacent locks are 90 degree. You can't see the status of the locks because they are inside. You can only touch them and set them. Every time, you can chose to touch any two locks and set them. A lock can be set to either 1 or 0. If all the four locks are set as 1 or 0, the chest will open. Once you had set two locks, the round chest will rotate. The rotation distance is random. Is there a way you can guarantee to open the chest?

Solution: The initial status is unknown, but definitely it is not 4 "1" or "0".  Try to think from the last step (under what condition, you can definitely open the box with one more move). We can do as follow:

1. Set two adjacent locks to "0", if still not open, go to step 2.
2. Set two locks that are opposite to each other to "0", if still not open, go to step 3.
3. If you reach here, it means there is one "1" and three "0". Try two adjacent locks, if one is '1" and one is "0", Bingo! Set the "1" to "0". But if you encounter two "0", you need to set one of them to "1". Then there are two cases: a) "1 0 1 0"  and b) "1 1 0 0". Let's go to step 4.
4. if it is a), then we try to set two locks that are opposite to each other to either "0" or "1". We are done! If it is b), we still try to set two locks that are opposite to each other. Basically, we just toggle them (or do nothing). Then step 5.
5. So we still have  "1 1 0 0". This time try to set two adjacent locks, if we encounter two "1" or two "0", we are done. If not, we toggle them. Then we have "1 0 1 0". Then go to step 5.
6. Try to set two locks that are opposite to each other, we got the treasure.

Extension Question: One condition in previous problem is actually redundant. Say you can't feel the lock (you can't tell the status of the lock) and you can just toggle it. Every time you can toggle 1 or 2 locks. Still, we can solve it in 7 steps:

1. Toggle two opposite ones.
2. Toggle two adjacent ones.
3. Toggle two opposite ones.
4. Toggle a random one.
5. Toggle two opposite ones.
6. Toggle two adjacent ones.
7. Toggle two opposite ones.

Generally, if the initial status is unknown, there are two type of cases: 1) two "1" and two "0" 2) three "1" (or "0") and one "0" (or "1"). For the case 1, setp 1~3 can guarantee we finish the game. Step 4 is to handle case 2). After step 4, we are facing case 1), so just repeat the three steps again. 

M balls and N boxes

Problem: There are M balls and N boxes. Each ball is randomly placed into a box. What is the expected number of boxes that have at least one ball inside?

Solution: We can create a series of identification variables, Ii, which denotes for the i th box, if there is at least one ball inside. If yes, Ii = 1, otherwise Ii = 0. Then our problem is to calculate the expected value to I, where I = I1 + I2 + ... + IN. There is symmetric here, so E(I) = N*E(Ii) = N*(1-(N-1/N)^M)

Related: How many boxes you need to have in order to collect all the toys?

How many boxes you need to have in order to collect all the toys?

Problem: Mike likes potato chips and also like the free toys piggybacked with the chips. There are N different toys in total. In each box of potato chips, there will only be one toy and the type of the toy is randomly decided. If Mile wants to collect all the N different toys, how many boxes of chips he needs to buy (on average)?


Solution: We can solve the problem by using Geometric Distribution. After we had collected i-1 toys ( i <=N), the number of  boxes we should get in order to get the i th toy conforms to a geometric distribution. The probability for the geometric distribution is (N-i+1)/N, thus the expected number of boxes to get the i th toy is N/(N-i+1). Then we can construct a random variable X and X = X1 + X2 + ... + XN, where Xi means the number of  boxes we should get in order to get the i th toy when we already have i-1 different toys. So E(X) = E(X1) + E(X2) + ... + E(XN) = N/N + N/N-1 + ...... + N/1 = N*(1/N + 1/(N-1) + ... + 1)

Related: Coupon collector's problem, M balls and N boxes