# Brain teasers

1. Make an unfair coin fair.
Solution: Flip it twice and consider the order of the tuple as the new 'coin flip'. If both are heads or tails, reject and repeat.

2. 100 doors.
Solution: Only perfect squares will be open because they will have an odd parity for the number of factors.

3. Josephus problem for 100 people.
Solution: Note that if number of people is $2^x$, then first person will survive. Therefore for 100 people, the nearest power of two is 64. Therefore, after 36 people die in the first round, i.e. 72 people left. The 73rd person can be thought of as the first person in a game of 64 and he will survive.

4. 4 chairs in a circle. Start anywhere. Roll fair dice. If 4 shows up, move counter clockwise. Otherwise, move $n$ steps clockwise where $n$ is the dice roll. What is the probability of returning to your starting seat after some $N$ dice rolls?
Solution: The problem is a Markov chain where each state is symmetric. Therefore the limiting distribution is a vector of 1/4, which is a good approximation if $N$ is large.

5. You are given two eggs and you need to find from which building-floor (assuming 50 storeys high) will they break.
Solution: Dynamic programming actually. For 100 floors, you need 14 tries. Guaranteed.

6. End combinations of a tic-tac-toe game.
Solution: Consider instead the number of moves for the game to end. If it is 9 moves (i.e. a draw), then there is 9! combinations. Repeat this for 8, 7, 6, and 5. Then we take care of symmetries, i.e. rotation and reflections, which is a factor of 8.

7. $P(x>0|x+y>0)$ if $x,y \sim \mathcal{N}(0,1)$.
Solution: (https://math.stackexchange.com/questions/3439609/what-is-px-0-mid-x-y-0-given-that-x-y-are-i-i-d-standard-normal)

8. You are at the center of a circle island, trying to reach the edge without being eaten by a shark in the water
Solution: https://www.puzzleprime.com/puzzles/brain-teasers/mathematics/shark-attack/

9. The price of a stock starts at 100 dollars, then drops 1%, then grows 1%, then drops 1% again and so on. What does the price converge to?
Solution: Geometric series with ratio of $0.99 \times 1.01$ which is less than one, therefore over time it converges to zero.

10. king's wine cellar (where you have 10 prisoners and 1000 bottles of wine, and one is poisoned wine)
Solution: label prisoners one to ten and label wine in binary. If there is one in the position of the prisoner's label, prisoner drinks. From the dead prisoners we infer the label of the bottle and convert back to decimal.

11. Max of IID variables
Solution: https://math.stackexchange.com/questions/150586/expected-value-of-max-of-iid-variables

12. You have the option to throw a die up to three times. You will earn the face value of the die. You have the option to stop after each throw and walk away with the money earned. The earnings are not additive. What is the expected payoff of this game?
Solution: Optimal strategy is to re-roll until you hit above the expected value of that stage. Have to grind those numbers. After first re-roll, expectation is 4.25. After second re-roll, expectation is 4.666 therefore that's the answer. Not really sure how the optimality is obvious.