[Ответ на вопрос читателя Б. Ивякина о решении задачи М115]

58

Спрашивайте — ответаем

В редакцию пришло письмо от десятиклассника Б. Ивачина. В нем он пишет:

«Просматривая старые номера «Кванта», я обращил внимание на приписку в конце решения задачи M115 «… эта задача впервые возникла в одной из работ известного современного алgebraиста А. И. Ширшова. Она понадобилась ему для построения серверной математической теории. Интеграно узнать, как она там решения? Использована ли для этого вычисляя математика, или решение воле элемента? Ведь если оно элементарно, мои циклы могут быть записаны воле серверными математическими исследованиями».

Мы попросили ответить на эти вопросы члена-корреспондента АН СССР А. И. Ширшова.

Дорогой Боря!

Не так уж обязательно просматривать старые номера «Кванта», чтобы наткнуться на интересные математические идеи. Они вокруг нас.

Вас занитересовала задача M115. Напомню ее условия:

ВMRI сосуда налимо по целому числу литров воды. В любой сосуд разрезается перелить столько воды, сколько в нем уже содержится, из любого другого сосуда. Доказать, что несколько максими переливаются можно освободить один из сосудов. (Сосуды достаточно велики: какый может вместе всю воду).

Я в свое время нашел излагаемое ниже решение.

Пусть $(n, p, q)$ — некоторое начальное состояние сосудов, а $\gamma$ — такое наиболее натуральное число, что по крайней мере одно из чисел $n+p$, $n+q$, $p+q$ делится на $2^\gamma$. Очевидно, что $\gamma > 0$. Пусть $n+p=2^\gamma (2s+1)$, $n=2^\alpha (2t+1)$, $p=2^\beta (2r+1)$. Предположим, что $\alpha=\beta$. Тогда $\alpha<\gamma$. Если $n>p$, то сделаем переливание $(n, p, q) \Leftrightarrow (n-p, 2p, q)$; если же $n<p$, то переливание $(n, p, q) \Leftrightarrow (2n, p-n, q)$. Поскольку $n-p=2^{\alpha+1}(t-r)$ и $2p=2^{\alpha+1}(2r+1)$, на каком-то шаге показали при двойках станут разными, или соответствующие числа сравняются. Поэтому можно считать, что $\alpha>\beta=\gamma$. Если $n<p$, то сделаем несколько переливаний $(n, p, q) \Rightarrow (2n, p-n, q) \Rightarrow \dots$, пока $n_i$ станет больше $p_i$ (β при этом не изменится, а $\alpha$ — возрастет). Итак, $n>p$, $\alpha>\beta=\gamma$. Если $p<q$, $(n, p, q) \Leftrightarrow (n, 2p, q-p)$ и $n+2p=2^{\gamma+1}m$, т. е. число γ увеличивается. Если $p>q$, $(n, p, q) \Leftrightarrow (n-p+q, 2(p-q), 2q)$ и $2(p-q)+2q=2p$. $\gamma$ воввь увеличивается. Поскольку $\gamma$ не может возрастать неограниченно, на каком-то шаге будет получен пустой сосуд.

Легко понять, что если бы решила бы были бы теми же. Опоржнить можно все сосуды, кроме, быть может, двух.

Разумеется, в моей работе (Matематический сборник 45:2, 1958 год), не было и речи о сосудах.