pow:problem3f25 [Department of Mathematics and Statistics, Binghamton University]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

<box 85% round orange|  Problem 3 (due Monday, October 6 )>

24 friends regularly attend parties organized by a puzzle-loving host.
The host challenges the group to the following game. The host has 24 name tags
with the names of the 24 friends and she randomly distributes one name tag to each
of the friends.  The goal of the game is for each of the friends to find out who
has their name tag. Each of the 24 players is allowed to ask the host in private (so no one else can hear it) about the name tags of up to 11 friends. No other
communication about the name tags is allowed. If each of the 24 friends correctly identifies
the person holding their name tag, the host provides a ride home for each of them.
Otherwise they all need to arrange for their ride home. Design as good a strategy as you can for the friends to maximize the likelihood to receive a free ride home. 


</box>
We have not received any solutions, except some useful comments from Matt Wolak, who knew a slightly different
version of this problem. There is a strategy which guarantees free ride home with probability slightly exceeding 2/5.  We do not know if a better strategy exists. For a detailed solution see the following link {{:pow:2025fproblem3.pdf|Solution}}.