Pigeon hole principle — an example for RMO preparation

Problem:

A student has 6 weeks (that is, 42 days) to prepare for her examination and she has decided that during this period she will put in a total of 70 hours towards her preparation for the examination. She decides to study in full hours every day, studying at least one hour each day. We have to prove that no matter how she schedules her studying pattern, she will study for exactly 13 hours during some consecutive days.

Solution:

If a_{i} denotes the number of hours she studies on the ith day, then we are given that each a_{i} is a positive integer and the sum a_{1}+a_{2}+ \ldots + a_{42}=70. To get the required succession of days, we must find some m and j such that m \leq j and a_{m}+ \ldots + a_{j}=13. Trying out all the possibilities, is close to impossible as well as dumb. Let b_{i} denote the partial sum a_{1}+ \ldots + a_{i} which is the number of hours she studies upto the ith day. Our given data then translates into

1 \leq b_{1} < b_{2} < \ldots < b_{41} < b_{42}=70

and we have to find some i<j such that b_{i}+13=b_{j}, that is, b_{j}-b_{i}=a_{i+1}+ \ldots + a_{j}=13 (clearly, then i<j). Hence, besides the 42 numbers in

B= \{ b_{1}, b_{2}, \ldots , b_{42}\} we also look at 42 more numbers in B^{'}= \{ b_{1}+13, b_{2}+13, \ldots, b_{42}+13\} which are also 42 different numbers and the largest among them is b_{42}+13=70+13=83. Hence, the 2 \times 42 are actually among the positive integers from 1 to 83 and hence, by the pigeonhole principle, we see that two numbers in B \bigcup B^{'} must be equal. As we already saw the numbers in B are all distinct and so are the numbers in B^{'}. Hence, we must have for some i and j, b_{i}=b_{j}+13 giving the required succession of days when she studied exactly for 13 hours a day.

More on pigeonhole principle,

Later,

Till then,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s