Волшебники Джона Конвея

Константин Кноп
«Квант» №8, 2020

Замечательный математик Джон Хортон Конвей знаменит не только разработанной им комбинаторной теорией игр, но и огромным вкладом в занимательную математику. Одну из самых интригующих задач Конвея я впервые услышал в пересказе Т. Ховановой [1], именно этот рассказ и послужил основой для данной статьи. Вот эта задача:

Вчера вечером я ехал в одном автобусе с двумя волшебниками и подслушал их беседу:
    А: У меня есть несколько детей, возраст каждого из них — целое положительное число, причем их сумма равна номеру этого автобуса, а произведение — моему собственному возрасту.
    В: Как интересно! Возможно, если ты скажешь мне свой возраст и число твоих детей, я смогу вычислить их возраста?
    А: Нет, не сможешь.
    В: Ага! Наконец-то я узнал твой возраст.
Каким был номер автобуса, в котором мы ехали?

Начну с замечаний. Автор головоломки — Джон Конвей — тщательно продумывал весь ее антураж. В частности, местом действия выбран автобус (bus), потому что вместе с возрастом первого волшебника (аgе) и количеством его детей (children) у Конвея получились удобные обозначения для трех числовых величин — \(a\), \(b\), \(c\). Пожалуй, я тоже сохраню именно эти обозначения. Итак, пусть \(a\) — возраст первого волшебника, \(b\) — номер автобуса (неизвестный нам, но известный второму волшебнику), а \(c\) — количество детей первого волшебника.

Второе замечание касается фразы волшебника А «Нет, не сможешь». В этом утверждении волшебник вовсе не сомневается в интеллектуальных способностях своего друга. Оно означает, что даже по полностью известной тройке чисел \((a,\ b,\ c)\) невозможно однозначно определить возраста детей. Иначе говоря, имеются несколько разных наборов возрастов детей, которые дают одни и те же значения \((a,\ b,\ c)\). Давайте будем называть такие наборы возрастов конвеевскими, или К-наборами.

Безумно красивой эту головоломку делает то, что к ней очень непросто подступиться. Если бы нам был известен возраст волшебника (число \(a\)), то можно было бы перебрать его делители и найти все варианты их сумм. Если бы был известен номер автобуса (\(b\)) — можно было бы разложить его различными способами в сумму слагаемых и получить варианты для их произведений. И даже если бы нам было известно всего лишь число детей (\(c\)), все равно объем перебора был бы уже существенно меньшим. Некоторые мои знакомые тратили на программирование перебора вариантов несколько часов и только тогда соображали, как подступаться к правильному решению.

Не правда ли, задача кажется совершенно недоопределенной, т. е. допускающей разные решения?

Вот одно из типичных рассуждений. Допустим, они едут в автобусе номер 21 (\(b=21\)), волшебнику 96 лет (\(a=96\)) и у него трое детей (\(c=3\)). Это значит, что их возраста — три натуральных числа с суммой 21 и произведением 96. Таких троек чисел есть две: (1, 8, 12) и (2, 3, 16), т. е. действительно если даже второй волшебник узнает все это, он не сможет определить возраста детей. Разве этот ответ не годится? Почему? Разве мы не нашли числа, удовлетворяющие всем условиям из диалога волшебников?

Нет, не нашли. Ответ «96 лет, автобус номер 21, 3 ребенка» не годится потому, что не учитывает самую последнюю реплику — о том, что волшебник В смог выяснить возраст волшебника А. Смог бы он это сделать, зная только номер автобуса? Иными словами, нет ли других К-наборов чисел с тем же \(b\), но другим \(a\)? Чтобы ответить на этот вопрос, поставим его иначе. Нет ли других К-троек чисел с меньшим \(b\) и другим \(a\)? Ведь если они отыщутся, то можно просто добавить к ним несколько годовалых детей так, чтобы общая сумма чисел (число \(b\)) в получившемся К-наборе оказалась равной 21. При этом произведение (число \(a\), т. е. возраст волшебника) не поменяется и останется отличным от старого. И действительно, такие К-тройки легко найти: например, это (1, 5, 8) и (2, 2, 10). Добавляя к ним годовалых детей, можно получить К-набор с любым \(b > 14\) (а возраст волшебника при этом — 40 лет). А из К-наборов (1, 6, 6) и (2, 2, 9) аналогичная операция дает К-набор с любым \(b > 13\), при этом волшебнику 36 лет. Таким образом, номер автобуса не может быть больше 13 — ведь в этом случае волшебник В не смог бы понять, 40 лет его напарнику или 36 (а возможно, и еще какие-то варианты нашлись бы).

Кажется, мы ухватили эту головоломку за правильный «хвост». Нам нужно отыскать наименьший номер автобуса, дающий два К-набора — и тогда все последующие значения номеров не будут годиться.

Мог ли у волшебника А быть всего один ребенок? Очевидно, нет: тогда бы его возраст совпадал и с номером автобуса, и с возрастом А, причем это единственный случай, когда \(b = a\). Следовательно, узнав (вычислив) \(a\), волшебник В сразу бы определил число детей (\(c = 1\)) и возраст этого ребенка, — но ведь мы должны верить А, который утверждает, что этого невозможно сделать.

