 |
Problem of the Week
BUGCAT
Zassenhaus Conference
Hilton Memorial Lecture
BingAWM
Math Club
Actuarial Association
Sidebar
pow:problem5s22
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?
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 Solution.
pow/problem5s22.txt · Last modified: 2022/04/13 10:30 by mazur