After a long hiatus (7 months!) I am finally back to writing. This week I revisited an old problem that Sam Coskey told me a couple of years ago. Some of you will remember this “Secret Santa problem”, which I wrote about before. The problem is:
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?
Last time I discussed the solution to Sam’s problem:
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?
I established, by induction, that it is impossible to do this. Great. We write “QED” and move on. There is a very convincing counter-argument that was brought to my attention by Jacob Tsimerman and a student at the Winter Canadian IMO camp. They proposed a method that seems like it should solve Sam’s problem in the positive. What exactly is going on in their method? Where is the mistake?
Jacob’s method. Player 1 chooses a large enough number N (say greater than 100); this is now their number. Player 1 writes down the numbers N+1 and N-1 on different pieces of paper and presents them face-down to Player 2. Player 2 chooses one of them and burns the other one without looking at it. The number Player 2 sees is their number.
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 
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!
Happy holidays everyone! As Christmas approaches so do the Christmas related problems. I’m not talking about the long lines at stores or the busy days filled with errands, I’m talking about Christmas math problems. Here is one I learned at my department holiday party from Eric Hart and Jeremy Voltz.
This whole post is going to be directed at a general audience.
Secret Santa Problem (simplified). An office needs to determine how to set up a secret santa gift exchange, but they have lost all of their dice and paper! How can each person in the office have exactly one person for whom they are buying a gift and also each person does not know who is buying them a gift?
Here we allow some of the employees to have private conversations if they wish.
Attempt 1: The obvious first thing to do (that doesn’t work) is to have one person tell everyone whose gift they are buying. You can tell right away why this won’t work: It is too much work for that one person the designator will have to designate someone to buy a gift for the designator!
Attempt 1.a: Have the boss tell everyone what they should do. Well… I don’t think the boss is going to like this idea. We should really try to find an internal solution. That is, let’s try to find a solution that does not use anything external (like random number generators, extra people, secret santa consultants, etc.)
Mike Pawliuk - Mathematics 