Combinatorics - Pigeonhole Principle

[mattmns]

I have two Pigeon Hole Principle questions that I am having trouble with.

First Question: In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of whose ages is the same.
-------

So I let $a_i$ = age of person i, i = 1,2,...,10.

Thus $1 \leq a_i \leq 60$ for i = 1,2,...,10

we can also assume that $a_i \neq a_j \forall i \neq j$ since if there were two (or more) that were equal then we would be done.

The book has the following hint: The number of sums that can be formed with 10 numbers is $2^{10} - 1$. No sum can exceed 600

Now I understand how they got these hints. For the first, you can use the idea of a Powerset, and the number of elements in P(S) = 2^n (2^n - 1 if you subtract the empty set, n is the number of elements in S). And 600 is obvious since 60x10 = 600 the max (though we could do more to show that the sum is actually lower; it is easy to show that the sum cannot exceed 555 (and it is even lower than that) and also that the sum must exceed 55, (and is even higher than that)).

However, I am not sure of how to use the first hint. There is obvious overcounting, and also we are interested in two groups (or subsets if we want to stick with that idea) whose sums are equal. The 2^n - 1 includes the sum of all 10, which should not be in there, it also includes things that repeat, like a1+a2 = a1, a1+a2+a3 = a1+a2, etc. Do I need to then count these things (and then subtract them from 2^10 - 1), and if so what would be an efficient way (I can think of the brute force way, but I would not want to have to do that )? Any ideas?
-------------------
Second Question: Use the pigeonhole principle to prove that the decimal expansion of a rationl number m/n eventually is repeating.
------

Now I am guessing they are also including decimal expansions that terminate (for example 3/4 = .75)

Let us again look at the book's hint: What are the possible remainders when an integer is divided by n?

The answer to this question is: 1, 2, 3, ..., n-1

So we have n-1 possible remainders, but I don't yet see what we can do with this.

So how about the following question: If I have m/n, how do I get the decimal expansion of this number? (I am guessing we will keep on dividing somewhere and that is where the remainders will come into play, but I don't know how to get a decimal expansion.) Any help would be appreciated, thanks!

 

[StatusX]

For the first one, I'm not sure what you mean by "it also includes things that repeat, like a1+a2 = a1, a1+a2+a3 = a1+a2, etc." All you need to do is find two subsets which have the same sum. Since there are more subsets than possible sums, this is where the pigeonhole principle comes in. And the requirement that the subsets have no members in common shouldn't be too hard to accommodate if you give it a moment of thought.

For the second, you get the decimal expansion of a rational number using long division. The key point is to notice what happens when some remainder comes up a second time. Actually, I don't think this proof uses the pigeonhole principle, so maybe they're looking for something else.

 

[mattmns]

Thanks for the response(s).

For the first, I meant that the number 2^n - 1 includes too much, but I was wrong (I was thinking wrong about what the count was representing), though I think the number should be 2^n - 2, to remove adding all n numbers together. So now the pigeonhole principle clearly applies and the problem is easily solved. The issue of common members is obvious, unless I am mistaken; if we have the same member in two sets, just remove it from both and the sums are still equal, repeat if there are more than 1 common member in each set.

For the second, I will look into the decimal expansion by long division, and see where that goes. Thanks!

 

[mattmns]

Wait, I am not so sure about the first anymore, but I still think the number is greater than 2^n - 2, so it would not be an issue.

Consider n = 4. {a1, a2, a3, a4}
We have the following possibilities.
a1 = a2, a1 = a3, a1 = a4, a1 = a2+a3, a1 = a2+a4, a1 = a3+a4, a1 = a2+a3+a4
a2 = a3, a2 = a4, a2 = a1+a3, a2 = a1+a4, a2 = a3+a4, a2 = a1+a3+a4
a3 = a4, a3 = a1+a2, a3 = a1+a4, a3 = a2+a4, a3 = a1+a2+a4
a4 = a1+a2, a4 = a1+a3, a4 = a2+a3, a4 = a1+a2+a3

Here there are actually 21 ways, not 2^4 - 1 = 15 (or 14 if you subtract 2).

 

[StatusX]

2^10-1 refers to the number of (non-empty) subsets of the ten people. Each of these subsets corresponds to some number between 1 and 600 via taking the sum of the ages of the people in the subset, and since there are more subsets than possible sums (more pigeons than holes), the pigeonhole principle states that some two subsets must have the same sum (you need to put two pigeons in the same hole).

 

[neurocomp2003]

The question you need to ask is how many paired groups can you make from 10 people(note two things: you listed one restriction from the first post, the second thing is that you need to ask whether the size sum of the two groups need always be 10).

StatusX: you are forgetting one of the criterias above.

 

[mattmns]

Ahh, I feel better now, thanks for the clarification!

 

[neurocomp2003]

For the 2nd question...find out what happens to the rationals
i/n, i=0-n-1.

 

[durt]

You have a set $$S_n$$of $$n$$ elements. Let $$A_n$$ be the set of all possible combinations (groups to be summed) of the elements of $$S_n$$. Let $$z_n$$ be the number of elements in $$A_n$$.

Now suppose you have a new set $$S_{n+1}$$ that consists of $$S_n$$ and a new element $$s_{n+1}$$. $$z_{n+1}$$ is the number of elements in $$A_{n+1}$$.

The elements of $$A_{n+1}$$ are the elements of $$A_n$$, $$a_{n+1}$$ plus each element of $$A_n$$, and $$a_{n+1}$$ itself. So $$z_{n+1}=2 z_n +1$$. From this, you can prove by induction that the number of combinations formed from the elements of $$S_n$$ is $$z_n=2^n-1$$.

You don't have to worry about whether anything repeats. This is the total number of groups of people. If each group had a distinct age sum, then the total number of possible age sums would have to be at least $$z_n$$. You know that the age sums can vary from 10 to 600, which is 591 total. Now show how the pigeon-hole principle applies. Since 591 < 1023, you don't need to go reducing the number of possible age sums by saying, "600 doesn't work, so the new total is 590, etc." The moral of this problem is: don't go making problems too complicated before trying simple methods. (Thanks to the hint, this was a pretty simple problem).

 

[neurocomp2003]

however you are not comparing 591 or 600 to 1023...

 

[0rthodontist]

StatusX: you are forgetting one of the criterias above.

No he's not--if you have any two unrestricted (different) sets of people with the same sum, you can delete the shared people and the sums will still be equal.

 

[neurocomp2003]

Orthodontist: but it then becomes whether, the two groups must union to all 10 people or not. If both groups union to 10 people then you do have to take the restriction into consideration...if not say two groups totalling 9 people...then statusX method would suffice.

 

[0rthodontist]

If the two groups must comprise all the people, the statement isn't true. In order for the sums to be equal in that case, if S is the sum of all 10 people, then if n is the sum of a subset of people satisfying the condition, you must have n = S - n, or n = S/2. This is only possible if S is even. The list of ages 1, 1, 1, 1, 1, 1, 1, 1, 1, 2 is a counterexample.

 

[neurocomp2003]

yeah i realized that...my bad.