One of the greatest joys in problem solving is to solve a puzzle and realize that the solution is an unexpected variant of something very familiar. I solved a puzzle yesterday whose solution’s unexpectedness left a nice aftertaste.
As we repeatedly pick one of the triangles and chop it into two, it turns out—and this is what we want to prove—that no matter what order you go about picking triangles to split, you will always have two triangles that are of the same size.
Let's call the three triangles we start with A, B, and C. They have hypotenuse 1 each.
Split B into two, and C into two. Also split both the parts generated from C into two. After these 4 splittings, the seven triangles left have hypotenuse 1(A), x and y (parts of B), and x2, xy, xy, and y2 (parts of parts of C). If we finally split one of the xy triangles, we are left with eight triangles no two of which are congruent.
Starting with four triangles, however, it turns out, we are guarenteed to always have at least two congruent triangles.
The pigeonhole principle, stated by itself, is exceedingly obvious and it is hard to believe that it can be a powerful technique. Here is what it says: if you stuff eleven pigeons into ten holes, some hole must contain at least two pigeons. What could be more elementary?
Yet, it can be used to prove such things as: “if you pick any 21 integers from among integers between 1 and 40, you are bound to have chosen two numbers such that one is a multiple of the other” or even that there must be two people in the world who have read exactly the same number of words in their lifetimes. Here, I will present the proof of the first of these since it gives the flavor of how the principle is in practice used.
We will distribute the 40 integers between 1 and 40 into 20 “holes”. These holes are: {1, 2, 4, 8, 16, 32}, {3, 6, 12, 24}, {5, 10, 20, 40}, {7, 14, 28}, …, {39}. That is: for the first hole, we started with 1 and included everything obtained by repeatedly multiplying by two. In the next hole, we started at 3 and did the same thing. In the next, we started at 5. The 20 holes correspond to each odd number less than 40. Notice that if we select two numbers from a single hole, one must be a multiple of the other. Moreover, since we pick 21 numbers and there are only 20 holes, by the pigeonhole principle, no matter which actual numbers we pick, we will necessarily have picked two numbers from some hole, and this completes the proof that one of the numbers we picked is a multiple of another number we picked.
Conversely, if the sum of girths is greater than the sum of entrance sizes, some hole must have more than one pigeon in it.
The Puzzle
You are given four identical right triangles. You will now repeatedly pick one of the triangles and split it into two triangles by dropping a perpendicular from the right angle to the hypotenuse (see figure). Note that both these smaller triangles are also right triangles and are in fact similar to the original triangle. |
| ΔABC is split into two: ΔABD and ΔACD |
As we repeatedly pick one of the triangles and chop it into two, it turns out—and this is what we want to prove—that no matter what order you go about picking triangles to split, you will always have two triangles that are of the same size.
Starting with Three Triangles is Not Enough
Since all triangles we will ever produce are similar, two triangles are congruent if their hypotenuse is the same length. Let's say that each of the three triangles we start with has hypotenuse 1, and splitting it results in triangles with hypotenuse x and y.Let's call the three triangles we start with A, B, and C. They have hypotenuse 1 each.
Split B into two, and C into two. Also split both the parts generated from C into two. After these 4 splittings, the seven triangles left have hypotenuse 1(A), x and y (parts of B), and x2, xy, xy, and y2 (parts of parts of C). If we finally split one of the xy triangles, we are left with eight triangles no two of which are congruent.
Starting with four triangles, however, it turns out, we are guarenteed to always have at least two congruent triangles.
Smacks of Pigeonhole
Features of problems alert us to possibly techniques that might work. For example, a problem that asks us to “show that for all integers such and such as true” can often be tackled using mathematical induction. Similarly, the phrasing “show that there are guaranteed to be two entities with such and such properties” suggests to me the use of the pigeonhole principle.The pigeonhole principle, stated by itself, is exceedingly obvious and it is hard to believe that it can be a powerful technique. Here is what it says: if you stuff eleven pigeons into ten holes, some hole must contain at least two pigeons. What could be more elementary?
Yet, it can be used to prove such things as: “if you pick any 21 integers from among integers between 1 and 40, you are bound to have chosen two numbers such that one is a multiple of the other” or even that there must be two people in the world who have read exactly the same number of words in their lifetimes. Here, I will present the proof of the first of these since it gives the flavor of how the principle is in practice used.
We will distribute the 40 integers between 1 and 40 into 20 “holes”. These holes are: {1, 2, 4, 8, 16, 32}, {3, 6, 12, 24}, {5, 10, 20, 40}, {7, 14, 28}, …, {39}. That is: for the first hole, we started with 1 and included everything obtained by repeatedly multiplying by two. In the next hole, we started at 3 and did the same thing. In the next, we started at 5. The 20 holes correspond to each odd number less than 40. Notice that if we select two numbers from a single hole, one must be a multiple of the other. Moreover, since we pick 21 numbers and there are only 20 holes, by the pigeonhole principle, no matter which actual numbers we pick, we will necessarily have picked two numbers from some hole, and this completes the proof that one of the numbers we picked is a multiple of another number we picked.
The Weighted Pigeonhole Principle
This solution to the puzzle involving triangles can be expressed using a “weighted” generalization of the pigeonhole principle. Imagine that you have ten pigeons with girths g1, g2, …, g10. Further, you have a twenty holes that have entrance sizes e1, e2, …, e20, where the entrance size is the largest girth of a pigeon that may enter. If it is true that no more than one pigeon is present in a hole, then the sum of the girths (that is, ∑gi ) can be at most the sum of entrance sizes (that is ∑ei).Conversely, if the sum of girths is greater than the sum of entrance sizes, some hole must have more than one pigeon in it.
Solution to the Puzzle
Some observations. Since all the triangles generated by splitting are similar to each other, the length of the hypotenuse identifies the triangle. If the initial hypotenuse is 1, and the other two sides are x and y, then splitting one of the original triangles will result in two triangles that have x and y as the hypotenuse. Splitting the triangle with hypotenuse x will result in two triangles that have hypotenuse x2 and xy. Similarly, splitting the triangle with hypotenuse y will result in two triangles that have hypotenuse y2 and xy.Defining the Holes
We define holes corresponding to every possible hypotenuse size, that is, xkyl, for every pair of integers k and l. We shall put a pigeon with a particular hypotenuse (say, xy) into the corresponding hole. Thus, if there are two pigeons in a given hole, they have the same hypotenuse and are congruent.
