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