Track / Stage 5 / 394 of 400 #994 of 2000

Problem 994

AIME late

Combinatorics Difficulty 6.0 Prove it

42. Schoolboy solves problems throughout the year; every day - at least one problem. Each week, to avoid overworking, he solves no more than 12 problems. Prove that there will be several consecutive days during which he will solve exactly 20 problems.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

42. Suppose that on the first day, the student solved $a_{1}$ problems, in the first two days $a_{2}$ problems, and in the first 77 days (11 weeks) $a_{77}$ problems.

Consider the numbers

$\begin{array}{ll} a_{1}, & a_{2}, \ldots, \quad a_{77} \\ a_{1}+20, & a_{2}+20, \ldots a_{77}+20 \end{array}$

There are 154 numbers in total. Note that $a_{77}$ is no more than $12 \cdot 11=132$ . Therefore, all the listed numbers do not exceed $132+20=152$ , and thus there are two equal numbers among them. However, all the numbers in the first row are distinct, and therefore the numbers in the second row are also distinct. Consequently, there exist such numbers $l$ and $k, l<k \leqslant 77$ , that

$a_{k}=a_{l}+20 \text { or } a_{k}-a_{l}=20$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.