If one eats $100$ chocolates in $58$ days,then he must be eating exactly 15 chocolates in some consecutive days

Question

BdMO 2014 Nationals

$X$ eats 100 chocolates in 58 days,eating at least 1 chocolate per day.Prove that,in some consecutive days,she ate exactly 15 chocolates.

I tried using the pigeonhole principle but that is hardly helping.A hint(not the whole solution) will be very much appreciated.

Answer 1

I think 57 or more and at least 100 chocolates is enough to get the conclusion, if there is at least one chocolate eaten per day.

At the end of every day there is some total number of chocolates that has been eaten.
The set of all totals includes $0$ and $100$, and $57$ other distinct integers from $1$ to $99$. In terms of this set, the question is...

...how large a subset of integers between $0$ and $100$ inclusive, including $0$ and $100$, is needed to guarantee a pair exactly $15$ apart?

A maximum 15-free set is the union of $[0,14]$ with $[30,44]$ and $[60,74]$ and $[90,100]$ for a total of $15+15+15+11 = 56$ numbers. This is optimal because it has the maximum number of elements in every arithmetic progression with a spacing of $15$, and all those progressions can be filled independent of each other.

Answer 2

Define $C_i$ as the cumulative number of chocolates eaten by the end of day $i$, with $C_0=0$, over a total of $N$ days. Note that $C_i\ne C_j$ for $i\ne j$.

Then considering these values $\bmod 15$, we have $N{+}1$ values in $15$ residue classes. $11$ of these classes ($\{\overline 0 .. \overline{10}\}$) have $7$ values in range ("long classes"), and $4$ classes ($\{\overline{11} .. \overline{14}\}$) have only $6$ values in range ("short classes"). The long classes can support $4$ values without having two separated by just $15$ (for example, $\overline 3$ can have $\{3,33,63,93\}$) and the short classes can support just $3$ values (for example in $\overline {12}$, you can only choose one from each of the pairs $(12,27),$ $(42,57),$ $(72,87)$).

This means that a maximum of $4\times 11+3\times 4=56$ different values can be supported with having two separated by exactly $15$. Thus when it takes $56$ or more days to eat the $100$ chocolates under the given conditions, there must be a period of successive days when exactly $15$ chocolates are eaten. In particular in this case it is true for a $58$-day period.