16
$\begingroup$

Abby selects a non-negative integer $A$, and Bobby selects a non-negative integer $B$. They then both tell their number secretly to Summy. Summy writes the numbers $5$, $8$, and $15$ on the blackboard, and announces that one of these three numbers is the sum $A+B$. Then the three go through several rounds of the following form:

  • Summy rings a bell.
  • Abby writes on a slip of paper whether she does know or does not know which of the numbers on the blackboard is the sum $A+B$.
  • Bobby writes on a (different) slip of paper whether he does know or does not know which of the numbers on the blackboard is the sum $A+B$.
  • Abby and Bobby give their papers to Summy.
  • Summy checks the papers. If at least one of the papers says YES, then the process stops. If both papers say NO, then the next round starts.

Abby and Bobby are absolutely honest and very very intelligent.

Question: What is the maximum number of times that the bell might be rung before the process stops?

Improve this question
$\endgroup$

6 Answers 6

Reset to default
23
$\begingroup$

10 times.

The following table gives the numbers of one person and the corresponding possible numbers of the other person.

own  other
0    5, 8, 15
1    4, 7, 14
2    3, 6, 13
3    2, 5, 12
4    1, 4, 11
5    0, 3, 10
6    2, 9
7    1, 8 
8    0, 7
9    6
10   5
11   4
12   3
13   2
14   1
15   0

Round 1:

If one of them has a number greater than 8 he/she would know that the sum is 15 as it can't be 5 or 8 anymore.

For the other numbers the following table is true(after both said no):

own  other
0    5, 8 -> no 15 as the other person would have known it
1    4, 7 -> no 14 as the other person would have known it
2    3, 6 -> no 13 as the other person would have known it
3    2, 5 -> no 12 as the other person would have known it
4    1, 4 -> no 11 as the other person would have known it
5    0, 3 -> no 10 as the other person would have known it
6    2    -> no 9 as the other person would have known it
7    1, 8 
8    0, 7

Round 2:

If one of them has a 6 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
0    5, 8
1    4, 7
2    3    -> no 6 as the other person would have known it
3    2, 5
4    1, 4
5    0, 3
7    1, 8 
8    0, 7

Round 3:

If one of them has a 2 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
0    5, 8
1    4, 7
3    5    -> no 2 as the other person would have known it
4    1, 4
5    0, 3
7    1, 8 
8    0, 7

Round 4:

If one of them has a 3 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
0    5, 8
1    4, 7
4    1, 4
5    0    -> no 3 as the other person would have known it
7    1, 8 
8    0, 7

Round 5:

If one of them has a 5 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
0    8    -> no 5 as the other person would have known it
1    4, 7
4    1, 4
7    1, 8 
8    0, 7

Round 6:

If one of them has a 0 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
1    4, 7
4    1, 4
7    1, 8 
8    7    -> no 0 as the other person would have known it

Round 7:

If one of them has a 8 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
1    4, 7
4    1, 4
7    1    -> no 8 as the other person would have known it

Round 8:

If one of them has a 7 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
1    4    -> no 7 as the other person would have known it
4    1, 4

Round 9:

If one of them has a 1 he/she now knows the number of the other one

For the other numbers the following table is true(after both said no):

own  other
4    4    -> no 1 as the other person would have known it

Round 10:

If they make it up to this round they now definitely know what number the other person has and at the same time what the sum of their numbers is.

EDIT:

This is actually a kind of derivation of the blue eyes problem:

In the 100 blue eyes problem - why is the oracle necessary?

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ in general, is the most-rounds-till-it's figured out scenario the one where both users have a number that is [one less than the smallest proposed sum]? Does the number of rounds depend on what the other numbers on the board are? $\endgroup$
    – Kate Gregory
    Commented Nov 19, 2015 at 19:53
8
$\begingroup$

The bell will be rung at most

10 times.

Since the situation is symmetric, consider it from the point of view of A who only knows their number and how B would respond if they had certain numbers. We can see how long it will take to know the sum for each starting number as follows:

  • 9-15: on first round, only option for sum is 15
  • 6: on 2nd round, know B is not 9 so sum is 8
  • 2: on 2nd round, know B is not 13; on 3rd round, know B is not 6 so sum is 5
  • 3: on 2nd round, know B is not 12; on 4th round, know B is not 2 so sum is 8
  • 5: on 2nd round, know B is not 10; on 5th round, know B is not 3 so sum is 5
  • 0: on 2nd round, know B is not 15; on 6th round, know B is not 5 so sum is 8
  • 8: on 7th round, know B is not 0 so sum is 15
  • 7: on 8th round, know B is not 8 so sum is 8
  • 1: on 2nd round, know B is not 14; on 9th round, know B is not 7 so sum is 5
  • 4: on 2nd round, know B is not 11; on 10th round, know B is not 1 so sum is 8

This covers all numbers, so the upper bound for the maximum number of rings is 10. B may, of course, say "yes" before A does, but since it's possible for both numbers to be 4, it's indeed possible for the bell to ring 10 times. Thus the bell can be rung a maximum of 10 times.

Improve this answer
$\endgroup$
3
$\begingroup$

