|
UPDATE (13 April):
In answer to a repeating question by several readers: both Alice and Bob
know in advance the value of N.
This month marks Claude Shannon's centenary. Shannon was born April 30th, 1916. To celebrate the event, this month's riddle is about information. The riddle comes from Rani Hod (Thanks, Rani!), and is a variation over a problem originally posed by Madhu Sudan. Alice has two distinct numbers between 1 and N. Bob has one of these numbers. The two can communicate in any protocol they choose. Communication between them is bi-directional. How many bits must the two exchange for Bob to be able to communicate to Alice which of her two numbers he has? Note that we are only concerned with the worst-case number of bits. In particular, nothing can be gained by using a stochastic protocol, so the protocol can be assumed to be deterministic. To be considered a solver, your answer must be exact up to O(1) bits. As usual, all answers must be accompanied by proofs. |
List of solvers:Yuping Luo (2 April 22:49)Uoti Urpala (3 April 07:30) Alexander Ruff (4 April 10:00) Thomas Hendrey and Kevin Hendrey (6 April 19:22) Nikhil Mande (10 April 23:36) Lin Jin (12 April 19:26) Yu Gao (29 April 20:04) Nis Jørgensen (30 April 05:03) |
Elegant and original solutions can be submitted to the puzzlemaster at riddles
brand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!