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

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