When you place three apples into two boxes, then one of the boxes must contain at least two apples. You may say that this is trivial. Indeed, it is a very simple observation and it is perhaps the simplest form of what is called the “Pigeonhole Principle.”
There are many ways to state the Pigeonhole Principle. One of the easiest ways is the following:
When you place 
I remember I first learn the Pigeonhole principle in Read the rest of this entry ?
During a recent visit of my high school, Island School, one of my students asked the following questions:
Given an 8 by 8 chessboard with the opposite corners removed. How many rectangles are there?
First of all, I believe the motivation comes from the following two problems:
1) Given an 8 by 8 chessboard, how many rectangles are there?
2) Given an 8 by 8 chessboard with the opposite corners removed, can you tile it using 31 dominos?
The student simply asked the problem in the other setting. While the other problem formed this way “can you tile an 8 by 8 chessboard with dominos” is stupid, asking the number of ways to tile such a board using dominos is very difficult. Before diving into this, let’s answer the question raised by the student.
In fact, we will answer the following: given an n by n chessboard with opposite corners removed, how many rectangles are there.
Proof: First label the opposite corners as Read the rest of this entry ?
