4
$\begingroup$

Alice, Bob and Charlie play a game.

Alice secretly communicates a positive integer to Bob, and a positive integer to Charlie.

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, while the other is the sum of the two secret numbers.

Now Alice asks Bob if he knows Charlie's 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?

Improve this question
$\endgroup$
5
  • $\begingroup$ How does Alice choose her number? $\endgroup$ Commented Nov 28, 2021 at 21:05
  • $\begingroup$ it is totally up to Alice which number she chooses $\endgroup$ Commented 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$ Commented Nov 28, 2021 at 21:17
  • 3
    $\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$ Commented Nov 28, 2021 at 21:19
  • $\begingroup$ @Deusovi, well explained. $\endgroup$ Commented Nov 28, 2021 at 21:21

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
2
$\begingroup$

Let Bob's number $= B$, Charlie's number $= C$, the lower of the two chosen numbers $= l$, and the higher of the two chosen numbers $= h$. Further, let $d = h - l$.

Once Bob or Charlie know with certainty which of $l$ and $h$ is the summation of their numbers (here notated the 'key') it is trivial to calculate the other number.

The first 'round' is trivial; if $B >= l$ then Bob solves, and if $C >= l$ then Charlie solves. (Their own number being GTE to $l$ tells them the key must be $h$, and therefore the opposing number is $h$ less their own.)

We then begin in earnest with Bob.

Bob knows that $B < l, C < l$ from above. If also $B < d$, then $B+C < d+l$, or $B+C<h$. Therefore the key is $l$. Else he passes.

Charlie now knows that $B >= d$. If also $C + d > l$, it follows that the sum must be greater than $l$ and therefore the key is $h$. Else he passes.

Bob now knows that $C < l - d$. Therefore, if $B < 2d$, then $B+C < l - d + 2d$, or $B+C < h$, and Bob then knows the key is $l$. Else he passes.

Charlie now knows that $B > 2d$. If also $C + 2d > l$, it follows that the sum is greater than $l$ and therefore the key is $h$. Else he passes.

From this we may induct a generalization.

After the trivial round, let $n$ be the round number, starting with 1. if $B < nd$, Bob knows the key is $l$. Otherwise, if $C + nd > l$, Charlie knows that the key is $h$. Otherwise, proceed to the next round.

Note that we can rewrite those conditions as $n > B/d$ (for Bob) and $n > (l - C)/d$ (for Charlie). We can therefore assert that Bob will solve in $ceil(B/d)$ rounds, and Charlie in $ceil((l-C)/d)$ rounds; trivially, the lesser of the two will prevail.

In all cases the number is finite and therefore a halting state exists.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.