Andrei and Belle have been set a task by their “friend”, Carroll. Carroll has promised them money depending on how well they do.
Carroll will give a 99 bit array to Andrei and a different one to Belle. They don’t see each other’s arrays. Andrei gets to send one message (made up of bits) to Belle and Belle then has to say whether she has no bits the same as Andrei’s in common positions or alternatively if exactly 99/3=33 of the bits in her array are the same as the bits in the corresponding position in Andrei’s array.
Carroll has promised that either one of those two conditions will be true.
To give an example with 3 bit arrays, if Andrei gets 011 and Belle gets 101 they have exactly 3/3=1 of their bits in common and 2 distinct. If Belle had received 100 then the two arrays are entirely distinct. Following Carroll’s rule, she could not have received 111 for example.
Clearly Andrei can just send his entire array to Belle. But here is the twist. Carroll will give them $(99-message length)*100 so that shorter messages get more money. She sets out the rules as follows:
- Andrei and Belle can talk only before they receive their arrays from Carroll.
- Whatever scheme they come up must always allow Belle to give the right answer no matter what arrays Carroll gives them. Belle’s decision on what to output must only depend on the message she gets from Andrei and her own array of bits.
How much money can they make?