Benoît Zhou

Puzzles

---

• You draw cards one by one without replacement from a deck of 52 cards (26 red and 26 black). You receive a dollar for a red card and lose a dollar for a black card. You can stop at any time. What is your strategy, and what is the expected payoff?
  
  Dynamic Programming
  
  
• What is the average number of cards you must draw without replacement before getting an ace?
  
  \(48/5\)
  
  
• There is coin on each vertex of a regular polygon. You flip each coin, and rotate it clockwise if you get a heads, counterclockwise if you get a tails. What is the probability that two coins overlap?
  
  \(1 - 1/2^{n-1} - \mathbb{I}_{2\mathbb{N}}(n) / 2^{n-1}\)
  
  
• Independent flips of a biased coin are made.
  1. What is the probability that the pattern THH occurs before HHH?
  2. What is the probability that the pattern HTH occurs before THH?
  3. What is the probability that the pattern HHH occurs before HTH?
  
  
  1. \((1+p+p^2)q\)
  2. \((1-pq) / (2-p)\)
  3. \(p / (1+pq)\)
  
  
• You have one gold coin and one silver coin. A gold heads gives you $3 and a silver heads gives you $1. You flip both coins 500 times each and receive $1100. Bound the most likely number of heads you got.
  
  Between 537 and 550
  
  
• You construct a sequence of polygons where the \((n+1)\)th polygon is obtained by setting its vertices as the centers of the sides of the \(n\)th polygon. Show that the speed of convergence is exponential.
  
  Matrix-vector description and eigenanalysis
  
  
• Given \(n\) independent points drawn uniformly at random on the circumference of a circle, what is the probability that they all lie within the same semicircle?
  
  \(n / 2^{n-1}\)
  
  
• 1. What is the average distance (length of the chord) between two independent points drawn uniformly at random on the circumference of a circle?
  2. How about the average distance between two points in a disk?
  3. And in a square?
  
  
  1. \(\frac{4}{\pi}R\)
  2. \(\frac{128}{45\pi}R\)
  3. \(\frac{2 + \sqrt 2 + 5 \ln(1 + \sqrt 2)}{15}R\)
  
  
• Given 4 independent points drawn uniformly at random in a circle, what is the probability that they form a four-sided convex quadrilateral.
  
  \(1 - \frac{35}{12 \pi^2}\)
  
  
• What is the probability that the sum of \(n\) independent random variables following a uniform distribution on [0, 1] is less than 1?
  
  \(1 / n!\)
  
  
• \(2n\) people numbered from \(1\) to \(2n\) play a cooperative game.
  A room has \(2n\) identical drawers, with one unique player's number in each closed drawer. The players enter the room, one after another. Each player may open and look into \(n\) drawers in any order. The drawers are all closed again afterwards. The players win if they all find their numbers in one of the drawers. In other words, if just one player does not find his number, they all lose. The players may discuss strategy before the first player enters the room, but may not communicate once the first player enters to look in the drawers. What is the best strategy?
  
  The survival probability is \(1 - (H_{2n} - H_n) \), which goes to \(1 - \ln2\) (think of the Euler–Mascheroni constant)
  
  
• \(2^n-1\) players play a cooperative game.
  Each player is put on a hat that is either black or red, the color being independently chosen uniformly at random. The players can see other players' hats, but not their own. They must all guess in the same time the color of their hat or pass. In order to win, at least one player must guess correctly and none must guess incorrectly (passing is neither correct nor incorrect). The players may discuss strategy before the hats are put on, but may not communicate after.
  1. What is the best strategy, and what is the probability of winning?
  2. What if there is a host that adversarially chooses the color of the hats?
  
  \( 1 - 1/2^n \)
  
  
• \(n\) people play a cooperative game.
  They sit around a table and are each put on a hat that can be any color chosen amongst \(n\) colors. Note that several hats can be the same color. The players can see other players' hats, but not their own. They must all guess in the same time the color of their hat. In order to win, at least one player must guess correctly. The players may discuss strategy before the hats are put on, but may not communicate after. What strategy garantees success?
  
  
• \(n\) ants are dropped on a stick. Each ant is going either left or right with constant velocity. When two ants meet, they bounce off each other and reverse direction. When an ant reaches an end of the stick, it falls off.
  1. What is the shortest amount of time you must wait to be certain that there are no more ants on the stick?
  2. What is the average time it takes for all the ants to fall off the stick?
  
  
  1. \(\frac{L}{v}\)
  2. \(\frac{n}{n+1}\frac{L}{v}\)
  
  
• In a line up of \(n\) students, what is the least number of students that can be picked in order of either increasing or decreasing heights? Assume that all students have different heights. Students can be picked from anywhere in the line, but their order of standing cannot be changed.
  
  \(\left\lceil \sqrt n \right\rceil\) (use the Erdős–Szekeres theorem)
  
  
• Is there a strategy for \(n\) people to compute their average age without disclosing their own age to others?
  
  Add randomness
  
  
• Can you fit 53 cuboids of dimension \(4\times1\times1\) in a \(6\times6\times6\) cube?
  
  No
  
  
• What is the \(100^\text{th}\) digit of \((1+\sqrt 2)^{3000}\)?
  
  9
  
  

Back to topShow/hide solutions