У пятерых гномов были монеты: у одного было 11 монет, у другого — 22, у третьего — 33, у четвёртого — 44, а у пятого — 55. Сидя за одним столом, эти гномы играли в игру, каждый раунд которой проходил следующим образом. Раз в минуту звучит команда, и по команде все гномы как можно быстрее кладут руку в центр стола. Тот, кто последним положит руку, должен отдать каждый раунд которой проходил следующим образом. Раз в минуту звучит команда, и по команде все гномы как можно быстрее кладут руку в центр стола. Тот, кто последним положит руку, должен отдать каждому из четырёх оставшихся гномов по 1 1 монете. Какое наибольшее количество монет могло оказаться у одного из гномов спустя несколько таких раундов? (В процессе игры не было ситуаций, когда проигравший в каком-то раунде гном не смог «рассчитаться» с остальными.)
Ключевые наблюдения и обозначения. Пусть начальные количества a1=11,a2=22,a3=33,a4=44,a5=55a_1=11,a_2=22,a_3=33,a_4=44,a_5=55a1=11,a2=22,a3=33,a4=44,a5=55. После TTT раундов если гном iii проиграл LiL_iLi раз, то в каждом раунде все получают по +1+1+1, а при каждом проигрыше гном теряет дополнительно 555 (вместо +1+1+1 он получает −4-4−4), поэтому конечное ai=ai(0)+T−5Li.
\text{конечное }a_i = a_i^{(0)} + T - 5L_i. конечноеai=ai(0)+T−5Li.
Кроме того ∑iLi=T\sum_i L_i=T∑iLi=T. Отсюда для гнома kkk, который никогда не проигрывает (Lk=0L_k=0Lk=0), имеем ak=ak(0)+T,
a_k = a_k^{(0)} + T, ak=ak(0)+T,
и возможные TTT удовлетворяют ограничению (для остальных i≠ki\neq ki=k) Li≤⌊ai(0)+T5⌋,T=∑i≠kLi≤∑i≠k⌊ai(0)+T5⌋.
L_i\le \Big\lfloor\frac{a_i^{(0)}+T}{5}\Big\rfloor,\qquad T=\sum_{i\ne k}L_i\le\sum_{i\ne k}\Big\lfloor\frac{a_i^{(0)}+T}{5}\Big\rfloor. Li≤⌊5ai(0)+T⌋,T=i=k∑Li≤i=k∑⌊5ai(0)+T⌋. Для максимизации берём kkk с ak(0)=55a_k^{(0)}=55ak(0)=55. Пусть T=5q+rT=5q+rT=5q+r(0≤r≤4)(0\le r\le4)(0≤r≤4). Тогда для остальных ∑i≠k⌊ai(0)+T5⌋=4q+∑i≠k⌊ci+r5⌋+∑i≠k⌊ai(0)5⌋,
\sum_{i\ne k}\Big\lfloor\frac{a_i^{(0)}+T}{5}\Big\rfloor =4q+\sum_{i\ne k}\Big\lfloor\frac{c_i+r}{5}\Big\rfloor +\sum_{i\ne k}\Big\lfloor\frac{a_i^{(0)}}{5}\Big\rfloor, i=k∑⌊5ai(0)+T⌋=4q+i=k∑⌊5ci+r⌋+i=k∑⌊5ai(0)⌋,
где остатки ci=ai(0) mod 5c_i=a_i^{(0)}\bmod5ci=ai(0)mod5 равны 1,2,3,41,2,3,41,2,3,4, и ∑⌊ai(0)/5⌋=20\sum\lfloor a_i^{(0)}/5\rfloor=20∑⌊ai(0)/5⌋=20. Подсчёт даёт для r=0,1,2,3,4r=0,1,2,3,4r=0,1,2,3,4 суммы соответственно 20,21,22,23,2420,21,22,23,2420,21,22,23,24, отсюда наибольший допустимый qqq равен 202020 для всех rrr. Следовательно максимальное TTT равно 5⋅20+4=1045\cdot20+4=1045⋅20+4=104. Тогда максимальное число у лучшего гнома amax=55+T=55+104=159.
a_{\max}=55+T=55+104=159. amax=55+T=55+104=159. Пример целевого состояния (совместимого по остаткам мод 555 и сумме): (0,1,2,3,159)(0,1,2,3,159)(0,1,2,3,159) — оно достижимо последовательностью допустимых проигрышей (в сумме 104104104 проигрышей у четырёх первых гномов: 23,25,27,2923,25,27,2923,25,27,29 раз соответственно). Значит наибольшее возможное количество монет у одного гнома равно 159159159.
Пусть начальные количества a1=11,a2=22,a3=33,a4=44,a5=55a_1=11,a_2=22,a_3=33,a_4=44,a_5=55a1 =11,a2 =22,a3 =33,a4 =44,a5 =55. После TTT раундов если гном iii проиграл LiL_iLi раз, то в каждом раунде все получают по +1+1+1, а при каждом проигрыше гном теряет дополнительно 555 (вместо +1+1+1 он получает −4-4−4), поэтому
конечное ai=ai(0)+T−5Li. \text{конечное }a_i = a_i^{(0)} + T - 5L_i.
конечное ai =ai(0) +T−5Li . Кроме того ∑iLi=T\sum_i L_i=T∑i Li =T. Отсюда для гнома kkk, который никогда не проигрывает (Lk=0L_k=0Lk =0), имеем
ak=ak(0)+T, a_k = a_k^{(0)} + T,
ak =ak(0) +T, и возможные TTT удовлетворяют ограничению (для остальных i≠ki\neq ki=k)
Li≤⌊ai(0)+T5⌋,T=∑i≠kLi≤∑i≠k⌊ai(0)+T5⌋. L_i\le \Big\lfloor\frac{a_i^{(0)}+T}{5}\Big\rfloor,\qquad
T=\sum_{i\ne k}L_i\le\sum_{i\ne k}\Big\lfloor\frac{a_i^{(0)}+T}{5}\Big\rfloor.
Li ≤⌊5ai(0) +T ⌋,T=i=k∑ Li ≤i=k∑ ⌊5ai(0) +T ⌋.
Для максимизации берём kkk с ak(0)=55a_k^{(0)}=55ak(0) =55. Пусть T=5q+rT=5q+rT=5q+r (0≤r≤4)(0\le r\le4)(0≤r≤4). Тогда для остальных
∑i≠k⌊ai(0)+T5⌋=4q+∑i≠k⌊ci+r5⌋+∑i≠k⌊ai(0)5⌋, \sum_{i\ne k}\Big\lfloor\frac{a_i^{(0)}+T}{5}\Big\rfloor
=4q+\sum_{i\ne k}\Big\lfloor\frac{c_i+r}{5}\Big\rfloor +\sum_{i\ne k}\Big\lfloor\frac{a_i^{(0)}}{5}\Big\rfloor,
i=k∑ ⌊5ai(0) +T ⌋=4q+i=k∑ ⌊5ci +r ⌋+i=k∑ ⌊5ai(0) ⌋, где остатки ci=ai(0) mod 5c_i=a_i^{(0)}\bmod5ci =ai(0) mod5 равны 1,2,3,41,2,3,41,2,3,4, и ∑⌊ai(0)/5⌋=20\sum\lfloor a_i^{(0)}/5\rfloor=20∑⌊ai(0) /5⌋=20. Подсчёт даёт для r=0,1,2,3,4r=0,1,2,3,4r=0,1,2,3,4 суммы соответственно 20,21,22,23,2420,21,22,23,2420,21,22,23,24, отсюда наибольший допустимый qqq равен 202020 для всех rrr. Следовательно максимальное TTT равно 5⋅20+4=1045\cdot20+4=1045⋅20+4=104.
Тогда максимальное число у лучшего гнома
amax=55+T=55+104=159. a_{\max}=55+T=55+104=159.
amax =55+T=55+104=159.
Пример целевого состояния (совместимого по остаткам мод 555 и сумме): (0,1,2,3,159)(0,1,2,3,159)(0,1,2,3,159) — оно достижимо последовательностью допустимых проигрышей (в сумме 104104104 проигрышей у четырёх первых гномов: 23,25,27,2923,25,27,2923,25,27,29 раз соответственно). Значит наибольшее возможное количество монет у одного гнома равно 159159159.