The One Or The Plus One
You give Alice and Bob each a closed box containing a number. They both know that the two numbers are consecutive positive integers, but do not know the opponent's number. Then you give them a blank card and a pencil each, and have them play the following game:
- In each turn, they could predict what the number in their opponent's box is by writing it down on the card. Whoever can do so wins. They are only allowed to do this when they know the answer.
- Or, they could choose not to play the turn and exchange blank cards, indicating that they do not know the answer yet as of that turn.
Given that the two integers given to Alice and Bob are 16 and 17, respectively, who wins and after how many turns?
Clarification : Alice/Bob only attempts to answer if they know the correct answer. This is not a guessing game.
You might also enjoy the Blue Eyes Puzzle.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I understand your solution. I think the rules of your game may need to be clarified. Somehow you seem to eliminate possibilities each round. Such as after round six ..you may not have 1,2,3,4,5,6... that is not written in the rules the way I read them. Without this rule it is a never ending game..a possible solution given. In example given...Alice would think he has 15 or 17 and he would think she had 16 or 18. They would never know which.
Log in to reply
No. The fact that a number of rounds have been passed (without the players being able to deduce a decision) gives the players information. As I observed, if X has 2 and Y 3 , for example, then X would know that Y had either 1 or 3 . If Y passes on a round, then she cannot have 1 , since Y would, in that case, know immediately that X had 2 , and therefore would not have passed. Thus, after a round of passes, X knows that Y has 3 , but Y would still be unsure what X had. As my inductive proof shows, each round of passing excludes one more number, and the player with the smaller of the two numbers will always be the first to know her opponent's number.
Log in to reply
Sorry, I really don't see how this progresses beyond n=4. If A has 5, then they don't know if B has 4 or 6. Hearing that B does not now know the number does not add to this knowledge, because whether they had 4 or 6 they would have no way of knowing whether A's number was higher or lower, so there would be no elimination, however many rounds took place. The point is that if A has 5 or more then B's passing of a blank card adds no more knowledge at all (because they could still equally have 4 or 6), so the problem has not progressed.
Log in to reply
@Angus Walker – Sure, one round of passing does not give enough information, but a number of rounds of passing does.
If A has 1, he knows B has 2 straight away.
If A has 2, he knows B has 1 or 3. If B had 1, he would have known that A had 2 straight away. If there is a round of passing, this means that B must have 3.
If A has 3, he knows that B has 2 or 4. If B had 2, he would have known that A had 3 after one round of passing. Thus, if there are two rounds of passing, A knows that B cannot have 2, and so knows that B has 4.
If A has 4, he knows that B has 3 or 5. If B had 3, he would have known that A had 4 after two rounds of passing. Thus, if there are three rounds of passing, A knows that B cannot have 3, and so know that B has 5.
If A has 5, he knows that B has 4 or 6. If B had 4, he would have known that A had 5 after three rounds of passing. Thus, if there are four rounds of passing, A knows that B does not have 4, and hence that A has 6.
And so on. Each time, use the result of the previous paragraph to help you with the current argument (that is what induction is all about).
Log in to reply
@Mark Hennings – I think I've got it. What feels counter-intuitive is that on round 1 (with n=16 say), the amount of information exchanged appears to be 0 and one would have thought that any number of 0s never adds up to anything more than 0. Just shows how hard it is to get your head around even quite simple abstract mathematical problems.
This assumes your opponent has common sense And we all know that is rare.
It is not abundantly clear to me that they know their own numbers. The "closed box" seemed to imply that they didn't.
what happens when they exchange blank cards? how would passing for 15 turns determine the fact that she has 16 and he has 17?
Mark..I do not see in the question that the round eliminates the internet if the round choice.
Log in to reply
You are going to have to explain what that means - a case of autocorrect gone wrong? The whole point of k-level thinking is that what you are able to deduce varies as you observe other decisions that are made.
Log in to reply
Basically the catch here is the positive integer thing! Other than that the game should've continued indefinitely
Log in to reply
@Kunal Gupta – Absolutely. If all A and B knew was that they had consecutive integers, which could be positive or negative, the game could never end.
Oops wait got it
I don't get the answer. Both of them knows his own number. So they have only two guesses for the opponent's number. For Alice it is 15 or 17 and for Bob it is 16 or 18. So how can it start for 0, 1, 2...? They will continue passing and still have no idea.
Log in to reply
So basically, each turn tells you something about the other player's number. I already know my own (though again, I don't find that to be clear in the initial reading), and I know that my opponent's number is one more or one less than mine. (This tidbit can actually throw you off. It's best to forget it at first.)
I also know that the numbers are in the set "Positive Integers".
Let's say my number is 6.
On the first round, I'm going to pass a blank card, because I don't know what my opponent's card was. But I'll think, "This is ridiculous. The only way I'd know what their card was was if I had 1, because then the only option would be 2."
I then look at my opponent's card. It's blank. "Heh, guess he didn't have a 1, either. Oh...
"So if he doesn't have a 1, then if I had a 2, I could correctly guess that he had a 3. But I don't." So I pass a blank card.
He passes back a blank. "Now, assuming he knows what I know, if he'd had a 2, he could've guessed mine to be a 3. So he doesn't have 1 or 2. But I don't have a 3, so I can't guess 4." Pass a blank card.
Once again, blank card back. He doesn't have 3. I don't have 4, so can't guess 5. Pass a blank.
Blank comes back. "He doesn't have a 4. Now it comes to it. He could have a 5. That's a real possibility. The others were hypothetical, but this one's not, because I have a 6. So he has the advantage at this moment. But he could also have a 7, so I can't guess." So I pass a blank card.
I get his card - it's blank. "He doesn't have a 5, or he'd've known what I have! Since I have a 6, he has to have a 5 or 7, and since I know he doesn't have a 5, I can safely guess 7 and win!
I pass a 7. He passes a blank. I win.
Look at my more detailed reply to Angus, which goes through, in detail, the arguments for the smaller numbers, after which the pattern of argument should be clear.
Hi!
I think that If X has 3 and Y has 4 in that case X can predict the number in second attempt and not 3rd as you have tried to prove using induction.
Let me explain this now.
X has 3, so he knows that the possible numbers for Y are 2 or 4. But in the first attempt he can not say anything.
Next Y has 4, so he also can not be sure of X's number apart from the obvious fact that it can be either 3 or 5.
Now It is again X's turn and this time he can easily claim that Y has 4. Because if Y had 2, then Y would have been able to tell in his first attempt itself that X has 3. (As X would have been able to predict Y's number if he had 1 but was not able to do so).
So your logic stands valid for first two cases which you mentioned in your explanation but is clearly not valid for every case.
Log in to reply
You are misunderstanding the problem. At each stage, either both A and B pass, or one knows the other's number. You are playing the game with the two players alternately passing or choosing. That is a different game.
The challange is nothing clear regarding that each turn must represent the answer. But if so, I agree with Mark Hennings and the answer should be 15 and not 16.
Poppycock! The logic is sound IF you assume the other person also understands the logic of the problem. The problem specifically stated, "This is not a guessing game," but you must GUESS about your opponents understanding of the logic. If something is actually "known", then it categorically cannot be false, but a failure in your opponents knowledge must undermine your own "knowledge". The fault is not in your elegant solution, but in the inept presentation of the problem.
Seventy-one percent answered this question "incorrectly". Either they DON'T understand the logic, and would contribute significantly to failure in the game's outcome, or they DO understand the logic and refuse to guess about their opponent's logical capacity. Here is a follow-up problem: "What is the probability, in a decimal,that the person who thinks he 'knows' will be wrong because his opponent didn't have a clue?"
If the two numbers are n and n + 1 , then then player X with number n will be able to determine that her opponent Y has n + 1 after n − 1 rounds of passing.
Prove this by induction. When n = 1 , then player X with 1 will know that her opponent Y has 2 without any rounds of passing. Suppose now that n = 2 , and that 1 round of passing has taken place. Now X knows that Y has either 1 or 3 . Since a round of passing has taken place, X knows that Y cannot have 1 , and so X knows that Y has 3 .
Suppose now that X has n and Y has n + 1 . X knows that Y has either n − 1 or n + 1 . If Y had n − 1 , she would have known X's number after n − 2 rounds of passing (by induction). Since this did not happen, X knows that Y has n + 1 .
Thus Alice, who has 1 6 while Bob has 1 7 , will be able to determine Bob's number after 1 5 rounds of passing.