An Interesting Problem for Tree Huggers

Using the Pigeonhole Principle prove that are two red maple trees in the United States that have the exact same number of leaves.

A statement of the Pigeonhole Principle follows:

Given m boxes and n objects to place in those boxes, if n > m then there is at least one box with more than one object.

To be honest, this problem is mathematically unsolvable, but inductively reasonable.

You see, I didn't tell you anything about the trees or the leaves themselves.

Let's let the number of leaves per tree be n.
n can be 0, 1, 2, 3, ....
so on into infinity

Now let the number of trees be m.
m can be 0, 1, 2, 3, ....
and so on

Now if n < m, that is the number of leaves per tree is less than the number of trees,
then IT IS TRUE that there are two Red Maples that have the same number of leaves
at any given point in time.

There's just a slight problem. Who said that there had to be more trees than the maximum
number of leaves a tree can have?

While it's admittedly true that a tree is extremely unlikely to have tens of thousands of leaves and there
are tens of thousands of red maples out there, it's not technically impossible in mathematical terms.

So in essence, it is reasonable to say that it is almost certain that there are two red maples in the United
States with the same number of leaves. It's not deductively demonstrable from the Pigeonhole Principle alone.

But technicalities aside, yes it is nigh impossible for there not to be two red maples that have the same
number of leaves in the United States. Awesomely weird fact no?

Now, if n<m then this means that there are not enough leaves to go around...so perhaps there are two Red Maple Trees that don't have any leaves at all. As you said though, this is inevitably unsolvable.

Well no. I let n be the "number of leaves per tree".
That is, n is the number of leaves on any given tree, not the number of leaves total.

If we let the number of leaves be n on the other hand we do have other issues.

If we let n > m we have a major problem. I can actually disprove the statement that there must be two Red Maples with the same number of leaves.

We simply have m trees, and I arrange them like so.
The first tree has 0.
The second tree has 1.
The third tree has 2.
The fourth tree has 3.
...
The mth tree has m-1.
Such that n = 1 + 2 + 3 +...+ (m-2) + (m-1)

There's no reason that trees can't have this arrangement of leaves, and the existence of the possibility of the situation automatically disproves the hypothesis.

However if we let n < m, as Kenny said, it's easily provable.

We'll imagine the trees as boxes for now, and the leaves as leaves that we can put in the boxes.

If n < m, we'll just put one leaf in each box until we fill them all. But since n < m we can't fill them all. But we've got a sequence of leaves in each box that looks like this:
1, 1, 1, 1, 1, 1,..., 1, 0, 0, 0,...
Out to the mth box, or tree.

Now we go to the box containing a leaf to the farthest right. We'll take a leaf from that one and add it to the second box. Now we have

1, 2, 1, 1, 1,..., 0, 0, 0,...

Repeat this process, adding each leaf to the next box down the line so that you get this:
1, 2, 2, 2,..., 0, 0, 0...

Now take a leaf from the box to the farthest right again, and this time add it to the third box and repeat.
Keep doing this process and you'll eventually get:
1, 2, 3, 4, 5,..., 0, 0, 0,...

Here's the thing about this entire process. To start we had m-n empty boxes, and which each iteration we only generated more empty boxes, so therefore more trees with 0 leaves.

Any sequence of distinct numbers you offer me has a tail of at least m-n zeros therefore, and therefore at least two Red Maples with the same number of leaves: zero.

Still, however, due to the lack of information the original problem remains unsolvable without another assumption that wasn't given to you in the problem.