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