Интернет-журнал "Домашняя лаборатория", 2007 №1

_{Список литературы}

_{[1] А. Я. Хинчин. Цепные дроби. Государственное изд-во физ. — мат. лит-ры. М., 1961.}

Задача: Три рыбака ловили рыбу и после ловли заночевали на берегу. Двое рыбаков заснули, а третий решил уехать домой со своей частью улова. Он разделил рыбу на 3 равные части, но при этом одна рыбина оказалась лишней. Он швырнул ее в воду, забрал свою треть и ушел.

Среди ночи проснулся второй рыбак и тоже решил уехать. Не зная, что первый рыбак уже ушел, он тоже поделил всю рыбу на 3 равные части, одна рыбина снова оказалась лишней, он ее тоже выкинул и ушел.

То же произошло и с последним рыбаком: проснувшись, он тоже разделил оставшийся улов на 3 равные части, выкинул одну рыбину и ушел.

Вопрос: какое наименьшее количество рыб могло быть у рыбаков?

Решение П. А. М. Дирака: Рыб было (-2). После того, как первый рыбак выкинул одну рыбину в воду, их осталось (-2) — 1 = -3. Потом он ушел, унося (-1) рыбу. Рыб стало (-3) — (-1) = -2. Второй и третий рыбаки просто повторили поступок своего товарища.

Из книги "Физики продолжают шутить".

На самом деле решение Дирака, хоть и остроумно, но, строго говоря, неверно, и во всяком случае неполно. Приведем полное, "математическое" решение, т. е. найдем ВСЕ решения.

Решение.

Пусть в начале рыб было n₀ (количество, после того, как уехало 0 рыбаков). Первый рыбак выбросил одну (лишнюю) рыбину (n₀ — > n₀ — 1), после чего количество рыбин стало делиться на 3, и взял 1/3 оставшегося улова, и после себя он оставил n₁ = (2/3)•(n₀ — 1) рыбин. Аналогичным образом действовали и остальные рыбаки, так что после отъезда 2-го рыбака рыб осталось n₂ = (2/3)•(n₁ — 1), а после отъезда 3-го — n₃ = (2/3)•(n₂ — 1). Подставляя в последнее равенство выражения для n₂ и n₁, получаем:

В итоге получаем уравнение, требующее разрешения в целых числах:

8n₀ — 27n₃ = 38.

Для упрощения расчетов имеет смысл уменьшить входящие в уравнение числа перейдя к новым переменным n₀ = n₀ + k, n₃ = n₃. Если взять k = 5, то уравнение превратится в

27n₃ — 8n₀ = 2. (1)

Это уравнение имеет вид

ах — by = с (1')

т. е. является диофантовым уравнением, и нужно найти все решения данного уравнения. Как это сделать?

Взглянем на уравнение (1') с точки зрения теории сравнений. В самом деле, требуется найти такое число х, что ах отличается от заданного числа с на слагаемое, кратное Ь. Иными словами, разность ах — с делится на Ь, т. е. (ах — с) = (mod b) или

ах = c(mod Ь). (1")

То же самое можно выразить словами: "ах сравнимо с с по модулю b" или "ах принадлежит тому же классу вычетов по модулю Ь, что и с". Т. е. мы свели уравнение с двумя неизвестными (х и у) к уравнению с одним неизвестным, поскольку ясно, что из (1'), зная х, сразу же можно найти у. Однако х все же не произволен, а именно — удовлетворяет (1").

Кроме того, можно усмотреть следующее. Уравнение (1') (или (1")) — это неоднородное сравнение первой степени (т. е. линейное сравнение). Согласно общей теории, общее решение неоднородного сравнения есть сумма частного решения неоднородного сравнения и общего решения однородного сравнения ах = (mod b). Таким образом, задача разбилась на две.

Займемся сначала неоднородным сравнением (1") — Рассматривая эквивалентное уравнение (1'), замечаем (стандартное рассуждение — см. [1]), что если числа а и b делятся на число k, то на это же число должно делиться и с. Поскольку это верно для любого общего делителя а и Ь, то это верно и для их наибольшего общего делителя (а, Ь) =< 1. Таким образом, делимость с на <1 — необходимое условие разрешимости сравнения (1").

В нашем случае а = 27, b = 8, (а, Ь) = 1, т. е. числа а и b взаимно просты, поэтому сравнение (1") разрешимо при любом с.

Из приведенного рассуждения следует и способ решения сравнения (1") — Если мы умеем решить уравнение ах₀ — by₀ =< d, то умножив его на целое число c/d (поскольку необходимо с делится на d), мы получим решение уравнения (1').

В нашем случае d = 1, и кратчайший способ решения уравнения ах₀ — by₀ = 1 дается в [2]. Именно, надо разложить число a/b в цепную дробь, и если а = р_n, b = q_n то положить х = (-1)^n-1q_n-1, y = (-1)^n-1p_n-1.Это следует просто из того, что q_{n_1}p_n — q_np_n-1 = (-1)^n-1.

В нашем случае

Поэтому

И в самом деле: 27•3–8•10 = 81–80 = 1, поэтому берем x₀ = 3, у₀ = 10. Значит частным решением уравнения аx₁ — by₁ = с будет х₁ =3•2, y₁ = 10•2.

Что касается однородного уравнения ах — by = 0, то очевидным семейством решений его будет х = b•k, у = a•k, k — произвольное целое число. То, что это общее решение однородного уравнения следует из того, что данное уравнение эквивалентно сравнению ах = (mod b) и в силу взаимной простоты а и b это сравнение можно поделить на а (см. [3]), после чего сравнение превращается в х = (mod b), т. е. х должно делиться на Ь.

В итоге, получаем решение

уравнения (1). Поэтому в исходных переменных получаем:

Если здесь положить k = —1, то получаем дираковское решение: n₀ = n₃ = —2. Однако видно, что оно вовсе не наименьшее, и существует множество других, еще меньше. Впрочем, в каком-то смысле дираковский ответ действительно наименьший из возможных: именно, если искать наименьшее по абсолютной величине возможное количество рыб, то таким в самом деле окажется (-2).