Twice. If either had a number higher than 8, he/she would've known the first time. If either had a number higher than 5 the second time, they would've known. Which leaves only the possibility of 5, meaning the bell has rung for a maximum of 2 times.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ If Abby has the number 8 she won't say yes the first time, because Bobby could have 0 or 7. Having 0 or 7 Bobby would also answer no the first round. From the knowledge that both of them answered no they wouldn't gain enough information to deduce each others number in the second round. $\endgroup$
    – The Dark Truth
    Commented Nov 19, 2015 at 12:21
  • $\begingroup$ If Abby has 8 and Bobby has 0, they would know the second round. Because Abby would know Bobby has 0 or else it would be impossible to get a valid number. If Bobby has 7 Abby would say yes the second time as well. Because she would know it has to be either 0 or 7, else there would be again no valid number. $\endgroup$
    – Jens
    Commented Nov 19, 2015 at 12:28
  • 4
    $\begingroup$ Yes she would know that he has EITHER 0 OR 7. But she doesn't know which of the two numbers exactly he has. $\endgroup$
    – The Dark Truth
    Commented Nov 19, 2015 at 12:30
  • $\begingroup$ You raise a perfectly valid point. I can't seem to think of a way where either would know the exact answer in said specific case. I'll have to think about it a bit more. (Or 0 should not be allowed?) $\endgroup$
    – Jens
    Commented Nov 19, 2015 at 12:48
3
$\begingroup$

I think the answer is 4 times.

After the first bell, if either has >8 the answer is 15 and there is no second bell.

After the second bell, if either has >5 the answer is 8 and there is no third bell.

After the third bell, both know that each has 5 or less. For the answer to be 8, the numbers must be 4 and 4 or 5 and 3. If either has 0, 1 or 2 the answer will be 5 and there will be no fourth bell.

The fourth bell sounds only if the answer is 8.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I like how succinctly this explains it. $\endgroup$
    – Engineer Toast
    Commented Nov 30, 2015 at 14:44
  • 2
    $\begingroup$ @EngineerToast This is probably because it's wrong. After the second bell 15 is still a possible answer (e.g one has 7 the other has 8). No one can know yet if 8 or 15 is correct. $\endgroup$
    – Sleafar
    Commented Nov 30, 2015 at 17:13
  • $\begingroup$ I guess I'm not as smart as I think I am. Since 15 is still a possibility after the second bell, only 6 has been eliminated (answer = 8). Following my logic from there gives me the 10 round sequence of The Dark Truth, duly credited with an up-vote. $\endgroup$
    – Sceptical-H
    Commented Dec 5, 2015 at 19:54
  • $\begingroup$ I also overlooked the case x=8 for the first round and came to the same conclusion. Easy mistake to make, good reminder to check for special cases. $\endgroup$
    – Jakob Pamp Bengtsson
    Commented Mar 1, 2017 at 10:21
2
$\begingroup$

Just as a side note, in addition to the correct answers already posted. It is interesting that the numbers 5, 8, 15 are kind of special. Most triples of numbers yield unsolvable games!

For example, if the numbers given are 1, 2, 3, and neither player had picked three at the beginning, you can't get anywhere and the game never terminates.

Improve this answer
$\endgroup$
2
  • $\begingroup$ To me this is still really confusing. For me it seems the game is never terminated, since no new information is ever received, even with the numbers on the blackboard being 5, 8 and 15. It seems that it's more bound to what numbers they initially choose. Let's say Abby chose 4. This means Bobby either has 1, 4 or 11. I'm still confused how going through those rounds any new information is revealed for them to be 100% sure what the other person has. Am I overthinking this? $\endgroup$
    – Leathe
    Commented Nov 20, 2015 at 7:50
  • 1
    $\begingroup$ @Leathe The information that is gained with each round is knowledge about the knowledge of the other person. To take the first round as an example: If both say no, then person1 knows that person2 has a number smaller than 9(as otherwise person2 would have know that 15 is the only possible sum). At the same time person1 also knows that person2 has made the same deductions. So person1 knows that person2 knows that person1 has a number smaller than 9. Following similar deductions for every round the knowledge of both slowly grows until at least one has enough information to know the others number $\endgroup$
    – The Dark Truth
    Commented Nov 20, 2015 at 11:20
0
$\begingroup$

Clarification

For me, according to my experience in scientific publication, non-negative means strictly greater than zero. (Otherwise, people write positive for x≥0.)

Answer

0 < A, B <15 and A + B $\in$ {5, 8, 15}

First round

  • if A≥8 or B≥8, then sum is 15 and A or B write YES
  • else A<8 and B<8, both write NO

Second round: A<8 and B<8 and A + B $\in$ {5, 8}

  • if A≥5 or B≥5, then sum is 8 and A or B write YES
  • else A<5 and B<5, both write NO

Third round: A<5 and B<5 and A+B $\in$ {5, 8}

  • if A $\in$ {1, 2, 3} or B $\in$ {1, 2, 3}, then the sum must be five and one can write YES
  • else, A = B = 4, both write NO

Fourth round: A = B = 4

  • both write YES
Improve this answer
$\endgroup$
3
  • $\begingroup$ 0 is neither negative nor positive, this leaves no space for debate. Your basic assumption does not hold. Please provide a link to a scientific publication which states otherwise. $\endgroup$
    – elias
    Commented Mar 1, 2017 at 10:12
  • 3
    $\begingroup$ Please see this question on math SE. As you can see, it's more or less up to debate and context, not something that is always clearly defined. $\endgroup$
    – Jakob Pamp Bengtsson
    Commented Mar 1, 2017 at 10:20
  • $\begingroup$ Thanks @JakobPampBengtsson, and sorry for my first comment then, there's something new to learn every day. I'm very surprised to see that, because then it means, the term 'positive' leaves some ambiguity if the context is not well-defined, and can lead to confusion in these cases. $\endgroup$
    – elias
    Commented Mar 1, 2017 at 10:43

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.