Last time, just in time for Christmas, we looked at the Secret Santa Problem. Basically the problem is to set up a secret santa type gift exchange without using any external aids like random number generators. A similar problem given to me by Sam Coskey is the following:
Sam’s Problem. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?
When Sam gave the problem to me he intended that each player would choose a natural number and then they would sequentially ask questions to each other, possibly refining their original numbers. In this sense it is more like a game of Guess Who than secret santa.
After much thinking, it turns out that there is a fairly easy solution to this problem.
Part 1. Can either player choose the number 0?
Well no, because that person would know that they have a smaller number than the other player.
Part 2. If both players know that cannot be chosen then cannot be chosen (as would have to be the smaller of the two numbers). So by induction, no number can be chosen by either player.
The lesson here is that induction is a very useful technique! This sounds naive but, when problem solving for contests, induction is often overlooked. Here is another related problem:
Father/Son problem. Is it possible for two players to each choose a human being so that the two humans are father and son, but neither player knows who has the father and who has the son?
The solution is again fairly simple, and uses induction. This time we need a different type of induction. We observe that no player can pick the first ever human being (as they would have the father of the other player’s choice). Now if there is a set S of humans that cannot be chosen, then the sons of people in S cannot be chosen either.
There you go, induction wins again!