Question

Question: Linda has 5 weeks to prepare for her CSCA67 final. Her friend has volunteered to help her for either 15min or 30min every day until the test but not for more than 15 hours total. Show that during some period of consecutive days, Linda and her help will study for exactly 8 3/4 hours.

Answer: We can solve this by letting ai represent the number of quarter hours Linda studies on day i. Then there are 5x7 = 35 days that Linda studies. Now we define 35 sums: s1 = a1, s2 = a1 +a2, s3 = a1 +a2 +a3. Then if one of these sums equals 8 ∗ 4+3 = 35 quarter hours, we are done. If not, then there are 35 sums (pigeons) and we set our holes to be the possible remainders for each sum when divided by 35, we have the values from 1..34 or 34 holes. Therefore there are two pigeons in one hole, ie, two sums that when divided by 35 have the same remainder. If we subtract the smaller sum from the larger we get a continuous subset of days (by the way we designed the si and this difference must be divisible by 35. Since no sum is larger than 60 and the difference is a multiple of 35, this multiple cannot be larger than 1. Therefore we have a set of consecutive days totally 8 3 4 hours.

My question: Can someone help me to under stand and solve this question in proper way by using php. I dont understand how answer says, "35 sums (pigeons) and we set our holes to be the possible remainders for each sum when divided by 35, we have the values from 1..34 or 34 holes"

Answer 1

Pigeon Hole Principle: If there are n+1 pigeons that are to be assigned in n pigeonholes, then at least two pigeons are assigned to the same hole.

In the answer to the problem, _{​​​​​​}a_i is defined to be the number of quarter hours(that is the number of sets of 15 minutes) that Linda studies on the i^th day, for i=1,2,3,...35.

Observe that since her friend has volunteered to help her for either 15 or 30 minutes every day, hence, a_i is either 1 or 2 for every i=1,2,3,...35.

Now, the answer defines the sums:

s₁ = a₁

s₂ = a₁ + a₂

s₃ = a₁ + a₂ + a₃

........

s₃₅ = a₁ + a₂ + a₃ +.....+ a₃₅

Observe that since the friend will not help for more than 15 hours in total, hence s_i (15 * 4)=60 quarters.

Now, if there is an i in {1,2,...35} such that s_i = 35 quarters, then there for the i consecutive days 1,2,3,...i , Linda studies 35/4 = 8+3/4 hours in total and hence we are done.

So, suppose that s_i 35 for all i=1,2,3,4,...35. Since each s_i is less than equal to 60, hence 35 does not divide any of the s_i (as the next higher multiple of 35 after itself is 70). As a result, the remainder r_i obtained when s_i is divided by 35 is in the set {1,2,3,...34} (and not 0) for each i=1,2,3,...35.

Consider the 35 s_i(or the 35 remainders r_i) as 35 pigeons and the 34 possible remainder values as 34 pigeonholes. By the pigeonhole principle, there are at least two sums s_i and s_j that leave the same remainder values (or at least two remainders r_i and r_j that have the same value). Assume without loss of generality that s_i < s_j. Then, 35 | (s_j - s_i) (as r_i=r_j).

Since s₁,s₂,....s₃₅ are each less than or equal to 60, hence so is the difference s_j - s_i. Now, s_j - s_i = a_i+1 + a_i+2 + .... + a_j >0.

Also, the only multiple s_j - s_i of 35 strictly between 0 and 60 is 35. Hence, a_i+1 + a_i+2 + ..... + a_j = s_j - s_i = 35.

Thus, for the period i+1, i+2, i+3,......j of consecutive days, Linda and her friend will study for exactly 35 quarters = 35/4 hours = 8+3/4 hours.