A forum devoted to the free exchange of thoughts and ideas in a civil manner, free from taboos, intimidation, or censorship.
 
HomeCalendarFAQSearchMemberlistUsergroupsRegisterLog in

Share | 
 

 An Interesting Problem for Tree Huggers

Go down 
AuthorMessage
TheSleepingDragon

avatar

Posts : 65
Join date : 2010-06-26

PostSubject: An Interesting Problem for Tree Huggers   6/27/2010, 01:04

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.
Back to top Go down
View user profile
TheSleepingDragon

avatar

Posts : 65
Join date : 2010-06-26

PostSubject: Re: An Interesting Problem for Tree Huggers   6/27/2010, 01:16

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?


Last edited by TheSleepingDragon on 6/27/2010, 01:22; edited 1 time in total (Reason for editing : Severe editing issues)
Back to top Go down
View user profile
Kenny Ruff



Posts : 15
Join date : 2010-06-28

PostSubject: Confused...of course   6/28/2010, 03:08

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.
Back to top Go down
View user profile
TheSleepingDragon

avatar

Posts : 65
Join date : 2010-06-26

PostSubject: Re: An Interesting Problem for Tree Huggers   6/28/2010, 04:21

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.
Back to top Go down
View user profile
Sponsored content




PostSubject: Re: An Interesting Problem for Tree Huggers   

Back to top Go down
 
An Interesting Problem for Tree Huggers
Back to top 
Page 1 of 1
 Similar topics
-
» Tree Grounding
» REPOST - Green Fruit Tree Dream
» Big Lush Tree
» Dream of a Large Tree amongst a hedge - Dream of trying to take a shower and no privacy
» Silverfish problem....

Permissions in this forum:You cannot reply to topics in this forum
Socrates Revival :: Puzzles :: Math Puzzles-
Jump to: