МАТЕМАТИЧЕСКИЙ КРУЖОК
Волшебники Джона Конвея
К.КНОП
ЗАМЕЧАТЕЛЬНЫЙ МАТЕМАТИК Джон Хортон Конвей знаменит не только разработанной им комбинаторной теорией игр, но и огромным вкладом в занимательную математику. Одну из самых интригующих задач Конвея я впервые услышал в пересказе Т.Ховановой [1], именно этот рассказ и послужил основой для данной статьи. Вот эта задача: Вчера вечером я ехал в одном автобусе с двумя волшебниками и подслушал их беседу: A: У меня есть несколько детей, возраст каждого из них – целое положительное число, причем их сумма равна номеру этого автобуса, а произведение – моему собственному возрасту. B: Как интересно! Возможно, если ты скажешь мне свой возраст и число твоих детей, я смогу вычислить их возраста? A: Нет, не сможешь. B: Ага! Наконец-то я узнал твой возраст. Каким был номер автобуса, в котором мы ехали? Начну с замечаний. Автор головоломки – Джон Конвей – тщательно продумывал весь ее антураж. В частности, местом действия выбран автобус (bus), потому что вместе с возрастом первого волшебника (age) и количеством его детей (children) у Конвея получились удобные обозначения для трех числовых величин – a, b, c. Пожалуй, я тоже сохраню именно эти обозначения. Итак, пусть a – возраст первого волшебника, b – номер автобуса (неизвестный нам, но известный второму волшебнику), а c – количество детей первого волшебника. Второе замечание касается фразы волшебника А «Нет, не сможешь». В этом утверждении волшебник вовсе не сомневается в интеллектуальных способностях своего друга. Оно означает, что даже по полностью известной тройке чисел a, b, c невозможно
DOI: https://doi.org/10.4213/kvant20200804
однозначно определить возраста детей. Иначе говоря, имеются несколько разных наборов возрастов детей, которые дают одни и те же значения 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 смог выяснить возраст волшебника А. Смог бы он это сделать, зная только номер автобуса? Иными словами, нет ли других К-наборов чисел с тем же b, но другим a? Чтобы ответить на этот вопрос, поставим его иначе. Нет ли других К-троек чисел с меньшим b и другим a? Ведь если они отыщутся, то можно просто добавить к ним несколько годовалых детей так, чтобы общая сумма чисел (число b) в получившемся Кнаборе оказалась равной 21. При этом произведение (число a, т.е. возраст волшебника) не поменяется и останется отличным от старого. И действительно, такие K-тройки легко найти: например, это 1, 5, 8 и 2, 2, 10. Добав-
42
КВА НT 2020/№8
ляя к ним годовалых детей, можно получить К-набор с любым b! 14 (а возраст волшебника при этом – 40 лет). А из К-наборов 1, 6, 6 и 2, 2, 9 аналогичная операция дает К-набор с любым b! 13, при этом волшебнику 36 лет. Таким образом, номер автобуса не может быть больше 13 – ведь в этом случае волшебник В не смог бы понять, 40 лет его напарнику или 36 (а возможно, и еще какие-то варианты нашлись бы). Кажется, мы ухватили эту головоломку за правильный «хвост». Нам нужно отыскать наименьший номер автобуса, дающий два К-набора – и тогда все последующие значения номеров не будут годиться.
Лирическое отступление
Мог ли у волшебника А быть всего один ребенок? Очевидно, нет: тогда бы его возраст совпадал и с номером автобуса, и с возрастом А, причем это единственный случай, когда b a. Следовательно, узнав (вычислив) a, волшебник B сразу бы определил число детей (с 1) и возраст этого ребенка, – но ведь мы должны верить А, который утверждает, что этого невозможно сделать. А как насчет двух детей (c 2)? Тогда, вычислив возраст a и зная номер автобуса b, волшебник B знал бы сумму и произведение двух натуральных чисел. Сможет ли он найти сами числа? Геометрическая аналогия этой задачи – известны полупериметр и площадь прямоугольника, стороны которого мы хотим найти (рис.1). Оказывается, что в
Рис. 1
этом случае можно узнать сами числа (в геометрическом варианте – стороны прямоугольника) даже в том случае, когда они не являются целыми, однако для этого нужно уметь решать квадратные уравнения. В нашем же случае можно обойтись простым перебором: найти все пары чисел с заданной суммой, начав с пары 1 и b 1, и затем «сближая» числа – их произведение при этом будет расти. В тот момент, когда произведение окажется равным a, нужные числа найдены. Таким образом, и для двоих детей А не мог бы сказать «Нет». Следовательно, при переборе можно отбросить все варианты с одним и двумя детьми.
А можно ли еще что-то отбросить? Да. Поскольку мы хотим найти минимальный номер автобуса, дающий неоднозначность выбора возрастов детей, то в разных Кнаборах не должно быть совпадающих чисел – потому что если бы они были, то их можно было бы убрать из каждого набора, и тогда номер автобуса (сумма) оказался бы еще меньшим. Например, если в одном из наборов есть годовалый ребенок, то в другом его быть не должно. Следовательно, в одном из К-наборов все дети старше года. Подведем промежуточные итоги. Мы сейчас будем искать разложения номера автобуса b в сумму нескольких натуральных слагаемых, больших 1. При этом рассматриваем только такие разложения, в которых число слагаемых не меньше 3, а сам номер автобуса не больше 12 (потому что для 13 мы уже знаем нужную пару К-наборов, а хотим либо найти еще меньшую, либо убедиться, что ее нет). Поехали! Перебирать варианты, безусловно, не самая приятная работа, однако порой необходимая для успешного решения жизненных задач. В нашем переборе мы будем отмечать значком строки с теми значениями a, которые встречаются (во всем переборе) более одного раза, причем с разными b. Сначала перечислим разложения, в которых каждое слагаемое больше 1: 6 2 + 2 + 2 (a 8) 7 2 + 2 + 3 (a 12) 8 2 + 2 + 2 + 2 (a 16) 8 2 + 2 + 4 (a 16) 8 2 + 3 + 3 (a 18) 9 2 + 2 + 2 + 3 (a 24) 9 2 + 2 + 5 (a 20) 9 2 + 3 + 4 (a 24) 9 3 + 3 + 3 (a 27) 10 2 + 2 + 2 + 2 + 2 (a 32) 10 2 + 2 + 2 + 4 (a 32) 10 2 + 2 + 3 + 3 (a 36) 10 2 + 2 + 6 (a 24) 10 2 + 3 + 5 (a 30) 10 2 + 4 + 4 (a 32) 10 3 + 3 + 4 (a 36) 11 2 + 2 + 2 + 2 + 3 (a 48) 11 2 + 2 + 2 + 5 (a 40) 11 2 + 2 + 3 + 4 (a 48) 11 2 + 3 + 3 + 3 (a 54) 11 2 + 2 + 7 (a 28) 11 2 + 3 + 6 (a 36) 11 2 + 4 + 5 (a 40) 11 3 + 3 + 5 (a 45) 11 3 + 4 + 4 (a 48) 12 2 + 2 + 2 + 2 + 2 + 2 (a 64)
43
МАТЕМАТИЧЕСКИЙ
12 2 + 2 + 2 + 2 + 4 (a 64) 12 2 + 2 + 2 + 3 + 3 (a 72) 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) 12 2 + 2 + 8 (a 32) 12 2 + 3 + 7 (a 42) 12 2 + 4 + 6 (a 48) 12 2 + 5 + 5 (a 50) 12 3 + 3 + 6 (a 54) 12 3 + 4 + 5 (a 60) 12 4 + 4 + 4 (a 64) Перебор еще не окончен: ведь есть еще Кнаборы с единицей, причем их наверняка больше. Как быть с ними? Мы не будем выписывать их отдельно, но добавим к уже выписанным наборы из одного и двух слагаемых, а затем отследим каждый из вариантов по уже выписанной таблице – ведь добавление единицы или нескольких единиц (i) сохраняет произведение; (ii) увеличивает на сколько-то количество детей; (iii) увеличивает на столько же число b, т.е. сумму возрастов детей. К ранее выписанным наборам добавляются: 2 2 (a 2) 3 3 (a 3) … 11 11 (a 11) 4 2 + 2 (a 4) 5 2 + 3 (a 6) 6 3 + 3 (a 9) 6 2 + 4 (a 8) 7 3 + 4 (a 12) 7 2 + 5 (a 10) 8 4 + 4 (a 16) 8 3 + 5 (a 15) 8 2 + 6 (a 12) 9 4 + 5 (a 20) 9 3 + 6 (a 18) 9 2 + 7 (a 14) 10 5 + 5 (a 25) 10 4 + 6 (a 24) 10 3 + 7 (a 21) 10 2 + 8 (a 16) 11 5 + 6 (a 30) 11 4 + 7 (a 28) 11 3 + 8 (a 24) 11 2 + 9 (a 18) Суммы 12 и выше выписывать уже не станем, так как после добавления единиц они увеличатся.
КРУЖОК
Поскольку К-наборы должны иметь одинаковые а, нас будут интересовать только строки, отмеченные знаком. Выпишем все наборы снова, упорядочив по возрастанию a: 5 2 + 3 (a 6) 6 6 (a 6)
6 8
2 + 2 + 2 8 (a 8)
2 + 4 (a 8)
6 9
3 + 3 (a 9) 9 (a 9)
7 2 + 5 (a 10) 10 10 (a 10)
7 8
2 + 2 + 3 3 + 4 (a 12) 2 + 6 (a 12)
8 2 + 2 + 2 + 2 2 + 2 + 4 10 2 + 8 (a 16)
4 + 4 (a 16)
8 2 + 3 + 3 (a 18) 9 3 + 6 (a 18) 11 2 + 9 (a 18)
9 2 + 2 + 2 + 3 2 + 3 + 4 (a 24) 10 2 + 2 + 6 (a 24)
10 11
2 + 3 + 5 (a 30) 5 + 6 (a 30),
10 2 + 2 + 2 + 2 + 2 2 + 4 + 4 (a 32) 12 2 + 2 + 8 (a 32)
10 11
2 + 2 + 2 + 4
2 + 2 + 3 + 3 3 + 3 + 4 (a 36) 2 + 3 + 6 (a 36)
11 2 + 2 + 2 + 2 + 3 2 + 2 + 3 + 4 3 + 4 + 4 (a 48) 12 2 + 2 + 2 + 6 2 + 4 + 6 (a 48)
11 2 + 3 + 3 + 3 (a 54) 12 3 + 3 + 6 (a 54) Ну а теперь уже дорешать головоломку до конца можно как угодно – например, отбрасывать все варианты, содержащие равные слагаемые (потому что если такие слагаемые есть, то после их отбрасывания получается другой набор, с меньшей суммой и меньшим произведением). А можем учесть, что большему значению суммы b в другом К-наборе соответствует большее число детей. Так или иначе, из всех выписанных строчек нам подходят всего две –
11 12
3 + 4 + 4 (a 48) 2 + 2 + 2 + 6 (a 48)
Они приводят к двум таким К-наборам: 12 1 + 3 + 4 + 4 2 + 2 + 2 + 6. Значит, ехали