Competition problem — Combinatorics

Combinatorics Difficulty 6.6 National Olympiad Prove it Italy

Normally Davide needs to sleep at least 8 hours per night. If on one night he sleeps $k$ hours less than he needs, he finds himself needing $k$ hours more sleep for the following $k$ nights. Every night he sleeps in any case an integer number of hours less than or equal to his requirement. For example, if on Monday night he needs 8 hours, but sleeps only 7, on Tuesday he will need 9 hours. If on Wednesday he needs 8 hours, but sleeps only 6, on Thursday and Friday he will need at least 10 hours of sleep; if on Thursday he sleeps only 9, on Friday he will feel the need for 11 hours ( $8$ , plus 2 for the hours lost on Wednesday, plus 1 for the one not slept on Thursday).
On a certain Monday night Davide would need to sleep 8 hours; the same occurs on the Monday night of the following week. During the course of the week there were 7 hours in which he would have needed to sleep but did not: what is the minimum number of hours Davide slept in the seven nights from Monday to Sunday?

Solution

Solution:

Davide slept a minimum of 58 hours.

Let us number the days of the week from 1 to 7 and suppose that Davide sleeps $k_{1}$ hours less than his requirement on Monday, $k_{2}$ hours on Tuesday, ..., $k_{7}$ hours on Sunday. We know that $k_{1} + \cdots + k_{7} = 7$ .

Since after a week has passed Davide would need to sleep the same number of hours as on the previous Monday, the hours added to his requirement due to the various sleep deficits must all fall within the week; in particular, the sum of the values of his requirement for each of the seven nights can be calculated as $7 \cdot 8 + k_{1}^{2} + k_{2}^{2} + \ldots + k_{7}^{2}$ . Moreover it must be that $k_{7} = 0$ , otherwise Davide would need to sleep more than 8 hours the following Monday.

Davide therefore sleeps $56 + k_{1}^{2} + \cdots + k_{6}^{2} - k_{1} - \cdots - k_{7} = 49 + k_{1}^{2} + \ldots + k_{6}^{2}$ hours during the course of the week.

Certainly, in order for $k_{1} + \cdots + k_{7} = 7$ and for $k_{7}$ to be 0, there must be a day $i$ (with $i$ different from 7) on which Davide sleeps at least 2 hours less than needed $\left(k_{i} \geq 2\right)$ . Note that setting, for example, $k_{1} = 2$ and $k_{2} = \cdots = k_{6} = 1$ gives a total of $49 + 2^{2} + 1 + 1 + 1 + 1 + 1 = 58$ hours over the course of the week.

We show that it is not possible for Davide to sleep less than 58 hours: if there is a day $j$ for which $k_{j} \geq 3$ , Davide will sleep strictly more than $49 + 3^{2} = 58$ hours; we may therefore assume that for $i = 1, \ldots, 7$ , $k_{i} \leq 2$ . If Davide had a deficit of 2 hours more than once during the course of the week, again he would have to sleep more than $49 + 2^{2} + 2^{2} + 1 = 58$ hours.

Thus the configuration in which he has a single deficit of 2 hours and 5 deficits of one hour is indeed minimal.

We have thus shown that on one hand Davide cannot sleep fewer than 58 hours, and on the other hand a configuration like the one described (for example: 6 hours of sleep on Monday, 9 on Tuesday, 10 on Wednesday, 8 from Thursday to Saturday and 9 on Sunday) accounts for exactly 58.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.