April 2012
This month's challenge is based on a model suggested by Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman, who described the garden-hose model in their paper "The Garden-Hose Game: A New Model of Computation, and Application to Position-Based Quantum Cryptography" ( http://arxiv.org/abs/1109.2563).
X and Y are two 5-bit numbers. Alice knows only X and Bob knows only Y. They have to find whether X and Y are equal.
To do so, they can use eight water pipes that lay between them. Moreover, they each have additional pieces of hose they can use to connect the ends of two water pipes on their side. Any pipe can be connected to at most one hose.
For each input they can use a different connection scheme. In addition, to compute the function, Alice has a source of water she can connect to one of the pipes on her side that is not connected to any hose.
After connecting all the hoses, Alice opens the water tap.
It is easy to see that the water will flow out of one side only. To win the game, the water must come out of Alice's side if and only if X=Y.
We mark the pipes with the first eight letters (A,B,...,H) and the tap with "T". Please supply the answer as 32 lines of comma separated pairs of letters for the connections for each value of the five bits. These two lists of comma-separated pairs (the first for Alice, the second for Bob) should be separated with a colon (":") representing the fence.
Remember, they do *not* know each other's bits; the listing is on the same line for the sake of brevity only.
For example, here is a solution to the same problem with a single bit (so only two lines instead of 32):
TA,CH:AB
TG,EF:DG,EF
Update 4/10: Per your request, here is a solution for two bits
TA BC DE:AF
TB AC ED:BG
TC AB DE:CH
TD AE BC:FD
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:
01/04/2012 @ 10:00 AM EST
Solution:
01/05/2012 @ 10:00 AM EST
List Updated:
01/04/2012 @ 10:00 AM EST
People who answered correctly:
Peter and David de Rivaz (03/31/2012 06:45 AM EDT)
Adrian Orzepowski (03/31/2012 08:22 AM EDT)
William Heller (03/31/2012 01:59 PM EDT)
Radu Alexandru Todor (04/01/2012 09:06 AM EDT)
Øyvind Grotmol (04/01/2012 12:01 PM EDT)
Shilei Zang (04/02/2012 03:40 PM EDT)
Deron Stewart (04/02/2012 06:25 PM EDT)
Joshua Small (04/02/2012 07:45 PM EDT)
Tom Sirgedas (04/03/2012 11:14 PM EDT)
Matthew Atwood (04/04/2012 12:38 AM EDT)
Liubing Yu (04/04/2012 03:10 PM EDT)
James Dow Allen (04/04/2012 07:30 PM EDT)
Mtv Europe (04/05/2012 11:55 AM EDT)
Donald Dodson (04/05/2012 03:04 PM EDT)
Marco Chiesa (04/05/2012 06:13 PM EDT)
Michael Rosola (04/06/2012 10:50 AM EDT)
Matej Kollár (04/06/2012 04:08 PM EDT)
Sergey Grishaev (04/06/2012 07:02 PM EDT)
James Aaronson (04/07/2012 04:14 AM EDT)
Lu Wang (04/07/2012 08:33 AM EDT)
János Csorba (04/07/2012 06:09 PM EDT)
Florian Fischer (04/07/2012 06:37 PM EDT)
John Spurgeon (04/08/2012 05:00 AM EDT)
Motty Porat (04/08/2012 08:15 PM EDT)
John Tromp (04/09/2012 02:08 AM EDT)
Yury X Volvovskiy (04/09/2012 01:04 PM EDT)
Michael S Kester (04/09/2012 03:47 PM EDT)
Brian Tivol (04/09/2012 10:21 PM EDT)
David Friedman (04/09/2012 11:52 PM EDT)
Christian Blatter (04/10/2012 05:07 AM EDT)
Hugues Chabot (04/10/2012 09:55 AM EDT)
Jonathon Noble Pendergrass (04/10/2012 12:52 PM EDT)
Dave Blackston (04/10/2012 04:02 PM EDT)
Martin Thiim (04/10/2012 04:22 PM EDT)
Grégory Strubi (04/11/2012 09:07 AM EDT)
Armin Krauss (04/12/2012 10:11 AM EDT)
Thomas Fleming (04/13/2012 07:52 PM EDT)
George Silvis, III (04/16/2012 03:44 AM EDT)
Andrew D. Kidd (04/16/2012 01:30 PM EDT)
John Jones (04/17/2012 11:39 AM EDT)
Serge Thill (04/19/2012 05:20 AM EDT)
Hannes Schenck (04/20/2012 05:40 AM EDT)
Daniel Bitin (04/23/2012 07:30 AM EDT)
Heiko Selber (04/23/2012 01:38 PM EDT)
Chuck Carroll (04/25/2012 05:56 PM EDT)
Mark Pervovskiy (04/26/2012 06:06 PM EDT)
Sergii Strelchuk (04/26/2012 07:54 PM EDT)
Jamie Jorgensen & Jason Lee (04/27/2012 09:34 PM EDT)
Thomas Pensyl (04/29/2012 02:34 PM EDT)
Ilya Khivrich (04/29/2012 06:54 PM EDT)
Stéphane Higueret (05/01/2012 03:33 AM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.