(This is a talk I gave for the Canadian IMO team at their 2014 winter camp at York University on Jan 3, 2014.)
The pigeonhole principle is a remarkable combinatorial theorem that looks silly and obvious, but turns out to be quite powerful and useful, especially in the context of contest problem solving. I’m going to present a couple of statements of the pigeonhole principle, then I’ll give some broad applications of it. I’ll end off with a list of problems.
People in Germany like Math! After my recent trip to Bonn, Germany, I visited my friend Maria in Munich, Germany for a weekend. She was wonderful and showed me all around town. One thing about her that has always impressed me was how into mathematics she is. When I met her in Toronto last year, I distinctly remember thinking that her interest in mathematics (she is a PhD student in Classics) came from her German education. My trip to Munich only reinforced this.
(After writing some posts directed at other mathematicians, here is one for everybody.)
I was sifting through some old issues of Crux Mathematicorum last Friday. For those of you who don’t know, this is a wonderful magazine that contains tons of math questions generally like those you would see in a math contest or olympiad, and the difficulty ranges from elementary school to undergraduate. In the September 2009 issue, I stumbled upon the following nice problem originally from the 2005 Brazilian Mathematical Olympiad. It is one of those problems that is mathematical in flavour and doesn’t need any previous math knowledge to begin thinking about the problem. For me, a nice problem is one that rewards you for thinking about it and can be attacked from many different angles.
So here’s the problem as stated:
We have four charged batteries, four uncharged batteries, and a flashlight which needs two charged batteries to work. We do not know which batteries are charged and which ones are uncharged. What is the least number of attempts that suffices to make sure the flashlight will work? (An attempt consists of putting two batteries in the flashlight and checking if the flashlight works or not.)
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 