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