А как насчет двух детей (\(c = 2\))? Тогда, вычислив возраст \(a\) и зная номер автобуса \(b\), волшебник В знал бы сумму и произведение двух натуральных чисел. Сможет ли он найти сами числа? Геометрическая аналогия этой задачи — известны полупериметр и площадь прямоугольника, стороны которого мы хотим найти (рис. 1). Оказывается, что в этом случае можно узнать сами числа (в геометрическом варианте — стороны прямоугольника) даже в том случае, когда они не являются целыми, однако для этого нужно уметь решать квадратные уравнения. В нашем же случае можно обойтись простым перебором: найти все пары чисел с заданной суммой, начав с пары 1 и \(b-1\), и затем «сближая» числа — их произведение при этом будет расти. В тот момент, когда произведение окажется равным \(a\), нужные числа найдены. Таким образом, и для двоих детей А не мог бы сказать «Нет». Следовательно, при переборе можно отбросить все варианты с одним и двумя детьми.

Рис. 1.

А можно ли еще что-то отбросить? Да. Поскольку мы хотим найти минимальный номер автобуса, дающий неоднозначность выбора возрастов детей, то в разных К-наборах не должно быть совпадающих чисел — потому что если бы они были, то их можно было бы убрать из каждого набора, и тогда номер автобуса (сумма) оказался бы еще меньшим. Например, если в одном из наборов есть годовалый ребенок, то в другом его быть не должно. Следовательно, в одном из К-наборов все дети старше года.

Подведем промежуточные итоги. Мы сейчас будем искать разложения номера автобуса \(b\) в сумму нескольких натуральных слагаемых, больших 1. При этом рассматриваем только такие разложения, в которых число слагаемых не меньше 3, а сам номер автобуса не больше 12 (потому что для 13 мы уже знаем нужную пару К-наборов, а хотим либо найти еще меньшую, либо убедиться, что ее нет).

Поехали! Перебирать варианты, безусловно, не самая приятная работа, однако порой необходимая для успешного решения жизненных задач. В нашем переборе мы будем отмечать значком \(\rhd\) строки с теми значениями \(a\), которые встречаются (во всем переборе) более одного раза, причем с разными \(b\).

Сначала перечислим разложения, в которых каждое слагаемое больше 1:

\[\begin{split} 6 &= 2 + 2+2\ &(a=8) \\ \rhd 7 &= 2 + 2+ 3\ &(a=12) \\ \rhd 8 &= 2 + 2 + 2 + 2\ &(a=16) \\ \rhd 8 &= 2 + 2+ 4\ &(a=16) \\ \rhd 8 &= 2 + 3 + 3\ &(a=18) \\ \rhd 9 &= 2 + 2 + 2 + 3\ &(a=24) \\ 9 &= 2 + 2 + 5\ &(a=20) \\ \rhd 9 &= 2 + 3 + 4\ &(a=24) \\ 9 &= 3 + 3 + 3\ &(a=27) \\ \rhd 10 &= 2 + 2 + 2 + 2 + 2\ &(a=32) \\ \rhd 10 &= 2 + 2 + 2+ 4\ &(a=32) \\ \rhd 10 &= 2 + 2 + 3 + 3\ &(a=36) \\ \rhd 10 &= 2 + 2+ 6\ &(a=24) \\ \rhd 10 &= 2+3 + 5\ &(a=30) \\ \rhd 10 &= 2+4+4\ &(a=32) \\ \rhd 10 &= 3 + 3+ 4\ &(a=36) \\ \rhd 11 &= 2 + 2 + 2 + 2+ 3\ &(a=48) \\ 11 &= 2 + 2 + 2 + 5\ &(a=40) \\ \rhd 11 &= 2 + 2+ 3 + 4\ &(a=48) \\ \rhd 11 &= 2+3 + 3 + 3\ &(a=54) \\ 11 &= 2 + 2 + 7\ &(a=28) \\ \rhd 11 &= 2+3 + 6\ &(a=36) \\ 11 &= 2+4 + 5\ &(a=40) \\ 11 &= 3 + 3 + 5\ &(a=45) \\ \rhd 11 &= 3 + 4 + 4\ &(a=48) \\ 12 &= 2 + 2 + 2 + 2 + 2 + 2\ &(a=64) \\ 12 &= 2+2+2+2+4\ &(a=64) \\ 12 &= 2+2+2+3+3\ &(a=72) \\ \rhd 12 &=2+2+2+6\ &(a=48) \\ 12 &=2+2+3+5\ &(a=60) \\ 12 &= 2+2+4+4\ &(a=64) \\ 12 &=2+3+3+4\ &(a=72) \\ 12 &= 3+3+3+3\ &(a=81) \\ \rhd 12 &=2+2+8\ & (a=32) \\ 12 &=2+3+7\ &(a=42) \\ \rhd 12 &=2+4+6\ &(a=48) \\ 12 &= 2+5+5\ &(a=50) \\ \rhd 12 &= 3+3+6\ &(a=54) \\ 12 &=3+4+5\ &(a=60) \\ 12 &=4+4+4\ &(a=64)\end{split}\]

