Задача 7.
На столе лежит 4 стопки монет. В первой стопке 9 монет, во второй — 7, в третьей — 5, в четвёртой — 10. За один ход разрешается добавить по одной монете к трём разным стопкам. За какое наименьшее количество ходов можно добиться того, чтобы во всех стопках стало поровну монет?
Ответ на Задачу 7.
Ответ: 11 ходов.
Решение:
Предположим, было сделано 𝑁 ходов, после которых во всех стопках стало поровну монет.
Немного изменим правила. Пусть первоначально в стопках лежало не 9, 7, 5 и 10 монет, а 𝑁 + 9, 𝑁 + 7, 𝑁 + 5 и 𝑁 + 10 соответственно; а ходы выполним следующим образом: вместо добавления по одной монете в три стопки, будем забирать одну монету из стопки (той, в которую во время оригинального хода мы не добавляли монету). Заметим, что итоговый результат от этого не изменится! (Фактически, вместо добавления монет в три стопки мы добавляем их во все четыре, а потом одну забираем.)
В рамках новых правил ответить на вопрос гораздо проще. За один ход мы забираем одну монету из любой стопки, и наша цель — как можно быстрее сделать так, чтобы монет во всех стопках стало поровну. Легко понять, что для этого надо везде оставлять по 𝑁 + 5 монет. Для этого из первой стопки нужно забрать 4 монеты, из второй — 2, из третьей — 0, из четвёртой — 5. Итого надо совершить 4 + 2 + 0 + 5 = 11 ходов.