У пятерых гномов были монеты: у одного было 11 монет, у другого — 22, у третьего — 33, у четвёртого — 44, а у пятого — 55. Сидя за одним столом, эти гномы играли в игру, каждый раунд которой проходил следующим образом. Раз в минуту звучит команда, и по команде все гномы как можно быстрее кладут руку в центр стола. Тот, кто последним положит руку, должен отдать каждый раунд которой проходил следующим образом. Раз в минуту звучит команда, и по команде все гномы как можно быстрее кладут руку в центр стола. Тот, кто последним положит руку, должен отдать каждому из четырёх оставшихся гномов по 1 1 монете. Какое наибольшее количество монет могло оказаться у одного из гномов спустя несколько таких раундов? (В процессе игры не было ситуаций, когда проигравший в каком-то раунде гном не смог «рассчитаться» с остальными.)

26 Окт в 19:40
17 +17
0
Ответы
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-44), поэтому
конечное ai=ai(0)+T−5Li. \text{конечное }a_i = a_i^{(0)} + T - 5L_i.
конечное ai =ai(0) +T5Li .
Кроме того ∑iLi=T\sum_i L_i=Ti 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)(0r4). Тогда для остальных
∑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=20ai(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=104520+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.
26 Окт в 20:02
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир