Условие
В
n стаканах достаточно большой вместительности налито поровну воды.
Разрешается переливать из любого стакана в любой другой столько воды, сколько
имеется в этом последнем. При каких
n можно в конечное число шагов слить воду
в один стакан?
Решение
Ответ: при
n=2
k ,
k – целое.
Если
n является степенью двойки, то алгоритм переливания легко строится по индукции.
Докажим, что при остальных
n перелить всю воду в один стакан нельзя.
Предположим, что нам удалось перелить всю воду в один стакан.
Примем за единицу измерения объема начальный объем воды в каждом стакане.
Тогда после любого числа переливаний объем воды в любом стакане будет
выражаться целым числом. Обратим наш процесс. Тогда в начальный момент у нас есть
n единиц объема воды в одном стакане,
а в конечный момент – но одной единице в каждом стакане. Одна операция
заключается в переливании из одного стакана половины имеющейся в нем воды
в любой из остальных стаканов.
Пусть
p - любой простой нечетный делитель числа
n .
В начальный момент количество воды в каждом стакане делится на
p ,
в процессе переливаний это свойство сохраняется. Значит, в конечный
момент количество воды в каждом стакане должно делиться на
p , то есть
1
делится на
p – противоречие.
Ответ
При
n=2
k ,
k – целое.
Источники и прецеденты использования
