14
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ I had to read fljx’s answer through three times before I could make any sense of it, because there’s a fundamental issue that’s not clear from the question. I understood the puzzle as Andrei having to send a specific subset of bits from his array to Belle (positions 11, 36 and 72, corresponding to [1, 0, 1] for example), and she would then have to tell whether she had 33/99 or 0/99 bits in common in her array, but fljx’s answer makes no sense under that interpretation. Is the message Andrei sends in fact allowed to contain any data at all in bit format? $\endgroup$ Jul 15, 2023 at 17:50
  • $\begingroup$ Also, your use of ‘message’ is confusing. You appear to be using it both to refer to the arrays they get from Carroll and the message sent from Andrei to Belle. I assume you mean that Andrei and Belle can talk only before they receive their arrays from Carroll? $\endgroup$ Jul 15, 2023 at 17:52
  • $\begingroup$ @JanusBahsJacquet Thank you for the fix. Yes Andrei sends any data he wants to Belle. I am just measuring the size of the message in bits. $\endgroup$
    – Simd
    Jul 15, 2023 at 18:54
  • $\begingroup$ Carroll will give a 99 bit array to Andrei and a possibly different one to Belle - the next sentence makes it apparent that it's not just possible, it' certain, that the array would be different, may be just omit the word "possibly"? $\endgroup$ Jul 15, 2023 at 23:43
  • $\begingroup$ @AndrewSavinykh I don't fully understand. It is possible for Andrei and Belle to get exactly the same array of bits $\endgroup$
    – Simd
    Jul 16, 2023 at 12:38

1 Answer 1

25
$\begingroup$

Andrei can send a message that is:

One bit long.
And they will get $9800 from Carroll

How?

Consider the two messages together.

If they are entirely different there will be exactly ninety nine 1's across both messages, so the combined parity will be odd.

If they have thirty three bits in common, those alike bits will contain an even number of 1's, and the unalike bits will have sixty six 1's across both messages. So the combined parity will be even.

So all Andrei has to do is send the parity of their message to Belle.

$\endgroup$
8
  • $\begingroup$ I am just checking, if we change 99 to 90 and 33 to 30, can your approach still apply? $\endgroup$
    – Simd
    Jul 15, 2023 at 8:29
  • $\begingroup$ @Simd if the message length is even, the parity solution no longer works. Not sure what the optimal solution would be in that case. $\endgroup$
    – fljx
    Jul 15, 2023 at 8:33
  • $\begingroup$ You cracked this very quickly! $\endgroup$
    – Simd
    Jul 15, 2023 at 20:22
  • 1
    $\begingroup$ Or just use gender-neutral language and skip all that. $\endgroup$
    – Omegastick
    Jul 17, 2023 at 15:37
  • 3
    $\begingroup$ @JasonSmith "their" as a gender neutral third person singular is pretty well established now and avoids a whole bunch of additional headaches. Using his/her is backward step. Using Google is a non-starter. Try getting it to reliably tell you what gender Bobby, or Carol, or Nicola should be (for example), when you have no idea what the cultural background of the question setter is. $\endgroup$
    – fljx
    Jul 18, 2023 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.