April 2012
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.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com