Credited with solving this puzzle, this was a fun one:
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
