2
$\begingroup$

Alice, Bob and Charlie play a game.
Alice writes down two positive integers on a blackboard visible to Bob and Charlie. She says that one of them is of her own choice, the other number is the sum of two positive integers, which were secretly communicated before by Bob and Charlie, respectively. Now Alice asks Bob, if he knows Charlies number. If he says "NO", the corresponding question goes to Charlie. If he says "NO", the question goes to Bob and so forth.

Can we expect a "Yes" answer at some point?

$\endgroup$
5
  • $\begingroup$ How does Alice choose her number? $\endgroup$
    – bobble
    Nov 28, 2021 at 21:05
  • $\begingroup$ it is totally up to Alice which number she chooses $\endgroup$
    – ThomasL
    Nov 28, 2021 at 21:14
  • $\begingroup$ I ask because for some choices of number (e.g. the same as the sum), a YES is guaranteed trivially, but for others maybe not. $\endgroup$
    – bobble
    Nov 28, 2021 at 21:17
  • 1
    $\begingroup$ @bobble The question is whether all possible choices will eventually lead to a "yes" answer. Your goal is to figure out the "maybe not"; the existence of trivial YES cases isn't relevant. $\endgroup$
    – Deusovi
    Nov 28, 2021 at 21:19
  • $\begingroup$ @Deusovi, well explained. $\endgroup$
    – ThomasL
    Nov 28, 2021 at 21:21

1 Answer 1

3
$\begingroup$

I claim the answer is:

yes

and here's why:

First, let's slightly modify the game: Alice will write the two numbers on the board before she decides what numbers to give to Bob and Charlie. This is obviously equivalent (because Bob and Charlie don't do anything before receiving both their numbers and the sums), but it lets us think of the numbers as being fixed.

Now, we can just write out all the possibilities for a game: for instance, for the (5,7) game, the possibilities are:

(1,4) (1,6)
(2,3) (2,5)
(3,2) (3,4)
(4,1) (4,3)
(5,2)
(6,1)

Say some of these scenarios never end. Take a look at the one with the smallest number for Bob - the highest never-ending scenario on the list. Let's call this number $b$.
Since it's the highest, all the possibilities above it end in finitely many turns; say, after $n$ turns, all of them would be done. This means that once $n$ turns have passed, Charlie knows that Bob's number must be at least $b$. And this is common knowledge - it doesn't use any assumptions about the numbers in the actual game.


So, let's say $n$ turns have passed, and it's now Charlie's turn. If the larger sum is correct, Charlie now knows that Bob's number must be exactly $b$ -- if it were any bigger, then their total would exceed both the sums on the board! So Charlie can answer YES.
If the smaller sum is correct, Charlie answers NO. Now it's Bob's turn -- he knows that if the larger sum was correct, Charlie could've deduced his number. So Bob knows that the smaller sum is correct.
Therefore there is no topmost never-ending scenario, and that implies that this game always ends.

Note:

In actual gameplay, the game would end faster than this, because Bob and Charlie would be making more deductions about their numbers - for instance, the bottommost scenarios on my list would also end immediately. This doesn't change the logic; a NO answer from perfect players would give at least as much information as a NO from players limited to make only the deductions I've mentioned. So they can end the game quicker than the bounds I've given... but the question only asks whether it will end at all.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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