Maths Olympiad Prep

Library / /626 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

There are 2017 jars in a row on a table, initially empty. Each day, a nice man picks ten consecutive jars and deposits one coin in each of the ten jars. Later, Kelvin the Frog comes back to see that NN of the jars all contain the same positive integer number of coins (i.e. there is an integer d>0d>0 such that NN of the jars have exactly dd coins). What is the maximum possible value of NN?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Label the jars 1,2,,20171,2, \ldots, 2017. I claim that the answer is 2014. To show this, we need both a construction and an upper bound. For the construction, for 1i2011 \leq i \leq 201, put a coin in the jars 10i+1,10i+2,,10i+1010 i+1,10 i+2, \ldots, 10 i+10. After this, each of the jars 1,2,,20101,2, \ldots, 2010 has exactly one coin. Now, put a coin in each of the jars 2008,2009,,20172008,2009, \ldots, 2017. Now, the jars 1,2,,2007,2011,2012,,20171,2, \ldots, 2007,2011,2012, \ldots, 2017 all have exactly one coin. This gives a construction for N=2014N=2014 (where d=1d=1). Now, we show that this is optimal. Let c1,c2,,c2017c_{1}, c_{2}, \ldots, c_{2017} denote the number of coins in each of the jars. For 1j101 \leq j \leq 10, define sj=cj+cj+10+cj+20+s_{j}=c_{j}+c_{j+10}+c_{j+20}+\ldots Note that throughout the process, s1=s2==sjs_{1}=s_{2}=\cdots=s_{j}. It is also easy to check that the sums s1,s2,,s7s_{1}, s_{2}, \ldots, s_{7} each involve 202 jars, while the sums s8,s9,s10s_{8}, s_{9}, s_{10} each involve 201 jars. Call a jar good if it has exactly dd coins. If there are at least 2015 good jars, then one can check that it is forced that at least one of s1,s2,,s7s_{1}, s_{2}, \ldots, s_{7} only involves good jars, and similarly, at least one of s8,s9,s10s_{8}, s_{9}, s_{10} only involves good jars. But this would mean that 202d=201d202 d=201 d as all sis_{i} are equal, contradiction.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.