| | |
The Pigeon-Hole Principle: Prove that if $kn+1$ pigeons are placed into $n$ pigeon-holes, then some pigeon-hole must contain at least $k+1$ pigeons.
Let's try to argue by contradiction:
Assume that no pigeon-hole contains at least $k+1$ pigeons.
This means that each pigeon-hole contains at most $k$ pigeons. There are $n$ pigeon-holes, so there are at most $nk$ pigeons total in all of the pigeon-holes. However, this contradicts the given fact that $kn+1$ pigeons were placed into the $n$ pigeon-holes.
Hence, our assumption must be rejected, and the opposite must be true:
Some pigeon-hole must contain at least $k+1$ pigeons.
Pick $5$ integers from $1$ to $8$, inclusive. Show that two of them sum to $9$.
We shall use the pigeonhole principle:
Consider the $4$ pairs of numbers $(1,8)$, $(2,7)$, $(3,6)$, and $(4,5)$. In each case, the sum of the two numbers is $9$. These pairs will serve as our "pigeon-holes". If we select $5$ distinct integers (i.e., the "pigeons") from the integers $1$ to $8$, inclusive -- then by the pigeonhole principle, at least two of them must be in the same pair. Since the $5$ integers chosen were distinct, we have found two that add up to 9.
Show that among $n+1$ arbitrarily chosen integers, there must exist two whose difference is divisible by $n$.
When dividing by $n$, note that there are $n$ possible remainders*: $0, 1, 2, \ldots, n-1$. These will play the role of our "pigeon-holes".
Taking as our "pigeons" the $n+1$ arbitrarily chosen integers -- by the pigeon hole principle, there must be two of these integers, say $a$ and $b$, that must have the same remainder, say $r$, upon division by $n$.
As such, we can find integers $k_1$ and $k_2$ such that
$$a = nk_1 + r \quad \textrm{ and } \quad b = nk_2 + r$$Consequently,
$$a-b = nk_1 - nk_2 = n(k_1-k_2)$$This implies $n \mid a-b$.
Hence, there must always exist two of our original $n+1$ numbers whose difference is divisible by $n$.
QED.*Assuming remainders are found in the normal way -- as the positive values of magnitude less than $n$ that can be added to a multiple of $n$ to produce the number $n$ is dividing.
Consider the first $2n$ integers, $1, 2, 3, \ldots, 2n$. If more than $n$ of these integers are selected, show that two of the selected integers must be relatively prime.
We can argue with the pigeon-hole principle...
Consider the sets $\{1,2\}, \{3,4\}, \{5,6\}, \ldots \{2n-1,2n\}$. These sets will be our "pigeon-holes". For any one of these sets, say $\{a,a+1\}$, we note that $a$ and $a+1$ have to be relatively prime. To see this, suppose $d$ was a positive integer divisor of both. Then $$\begin{array}{rcl} d \mid a \textrm{ and } d \mid a+1 &\Rightarrow& d \mid (a+1) - a\\ &\Rightarrow& d \mid 1\\ &\Rightarrow& d = 1 \end{array}$$
So we have $n$ sets that each consist of two relatively prime numbers. If we select more than $n$ of the integers from $1$ to $2n$ (these are our "pigeons"), then by the pigeon-hole principle, one of the sets must contain two of the selected integers. Since these two integers must then be relatively prime, we are done.
Rearrange the first $n$ integers $1, 2, 3, \ldots, n$, listing them as $a_1, a_2, \ldots a_n$. Prove that if $n$ is odd, then $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ must be even, regardless of how the integers were initially rearranged.
We argue indirectly...
Assume $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ is odd. Then each factor $(a_1 - 1)$, $(a_2 - 2)$, ... $(a_n - n)$ must be odd. This implies that $a_1, a_3, a_5, \cdots, a_n$ are all even, while $a_2, a_4, \cdots, a_{n-1}$ are all odd. Contemplating the potential use of the pigeon-hole principle (although we end up not using it after all), we count the number of odds and find there are $\displaystyle{\frac{(n-1)}{2}}$ of the $a_i$'s that are odd.
However, the numbers $a_1, a_2, \cdots a_n$ are precisely the numbers $1,2,3,\ldots,n$ -- just possibly in a different order. The number of odd numbers in this last list is $\displaystyle{\frac{(n-1)}{2} + 1}$, so we have a contradiction.
Hence, we must reject our initial assumption that the product $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ could be odd. Instead, it must always be even.
If each point of the plane is colored red or blue, prove there are two points of the same color at distance one inch from each other.
We shall argue by the pigeon hole principle:
Consider the vertices of an equilateral triangle in the plane whose side length is one inch. There are two colors (our "pigeon-holes") and 3 vertices (our "pigeons"). Two of these vertices must hence be of the same color. Noting that every pair of such vertices are at distance one inch from one another, we are done.
Prove that among any five points selected inside a square with side length 2 units, there always exists a pair of these points that are within $\sqrt{2}$ units of each other.
We can argue using the pigeon-hole principle...
Suppose we divide our square into 4 smaller square regions each of side length 1 unit, like so:
These smaller square regions will be our "pigeon-holes". Now, if one selects $5$ points (our "pigeons") inside the larger square, and noting that $5$ is one more than the number of smaller square regions -- the pigeon-hole principle requires that 2 of these points be in at least one of the smaller squares. Since the maximum distance between two points in one of these smaller squares is the length of the diagonal of that square, namely $\sqrt{2}$, we know there exists a pair of points out of the group of five originally selected that will be within $\sqrt{2}$ units of each other.
Prove that among any five points selected inside an equilateral triangle with side equal to one inch, there always exists a pair at the distance not greater than one half an inch.
We can argue using the pigeon-hole principle...
Suppose we divide our equilateral triangle into 4 smaller equilateral triangle regions each of side length one half an inch, by connecting the midpoints of each side:
These smaller regions will be our "pigeon-holes". Now, if one selects $5$ points (our "pigeons") inside the larger triangle, and noting that $5$ is one more than the number of smaller triangular regions -- the pigeon-hole principle requires that 2 of these points be in at least one of the smaller triangles. Since the maximum distance between two points in one of these smaller triangles is the length of the side of that smaller triangle, namely one half an inch, we know there exists a pair of points out of the group of five originally selected that will be at distance not greater than one half an inch from one another.
Is it possible to cover a chessboard with dominoes that each cover exactly two squares? What if the squares in two diagonally opposite corners are removed? Explain.
It is certainly possible to cover a chessboard with dominoes that each cover exactly two squares. Consider the following:
However, if the two diagonally opposite corners are removed, this changes.
We argue indirectly, using the pigeon-hole principle...
Assume it is possible. Note that the diagonally opposite corners of a complete chessboard are of the same color. Without loss of generality, let's suppose the two corners removed were both white. Consequently, there are only 30 white squares left from the original 32 on a complete board, while the number of black squares remains unchanged at 32. These 32 black spaces will play the role of our "pigeons". Each domino, no matter how it is placed on the board to cover exactly two squares will always cover exactly one black square and exactly one white square. With 62 places to be covered, 31 dominoes will be needed. These 31 dominoes will be our "pigeon-holes". By the pigeon-hole principle, two of the black squares must be covered by the same domino. This is clearly impossible, so we have our desired contradiction. The reverse of our assumption must be true:
It is not possible to cover a chessboard with dominoes that each cover exactly two squares if the squares in the two diagonally opposite corners have been removed.
🔎 Every point of a plane is colored one of 2 colors. Prove that there will always be an equilateral triangle with all its vertices of the same color. Also prove that there exists a rectangle, all of whose vertices are the same color.
For the second part, in how many ways can 3 collinear points be colored with 2 colors?
🔎 Given any set of ten natural numbers between 1 and 99 inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements.
Note that $\{a,b,c,d\}$ and $\{b,c,e,f\}$ are not disjoint sets, but $\{a,d\}$ and $\{e,f\}$ are.