Перебор еще не окончен: ведь есть еще К-наборы с единицей, причем их наверняка больше. Как быть с ними?

Мы не будем выписывать их отдельно, но добавим к уже выписанным наборы из одного и двух слагаемых, а затем отследим каждый из вариантов по уже выписанной таблице — ведь добавление единицы или нескольких единиц
    (i) сохраняет произведение;
    (ii) увеличивает на сколько-то количество детей;
    (iii) увеличивает на столько же число \(b\), т. е. сумму возрастов детей.

К ранее выписанным наборам добавляются:

\[\begin{split}2 &= 2\ &(a=2) \\ 3 &= 3\ &(a=3) \\ \ldots \\ 11 &= 11\ &(a=11) \\ 4 &= 2+2\ & (a=4) \\ \rhd 5 &= 2+3\ &(a=6) \\ \rhd 6 &= 3+3\ &(a=9) \\ \rhd 6 &= 2+4\ &(a=8) \\ \rhd 7 &= 3+4\ &(a=12) \\ \rhd 7 &= 2+5\ &(a=10) \\ \rhd 8 &= 4+4\ &(a=16) \\ 8 &=3+5\ &(a=15) \\ \rhd 8 &= 2+6\ &(a=12) \\ 9 &= 4+5\ &(a=20) \\ \rhd 9 &=3+6\ &(a=18) \\ 9 &= 2+7\ &(a=14) \\ 10 &= 5+5\ &(a=25) \\ \rhd 10 &=4+6\ &(a=24) \\ 10 &=3+7\ &(a=21) \\ \rhd 10 &=2+8\ &(a=16) \\ \rhd 11 &=5+6\ &(a=30) \\ 11 &=4+7\ &(a=28) \\ \rhd 11 &=3+8\ &(a=24) \\ \rhd 11 &=2+9\ &(a=18)\end{split}\]

Суммы 12 и выше выписывать уже не станем, так как после добавления единиц они увеличатся.

Поскольку К-наборы должны иметь одинаковые \(a\), нас будут интересовать только строки, отмеченные знаком \(\rhd\). Выпишем все наборы снова, упорядочив по возрастанию \(a\):

Ну а теперь уже дорешать головоломку до конца можно как угодно — например, отбрасывать все варианты, содержащие равные слагаемые (потому что если такие слагаемые есть, то после их отбрасывания получается другой набор, с меньшей суммой и меньшим произведением). А можем учесть, что большему значению суммы \(b\) в другом К-наборе соответствует большее число детей. Так или иначе, из всех выписанных строчек нам подходят всего две —

\[\begin{split} \rhd 11 &= 3+4 + 4\ &(a=48) \\ \rhd 12 &= 2+2 + 2 + 6\ &(a=48)\end{split}\]

Они приводят к двум таким К-наборам: \(12 = 1+3 + 4 + 4 = 2 + 2 + 2 + 6\). Значит, ехали они в автобусе номер 12, а первому волшебнику — 48 лет. Задача решена!

Визуализацию решения этой задачи можно посмотреть в [4].

*  *  *

Попробуйте самостоятельно разобраться со следующими вариантами диалога волшебников.

1 (упрощение задачи Конвея, автор — Т. Хованова [1]).
    А: У меня есть несколько детей, возраст каждого из них — целое положительное число, причем их сумма равна номеру этого автобуса.
    В: Как интересно! Возможно, если ты скажешь мне число твоих детей, я смогу вычислить их возраста?
    А: Нет, не сможешь.
    В: Ага! Наконец-то я узнал, сколько у тебя детей.
Каков номер автобуса?

2 (широко известная версия).
    А: У меня трое детей, возраст каждого из них — целое положительное число, причем их сумма равна номеру этого автобуса, а произведение — 36.
    В: Но я не могу узнать, сколько им лет!
    А: Твоя дочь старше всех моих детей.
    В: Спасибо, этого хватает.
Сколько лет детям волшебника А и каков в этот раз номер автобуса?

3 (авторская версия [3]).
    А: У меня четверо сыновей, произведение их возрастов равно 180, а сумма их возрастов равна номеру этого автобуса.
    Б: Все равно информации недостаточно!
    А: Мой младший сын очень любит мороженое.
    Б: И этого еще недостаточно.
    А: А у старшего сегодня день рождения.
    Б: Спасибо, теперь я знаю, сколько им лет!

4. Волшебник поймал Алису и Боба и сказал каждому целое число от 0 до 10, причем их числа отличаются на единицу (и они об этом знают). Диалог:
    Алиса: Я не знаю твоего числа, а ты не знаешь моего.
    Боб: Я не знаю твоего числа, а ты не знаешь моего. Теперь ты знаешь мое число!
Какое число было сообщено Бобу?

Литература
1. Tanya Khovanova. Conway’s Wizards.
2. С. Артемов, Ю. Гиматов, В. Федоров. Много битов из ничего // «Квант», 1977, №3.
3. К. Кноп. Задача о детях бармена.
4. А. Перепечко. Визуализация задачи Конвея.