Представьте, что у вас есть три ящика с яблоками. В первом ящике лежит 8 яблок, во втором – 5 яблок, в третьем – 3 яблока. Яблоки можно перекладывать между двумя ящиками в любом порядке, но особым образом: на первом ходу можно переложить 1 яблоко, на втором – 2 яблока, на третьем – 3 яблока, и так далее. При этом все яблоки, взятые из одного ящика, можно положить только в другой ящик, порцию яблок запрещено дробить между несколькими ящиками.
За какое минимальное количество ходов можно переложить все яблоки в один ящик?
Ответ, как обычно, вы найдёте ниже.
↓
↓
↓
Итак, с каждым ходом количество перекладываемых яблок у нас увеличивается на одно. При этом нетрудно прикинуть ограничение на минимальное количество перекладываний (ходов). Всего в ящиках 16 яблок, причём выгоднее всего переложить яблоки из второго и третьего ящиков в первый, то есть – переместить 8 яблок. Очевидно, что ходов будет больше, чем три, ведь за первый ход мы переместим 1 яблоко, за второй – 2, а за третий – 3, в сумме – 6 яблок. Соответственно, придётся сделать не менее четырёх ходов, так как в этом случае мы можем переместить 10 яблок, чего более чем достаточно.
Немного поразмышляв и попробовав разные схемы, вы придёте к такому алгоритму:
Таким образом, переложить все яблоки в один ящик можно всего за четыре хода. А максимальное количество ходов не может быть больше 15, так как яблок всего 16, причём последним ходом можно переложить 15 яблок в коробку с 1 яблоком, достигнув нужно результата. Одним из алгоритмов решения может быть следующий:
Как видите, после четвёртого хода третий ящик перестаёт участвовать в перемещении яблок, так как все действия происходят только между двумя первыми ящиками. Но это и понятно, ведь на каждом ходу количество перемещаемых яблок возрастает, и нужно иметь запас, а при разбивке яблок на три ящика этого запаса не будет.
Такая вот незамысловатая задачка, от которой потом хочется не математических яблок, а самых настоящих.