5

The problem statement:

I have two people A and B, and think of a natural number n. Then I give the number n to A and the number n + 1 to B. I tell them that they have both been given natural numbers, and further that they are consecutive natural numbers. However, I don't tell A what B's number is and vie versa. I start by asking A if he knows B's number. He says \no". Then I ask B if he knows A's number, and he says \no" too. I go bak to A and ask, and so on. A and B an both hear each other's responses. Do I ever get a \yes" in response? If so, who responds first with \yes" and how many times does he say \no" before this? Assume that both A and B are very intelligent and logical.

I understand we should start from a simple case where $A = 1$, and $B = 2$ ---- obviously number of "no" from $A$ is $0$.

Then for $A = 2, B = 3$ case, $A$ responds with "no" because $B$ could be $1$ or $3$, then $B$ responds with "no", so $A$ knows $B$ is not $1$, then in the second respond he says "yes".

So on and so forth.

However, it's not clear to me how should I extend the case to $n$ and $n+1$? Maybe better to have a recursive relation between $(n,n+1)$ and $(n-1,n)$ case?

ChuNan
  • 303
  • "I tell them that they have both been given natural numbers, and further that they are consecutive natural numbers." It's implied but unstated that A knows they got the lower one. If they don't, then this is in general unsolvable (you never get a "Yes" answer from either, except in the special case where one of them gets 1, because obviously the other one had to get 2, because it couldn't be 0). – smci Dec 29 '20 at 07:01
  • @smci that's not true, the OP even shows the strategy for $n=2$. if A knows they got the lower one, then there's nothing to guess. – Alan Dec 30 '20 at 01:28
  • @Alan: I said if A doesn't know whether they got the lower/higher one, then they can't know B's number for sure, hence this is in general unsolvable. (They could take a 50/50 guess, but the rules don't allow for that). – smci Dec 30 '20 at 04:35

1 Answers1

7

Your examples suggest that if $A$'s number is $n$, then $A$ can guess the number within $n$ guesses. You've already proved the $n=1$ case. Suppose that $A$'s number is $n>1$ and that the statement is true for $n-1$. $A$ knows that $B$'s number is $n-1$ or $n+1$. Suppose no one has guessed the number after $n-1$ turns. Then $A$ can reason as follows. Reversing the roles of $A$ and $B$, if $B$'s number were $n-1$ he would have known it by turn number $n-1$, by the induction hypothesis. ($B$ can just ignore $A$'s first statement.) Therefore, on his $n$th turn, $A$ knows that $B$'s number is $n+1$.

saulspatz
  • 53,131