I’ve talked about how analyzing games naturally leads to inductive arguments, and gave a few examples. Here is a tricky game problem which is a little mind bending. It’s much tricker than anything else I have suggested, so consider it a challenge problem (for fun).
Problem: Alice and Bob are infinitely intelligent, and honest, and they play the following game. They both write down a natural number on a piece of paper (without showing the other) and then give them to Chuck. Let’s call them \(a\) and \(b\). Chuck then reveals to Alice and Bob two numbers; one of the numbers is the sum \(a+b\), and the other is an integer \(c\), but Chuck does not tell either Alice or Bob which is which.
Chuck asks Alice: “do you know Bob’s number”? If Alice says yes, the game ends. Otherwise:
Chuck asks Bob: “do you know Alice’s number?” If Bob says yes, the game ends. Otherwise:
Chuck asks Alice: “do you know Bob’s number”? If Alice says yes, the game ends. Otherwise:
… Chuck keeps going back and forth alternatively asking Bob and Alice the same question. The problem it to show that, after finitely many turns, one of Alice or Bob says yes.
An Example: Suppose that Alice write down \(a = 7\) and Bob writes down \(b = 17\), and that Chuck writes down the numbers \(32\) and \(24\).
- Alice looks at these numbers and she can’t distinguish between whether Bob has the number \(24 – 7 = 17\) or the number \(32 – 7 = 25\), so she says no.
- Now it is Bob’s turn. Bob knows that Alice either has the number \(24 – 17 = 7\) or the number \(32 – 17 = 15\). He knows that if Alice had the number \(7\), then she would have said no on the first term. He also knows that if Alice had the number \(15\), she would think that Bob either had then number \(9\) or the number \(17\), so she also would have said no. So Bob can’t distinguish from Alice’s last answer whether she had either a \(7\) or a \(15\), so he says no.
- Now it is Alice’s turn. Alice knows that Bob has the number \(17\) or the number \(25\). She knows that if Bob has the number \(17\) then he would say no (as he did). She also know that if Bob has the number \(25\), then Bob would have said yes, since then Bob would know that the sum is \(32\) since \(24\) is not the sum of \(25\) and a natural number. (The fact that natural numbers are positive is a key fact, the game would not end if Alice and Bob were allowed to choose an integer.) So Alice says yes, and the game ends!
It should be very much clear that something inductive is going on in this problem. So the problem is: what is going on?