Let’s start with the following definition.
THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.”
Source: Discrete Mathematics and its Applications by Rosen.
Let’s have d boxes numbered 0, 1, 2, …, d-1. In a box, we will put a positive integer that, when divided by d, gives us a reminder equal to the number in the box.
For instance, let’s d=5, and one of the 6 numbers is 7. The reminder of 7 divided by 5 is 2. So, we will put the number 7 in the box labeled 2.
Having d boxes, and d+1 integers, by the pigeonhole principle, at least one box will have two or more integers.
Related exercises:
- Let(xi,yi),i = 1,2,3,4,5, be a set of five distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates.
- Show that if f is a function from S to T, where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f(s1)=f(s2), or in other words, f is not one-to-one
- A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them
- Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.
- A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.