July 2015
Four people stand in line with hats on their heads. On the back of each hat is a unique number (i.e., no two people have the same number) between 1 and 6. Each person can see only the numbers of the people in front of him. One by one, starting from the back of the line, they need to guess the number on their own head, but they are not allowed to use any number that was previously guessed. Since they guess out loud, all the people in line hear each other's guesses. Clearly, the last person in line (who is the first to guess) cannot guarantee being correct. Our challenge this month is to show that all the rest can.
Your challenge is to provide the strategy of the last person (the first to guess) in guessing a number between 1 and 6, as a function of the other three numbers he sees. Please provide your answer as a list of 216 digits: 1-6 for a guess, and 0 for the illegal cases (when not all the three numbers are different as they should be).
For example, here is a solution for the trivial case when the numbers are only in 1-4 range:
0000 0043 0402 0320
0043 0000 4001 3010
0402 4001 0000 2100
0320 3010 2100 0000
In this case, the last person actually knows his number as the one missing from the rest. For example, the first zero represents the illegal case when he sees "1, 1, 1"; the first nonzero number (4) corresponds to the case when he sees "1, 2, 3" in front of him; the next number (3) is used when he sees "1, 2, 4", etc. As a side note just to better explain the game, the second guesser sees two hats in front of her, and hears the guess of the person behind her and can therefore deduce her number; etc.
As we said before - we are only looking for the strategy used by the last person in line.
Update (9/7, thanks James):
- The last person (first to guess) is helping the other players to win, and that they have agreed on a strategy in advance.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
02/07/2015 @ 12:00 PM EST
Solution:
01/08/2015 @ 12:00 PM EST
List Updated:
02/08/2015 @ 12:00 PM EST
People who answered correctly:
Robert Gerbicz (02/07/2015 07:54 PM IDT)
Lei Fu (02/07/2015 10:18 PM IDT)
Yanwu He (02/07/2015 10:42 PM IDT)
Jesse Rearick (03/07/2015 01:32 AM IDT)
Radu-Alexandru Todor (03/07/2015 02:52 AM IDT)
Joseph DeVincentis (03/07/2015 04:05 AM IDT)
Paolo Farinelli (03/07/2015 06:13 AM IDT)
Minxi Jiang (03/07/2015 11:06 AM IDT)
Graham Hemsley (03/07/2015 01:10 PM IDT)
Lischka Marc (03/07/2015 05:29 PM IDT)
Todd Will (03/07/2015 05:42 PM IDT)
Uoti Urpala (04/07/2015 02:40 AM IDT)
Sean Egan (04/07/2015 08:15 AM IDT)
José Eduardo Gaboardi de Carvalho (04/07/2015 04:33 AM IDT)
Vladimir Sedach (04/07/2015 07:03 PM IDT)
Lorenz Reichel (04/07/2015 07:41 PM IDT)
Motty Porat (05/07/2015 02:07 AM IDT)
Michael Rosola (05/07/2015 02:14 AM IDT)
Dieter Beckerle (05/07/2015 10:42 AM IDT)
Jean-Baptiste Rouquier (05/07/2015 12:26 PM IDT)
Di Luo (05/07/2015 05:41 PM IDT)
Andreas Stiller (05/07/2015 06:13 PM IDT)
Alex Wagner (05/07/2015 10:10 PM IDT)
Ben Phillabaum (06/07/2015 12:31 AM IDT)
Don Dodson (06/07/2015 06:51 AM IDT)
Bryce Herdt (06/07/2015 05:47 PM IDT)
Chuck Carroll (07/07/2015 04:41 AM IDT)
Zhizhong Zhou (07/07/2015 06:18 AM IDT)
James Dow Allen (07/07/2015 09:40 AM IDT)
Peter Gerritson (07/07/2015 06:20 PM IDT)
William Heller (07/07/2015 11:58 PM IDT)
Chris Shannon (08/07/2015 01:10 AM IDT)
Marcus Reble (08/07/2015 02:29 AM IDT)
Caili Shen (08/07/2015 06:00 AM IDT)
Yury Volvovskiy (08/07/2015 01:04 PM IDT)
Ariel Landau (08/07/2015 03:20 PM IDT)
Li Li (09/07/2015 02:00 AM IDT)
Nyles Heise (09/07/2015 06:34 AM IDT)
Erik Hostens (09/07/2015 02:51 PM IDT)
Nagendra Gd (10/07/2015 09:44 AM IDT)
Reiner Martin (11/07/2015 12:05 AM IDT)
Aharon Malachi (11/07/2015 08:53 PM IDT)
Alex Fleischer (12/07/2015 12:36 AM IDT)
Peter Isza (12/07/2015 12:17 PM IDT)
Harald Bögeholz (12/07/2015 09:34 PM IDT)
Janos Csorba (12/07/2015 09:51 PM IDT)
Francis Golding (13/07/2015 03:03 PM IDT)
Lucas Mirelmann (14/07/2015 01:44 AM IDT)
Gary M. Gerken (14/07/2015 06:36 AM IDT)
David Friedman (14/07/2015 06:28 PM IDT)
David Greer (14/07/2015 06:50 PM IDT)
John Tromp (15/07/2015 04:43 AM IDT)
Greg Janée (15/07/2015 09:09 AM IDT)
Jacob Speer (16/07/2015 06:15 AM IDT)
Chi-Man Liu (16/07/2015 12:11 PM IDT)
Dmitry Serbin (16/07/2015 06:10 PM IDT)
Lv Jianhao (18/07/2015 06:58 PM IDT)
Mark Pervovskiy (19/07/2015 12:06 AM IDT)
Shirish Chinchalkar (19/07/2015 02:24 AM IDT)
Daniel Bitin (19/07/2015 02:45 PM IDT)
Geza Bohus (19/07/2015 07:11 PM IDT)
Bart De Vylder (20/07/2015 12:57 AM IDT)
Mathias Schenker (20/07/2015 07:53 AM IDT)
Kang Jin Cho (20/07/2015 09:20 AM IDT)
András Agócs (20/07/2015 08:22 PM IDT)
Akos Groller (20/07/2015 08:08 PM IDT)
Ferenc Wettl (23/07/2015 11:08 AM IDT)
Hao Wu (24/07/2015 07:43 AM IDT)
Armin Krauss (24/07/2015 09:04 PM IDT)
Gyorgy Gyomai (25/07/2015 02:05 PM IDT)
Varun Ahluwalia & Anwesha Tapadar (27/07/2015 05:19 AM IDT)
Kim Georg Lind Pedersen (27/07/2015 06:09 PM IDT)
Bradley Sherman & Mason Bouffard (29/07/2015 01:06 AM IDT)
Katie Lo (29/07/2015 06:54 PM IDT)
Anna Rudas (29/07/2015 10:50 PM IDT)
David Dunkley (30/07/2015 11:23 PM IDT)
Jitesh Gandhi (31/07/2015 02:34 AM IDT)
Liubing Yu (01/08/2015 12:45 AM IDT)
Gregory Giecold (01/08/2015 05:41 AM IDT)