IIT JEE , AIEEE Forum - Articles Category , Community shelf

kiran

The Pigeon Hole Principle

The Principle:

Let there be 'n' pigeon holes and 'n+1' pigeons. Then atleast one hole contains more than 1 pigeons.

example:

Suppose a musical group has 11 weeks to prepare for opening night, and they intend to have at least one rehearsal each day. However, they decide not to schedule more than 12 rehearsals
in any 7-day period, to keep from getting burned out. Prove that there exists a sequence of successive days during which the band has exactly 21 rehearsals. This problem can be
solved by a double application of the pigeonhole principle. First, since the band has no more than 12 rehearsals per week, they can't have more than 132 rehearsals in 11 weeks. (To see this, let x_k denote the number of games played in each of the 11 consecutive weeks, and note that they cannot sum to greater than 132 if they are each no greater than 12.) Now let x_n denote the total number of rehearsals that have been held after n days. Since the band rehearses at least once per day, we have 1 <= x_1 < x_2 < x_3 < ... < x_77 <= 132 Also, we can add 21 to each of these numbers to give the sequence (x_1 + 21) < (x_2 + 21) < ... < (x_77 + 21) <= 153 There are 77 numbers x_n and 77 more numbers x_n + 21 for a total of 154 numbers, all in the range from 1 to 153. Thus, at least two of these 154 numbers must be equal. But the x_n are all distinct, as are the (x_n + 21), so any "overlap" must be between a number of the form x_n and one of the form (x_m + 21), which implies x_n = x_m + 21 This proves that there are indices m,n such that exactly 21 rehearsals were held during the sequence of consecutive days from day n+1 to day m.

Cheers!

Ask & Discuss Questions with Community & Experts

The Pigeon Hole Principle