Differences

This shows you the differences between two versions of the page.

--- pow:problem5s22 [2022/04/12 22:53] – mazur
+++ pow:problem5s22 [2022/04/13 14:30] (current) – mazur
@@ Line 1: / Line 1: @@
+<box 85% round orange| Problem 5 (due on Monday, April 11) >
+A group of 100 friends plans a trip to a remote island to play a new
+exciting game. Upon arrival each of them will be given one of 199 possible
+nick-names to use during the game. Each player will know the nick-name of
+all the other players, but not her own. No communication will be possible
+between the players while they are on the island. However, at the end of the game each player will be
+asked about her nick-name. Only if at least one player answers correctly,
+they all will be allowed to return home.
+Can they prepare a strategy which will guarantee they can return?
+</box>
+We received only one solution: from Leo Kargin (a 9-th grader at
+the Proof school in San Francisco). Leo's solution is based on the same idea as our
+solution, but his execution of the key step is much better than the one in our original
+solution. In fact, after additional simplifications, the strategy is rather easy to formulate:
+Number the nick-names from 1 to 199. Each player knows the 99 numbers representing nick-names of her
+friends. The player computes the sum $s$ of these numbers modulo 100 (so $0\leq s<100$) and sets $k=100-s$.
+Then her guess is the $k$-th smallest of the remaining 100 numbers (nick-names). It turns out that one of the players
+must be right!
+For a justification and more details see the following link {{:pow:2022sproblem5.pdf|Solution}}.