Ponder This Challenge - April 2012 - Garden hose model

Ponder This Challenge:

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

Solution

• Click here to view the solution

  This month, we received many similar answers to the challenge, but Brian Tivol's solution was written in such a lovely way that we couldn't resist posting it here verbatim, ending with our comments as an epilog.

  Alice tells Bob: "Can we play this game on four pipes to communicate a number between 0 and 5?"

  Bob tells Alice: "Well, I have six ways to add a single hose to four pipes. I'll list the six possible ways in alphabetical order, and when I get a number I'll attach a single hose corresponding to that spot on the list."

  Alice tells Bob: "OK. When I get a number, I'll say 'Which two pipes would Bob use if he had my number?' I'll name one of those 'in' and one 'out'. I'll connect a hose to my two unnamed pipes. I'll connect the tap to 'in'."

  Bob tells Alice: "That works!"

  Alice tells Bob: "OK, so now let's use eight pipes to communicate a number between 0 and 35. We'll treat it as a base six number, and use ABCD for the low digit and EFGH for the high digit."

  Bob tells Alice: "I can add one hose per digit, as before. But you don't have one tap per digit!"

  Alice tells Bob: "For each digit, I'll label and connect the pipes, as before. I'll connect the tap to my low digit's 'in', and I'll connect my low digit's 'out' to my high digit's 'in'."

  Bob tells Alice: "That works, too!"

  Ponder-This epilog:

  Cascading the 6-possibilities/4-pipe solution gives us 4 pipes for each log_2 6 bits, which is p=~1.547n.

  We can use a similar construction which gives 15 possibilities for 6 pipes, thus yielding p=~1.536n.

  There is also an uncascadable solution for 10 possibilities with 5 pipes, which is p=~1.505n

  Donald Dodson sent us a correct solution for 45 possibilities with 8 pipes, which gives p=~1.457n.

  And we have found a solution for 46 possibilities with 8 pipes, which gives p=~1.448n.

  The minimal number of pipes p for n bits is still an open problem.

Solvers

• 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)