Solving Problems Using the Pigeonhole Principle

[Caldus]

I get the principle itself, but I cannot figure out how to form the 'boxes' and the 'objects' for these problems so that I can try to answer them:

1. Thirty buses are to be used to transport 2000 refugees from Gander to St. John's, Newfoundland. Each bus has 80 seats. Assume one seat per passenger. Prove that one of the buses will carry at least 67 passengers.

2. George has promised to increase his vocabulary by learning the meanings of 90 new words during his summer holidays. Suppose he has 53 days in which to accomplish this task and will learn at least one new word a day. Show that during some span of consecutive days, George will learn precisely 15 new words.

Pointing me in the right direction with either of these will be greatly appreciated.

 

[Janitor]

It has been so long since I have read anything on the pigeonhole principle that I probably will not be able to guide you in deriving an answer in the way the instructor wants you to.

If I just wing it, I would say this:

Suppose all buses carried the same amount of people. Then each bus would carry 2000/30=66.66 people. Since the bus driver would get into legal trouble for showing up at the destination with a fractional refugee, the realistic solution in which the busloads are as equitable as possible is 67 people on some buses and 66 people on some buses. Shifting people out of any of the buses carrying either 66 or 67 people will either leave 67 as the maximum number on any bus, or else increase the maximum number on any bus to 68, or to 69, or to 70...

But maybe you have already gotten this far, and the point is to formalize the reasoning to a greater degree than I have been able to.

 

[matt grime]

This is pure maths, so it isn't the pigeon hole principle "result" that is important so much as its "proof"

so suppose that on none of the buses there is more than 66 people, then there are at most 66*80 < 2000 people,

(you can consider this the extended pigeon hole principle)

the second one is puzzling me

first he learns at least one of the 90 on each day, thus leaving 37 to distribute amongst the 53 days, we must show that no matter how that is done then there is a set of consecutive days where he learns 15 words... can't quite get it yet..

 

[cookiemonster]

All the second one says is that there is at least 1 day where there is only a single word learnt, no?

cookiemonster

 

[matt grime]

It says more than that - a smaller example, 5 words 3 days must be distributed in one eof the following words per day:

3,1,1 or 1,3,1 or 1,1,3 or 1,2,2 0r 2,1,2 or 2,2,1

in each case there is some day or consecutive days where exactly three words are learnt.

it also states that there are at least 53 -37 = 16 days with exactly one word learned in the original question.

i just can't see a better way of doing it than case by case at the moment

 

[Caldus]

OK, I think I have a little bit of an idea for the second one (thanks a lot for pointing me in the right direction with the first one):

Suppose that the objects are how many words he learns on a given day:

An = Number of new words learned on day n.

So:

A1 = A1
A2 = A1 + A2
An = A1 + A2 ... + An

And the boxes consist of equivalence classes 1, 2, 3, ... 14 (since 15 would be congruent mod 1 in this case).
This means that 2 sums must be congruent mod 14 and the difference must be divisible by 14.
Let these two sums be:
A1 + A2 ... + Ak
A1 + A2 ... + Ak + Al (k and l are integers)
The difference of these two sums is:
Ak+1 + Ak+2 + ... + Al

I think I am way off with the actual proof, but I think I have good idea of what to do now. I just can't quite figure it out. Any help appreciated.

 

[matt grime]

the second equality you write implies A2=0

don't confuse the number learned on day n, An, with those learned by day n, call it Bn:
Bn=A1+...+An

 

[sunilkamadolli]

i think this is discrete mathematicz...anywayz, I am not sure if I am rite...
you draw two ovals...one with 1 to 90 holes in it and the other with 53 holes in it...according to the pigeon hole principle, the 53 holes[days] will point to the other 53 holes [words]. leaving us with 90-53=37 words.

the question iz "Show that during some span of consecutive days, George will learn precisely 15 new words." now, for the 37 which is left, we can just distribute them into the first 37 days leaving us with 2 words for the 1st 37 days...we can say 15 words were learned from day 31 to 38 [7*2 + 1 = 15]

lets try the other possiblilty...we will try to place them as far away from each other...thus, we will start filling the 53 holes with 37 words by separating each word by 1 days...so day 1 has 2 words, day 2 has 1 word and day 3 has 2 words, day 4 has 1 word etc etc...we can notice that this way only 27 words get filled till the 53rd day...now we just have 37-27=10 words to will into the 53holes. now no matter where we place those 10 words we will have the sequence of 2 s and a 1 in the border of the sequence...so therez 2*7 + 1=15 words learned in conseq days...

Im not sure if this is right...did this really fast...my answer does not seem like a mathematical proof...ill be glad to see few more ways of doing this.

 

[matt grime]

There are another 53^37 - 2 possibilities to consider, sunilkamadolli. Good luck. (Ok it's not that many really, but it's close enough as to still be impossible)

 

[Caldus]

OK, trying this again:

Suppose that the statement is false. In other words, suppose that George did not learn exactly 15 new words within a number of consecutive days. Let Wj be the number of words learned on day j where 0 <= j <= 42. Let Tj be the total number of words learned by day j where 0 <= j <= 42. So:

Objects:
T1 = W1
T2 = W1 + W2
Tn = W1 + W2 + ... + Wn

The "boxes" in this case would be the equivalence classes 0, 1, 2, ... , 14. This means that 2 sums must be congruent mod 14 and the difference of these two sums must be divisible by 14. Let these two sums be:

W1 + W2 + ... + Wk
W1 + W2 + ... + Wk + Wl (k and l are integers)

The difference of these two sums would be:

Wk+1 + Wk+2 + ... + Wl

If this statement were false, then there would be no two sums which were congruent mod 14 and the difference of these two sums would never be divisible by 14. One counterexample of this is that at some point George will have to know more than one word, so suppose that:

W1 = 1
W2 = 1
...
W13 = 1
W14 = 2

In this case George will have learned 15 new words in 14 days. So the statement is true.

Any better? Still needs a lot of work I bet...

 

[matt grime]

Wht are we now using 42 and not 53 days? There mus be ar least 4 differences which are zero mod 14. I don't understand what you are doing when you say: if this statement were false. which statement? and why is one counterexample sufficient? I think you may have found a good anlge here, but don't hold me to that.