Задача с монетами
На столе лежит 4 стопки монет. В первой стопке 9 монет, во второй-7, в третьей-5, в четвертой-10. За один ход разрешается добавить по одной монете к трем разным стопкам. За какое наименьшее количество ходов можно добиться того, чтобы во всех стопках стало поровну монет?
Ответ 11. Строим пример:
00. 9 7 5 10
01. 10 8 6 10
02. 11 9 7 10
03. 11 10 8 11
04. 12 11 9 11
05. 12 12 10 12
06. 13 13 11 12
07. 13 14 12 13
08. 14 14 13 14
09. 15 15 14 14
10. 15 16 15 15
11. 16 16 16 16
Теперь докажем, что меньше 11 быть не может.
Исходное количество монет = 31, значит у нас может быть 3, 7, 11 и т.д. добавлений, чтобы сумма монет была кратна 4.
Покажем, что за менее 9 добавлений это невозможно.
Для этого рассмотрим стопки, которые начинались с 9, 5 и 10.
Во всех стопках в конце одинаковое число монет (скажем, x). Если есть шаг, одновременно увеличивающий стопку 9 и стопку 10, то разрыв между стопкой 5 и полусуммой этих стопок не уменьшается, а он должен быть равен 0, поэтому оптимально увеличивать либо стопку 9, либо стопку 10.
Предположим, что после какого-то шага мы увеличили стопку 5 суммарно на t, тогда пользуясь предыдущим, можно утверждать, что 9 и 10 увеличились также на t (случай, когда они увеличились больше можно не рассматривать)
Получаем систему:
9 + 10 + t = 2x
5 + t = x
Откуда x = 14, а t = 9.
Таким образом, количество шагов не может быть меньше 9. Следующее возможное количество - 11, и для него построен пример.