# A Problem on Problem-solving skills !!

Problem:

In order to acquire problem-solving skills, a student decides to solve at least one problem per day and at most 11 per week and to do this for a whole year. Show that there exists a period of consecutive days during which he will solve exactly 20 problems.

Proof !

For each $n^{th}$ day of the year, let $a_{n}$ be the total number of solved problems between the first day and the n-th day inclusively. Then, $a_{1}, a_{2}, \ldots$ is a strictly increasing sequence of positive numbers. Consider another sequence $b_{1}, b_{2}, \ldots$ obtained by adding 20 to each element of the preceding sequence, that is, $b_{n}=a_{n}+20$, $n = 1, 2, \ldots$ The $b_{n}$‘s are strictly increasing and are also  all distinct. But, for a period of eight consecutive weeks (one needs to consider at least seven consecutive weeks) during the year, the student cannot solve more than $11 \times 8$, that is, 88 problems. Then, the numbers $a_{n}$ are located between 1 and 88 inclusively, while the $b_{n}$‘s are between 21 and 108 inclusively. Since there are 56 days in eight weeks, the concatenation of the two sequences gives

$a_{1}, a_{2}, \ldots, a_{56}, a_{1}+20, \ldots, a_{56}+20$

which yields a total of 112 distinct integers all located between 1 and 108 inclusively. By the Pigeon hole principle, at least two elements of the concatenated sequence must be equal. One of the two must be in the first half of the sequence and the other in the second part. Let $a_{j}$ and $a_{k}+20$ be these two integers. We then have $a_{k}-a_{j}=20$, which implies that the student must solve exactly 20 problems between the $(j+1)^{th}$ day and the k-th day of the year.

More later.

Nalin Pithwa

# 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 such that $b_{i}+13=b_{j}$, that is, $b_{j}-b_{i}=a_{i+1}+ \ldots + a_{j}=13$ (clearly, then $i. 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