Загадочный граф

Обозначим число, известное Б, через \(n\), а число, известное В, — через \(k\).

Исходя из слов А и не вникая пока в реплики Б и В, попробуйте определить, для каких \(n\) существуют подходящие графы, и найти диапазон возможных значений \(k\) для каждого такого \(n\). Рассмотрите все графы, удовлетворяющие условиям, сформулированным A, для малых значений \(n\).

Вооружившись этой информацией, можно приступить к анализу диалога Б и В.

Существуют ли такие \(n\), что знание \(k\) позволит Б гарантированно определить граф? А существуют ли такие \(n\), для которых знания \(л\) будет заведомо недостаточно?

Наконец, существуют ли \(n\), не относящиеся ни к первой, ни ко второй категории?

Ясно, что В не может быть бездетен (это означает, что \(k>0\)). Единственный граф, у которого и максимальная степень вершины, и количество связных компонент равны 1, состоит из двух вершин, соединенных единственным ребром, не удовлетворяет условию. Поэтому \(k\ge2\). Но тогда легко убедиться (убедитесь!), что \(n\ge6\). Кроме того, понятно, что \(k\le\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) (иначе максимальная степень вершины будет меньше количества связных компонент).

Рассмотрим возможные графы (то есть, те, у которых поровну вершин и ребер, а количество связных компонент равно максимуму степеней вершин) для малых значений \(n\). Очень часто, в случае, когда нет готовых идей, именно такое рассмотрение служит толчком к решению.

При \(n=6\), \(k=2\) существует всего один подходящий граф (рис. 1).

Рис. 1.

При \(n=6\), \(k=3\) тоже имеется всего один подходящий граф (рис. 2).

Рис. 2.

И при \(n=7\), \(k=2\) тоже найдется всего один подходящий граф (рис. 3).

Рис. 3.

А вот при \(n=7\), \(k=3\) есть более одного подходящего графа (рис. 4).

Рис. 4.

И при \(n=8\) для каждого допустимого \(k\) (в данном случае \(k\in\{2,3,4\}\)) будет более одного подходящего графа. Например, при \(k=2\) таковыми будут граф, являющийся объединением двух 4-звенных циклов, и граф, являющийся объединением 3-звенного и 5-звенного циклов.

Но не будем же мы перебирать весь натуральный ряд?! Ведь в условии \(n\) ничем не ограничено сверху. Конечно, не будем! Покажем, что при всех \(n\ge8\) для каждого \(k\) от 2 до \(\Bigl\lfloor\frac{n}{2}\Bigr\rfloor\) существует более одного подходящего графа.

При этом достаточно рассматривать четные \(n\) (для нечетных можно просто добавить в каждый из подходящих графов по ребру и вершине, «поместив» вершину на имеющееся ребро).

При \(k=2\) можно взять один граф из двух равных циклов, а другой — из двух различных (как мы сделали для \(n=8\)).

При \(k=\frac{n}{2}\) можно взять общую «заготовку»: \(k-1\) изолированную вершину и цикл длины \(k+1\), к которому добавлены \(k-2\) ребра, исходящие из одной вершины. Чтобы получить из этой заготовки два разных графа, достаточно в одном случае соединить ребром вершины степени 2, а в другом — задействовать при добавлении ребра хотя бы одну вершину степени 3. Получающиеся таким образом графы для \(n=10\) представлены на рис. 5.

Рис. 5.

Наконец, при остальных \(k\) можно взять подходящие графы с разными количествами изолированных вершин.

Вернемся к задаче.

Мы видим, что при \(n=6\), знание \(k\) позволяет математику Б однозначно определить граф, а при \(n\ge8\) информация о количестве детей В не поможет. А вот при \(n=7\) математик Б сможет определить граф, если у В двое детей, и не сможет — если их трое. Таким образом, из второй реплики Б следует, что \(n=7\).

Но тогда из последней реплики математика В следует, что \(k=2\) (иначе он не смог бы определить, какой из изображенных на рис. 4 графов загадан). Поэтому загадан граф с рисунка 3.

Задачи, подобные предложенной — в которых надо учитывать рассуждения от имени персонажей задачи, обладающих информацией, не заданной в условии явно, — иногда называют задачами на эпистемическую логику. При этом негласно (а иногда и гласно) предполагается, что персонажи логичны и не ошибаются в вычислениях.

Такие задачи обычно «раскручиваются» пошагово: круг «подозреваемых» сначала очерчивается, а затем последовательно сужается на основании реплик персонажей. Нарушая этот принцип, можно попасть впросак. Так, много лет назад автор, впервые столкнувшись с задачей такого рода, потратил на решение достаточно много времени, нарушив этот принцип. Это была, пожалуй, наиболее известная и, возможно, старейшая задача на эпистемическую логику. Вот одна из ее формулировок:

Задача 1. На автобусной остановке встретились два бывших одноклассника, не видевшиеся много лет. В завязавшемся разговоре один из них сообщил, что является отцом троих сыновей. Дальше беседа развивалась так:
– И сколько же им лет?
– Произведение их возрастов равно 36, а сумма — номеру вот этого автобуса.

Собеседник отца семейства, посмотрев на номер автобуса и немного подумав, сказал:
– Этих данных мало.
– Ах, да! Старшего я назвал Сергеем.
– Вот теперь достаточно.

Сколько лет сыновьям?

В сети наиболее популярен вариант, где старший — рыжий, но автору этой заметки достался вариант с Сергеем.

Автор (в отличие от многих из тех, кому он позже предлагал эту задачу) был в курсе, что люди по имени «Сергей» не пребывают в шестилетнем возрасте всю жизнь с самого рождения. Конечно же, реплика про Сергея дает информацию о наличии старшего. На этом основании «сообразительный» автор, выписывая возможные тройки натуральных чисел, дающих в произведении 36, не стал выписывать тройку (6, 6, 1), в которой нет старшего. И, подсчитав суммы чисел в остальных тройках, надолго завис...

Теоретически не выглядит сложным рассуждение «раз собеседник отца семейства, который знал номер автобуса, не смог определить возрасты, значит существуют, по крайней мере, две разные тройки с одинаковыми суммами». Однако, практически все, кто сталкиваются с подобными задачами впервые, приходят к этой мысли, только обнаружив такие тройки. Этот факт подтверждает простую, но не самую очевидную мысль: чтобы решить задачу, надо действовать, а не ждать озарения, — озарение само посетит того, кто трудится. Все слышали, что периодическая таблица Менделееву приснилась., но это ведь не означает, что для того, чтобы совершить открытие, достаточно удачно поспать.

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

Задача 2. Падишах решил проверить, насколько мудры его визири Али и Вали. Вызвал их сказал:
– Я загадал две цифры, не обязательно различных. Сейчас я сообщу Али их произведение, а Вали — их сумму. Ваша задача — назвать загаданные цифры.

После этого султан шепотом на ухо сообщил Али произведение, а Вали — сумму.

Озадаченные мудрецы разговорились:
А: — Я не могу однозначно определить, что это за цифры.
В: — Я не могу однозначно определить, что это за цифры.
А: — Я не могу однозначно определить, что это за цифры.
В: — Я не могу однозначно определить, что это за цифры.
А: — Я не могу однозначно определить, что это за цифры.
В: — Я не могу однозначно определить, что это за цифры.
А: — Я не могу однозначно определить, что это за цифры.
В: — Я не могу однозначно определить, что это за цифры.
А: Ура! Я знаю эти цифры!

Что это за цифры?

Примечание: Нуля в ту далекую пору еще не изобрели.

Ясно, что Али не мог знать, например, число 33 (оно не является произведением двух цифр). Если же он знал, например, число 40, то он сразу бы догадался, что загаданы цифры 5 и 8.

Выпишем все произведения, которые мог знать Али, с учетом его первой реплики. В скобках укажем возможные суммы, которые мог знать при данном произведении Вали (см. самый левый столбец таблицы). Выделим те суммы, зная которые, Вали, услышав первую реплику напарника, узнал бы загаданные цифры. В самом деле, допустим Вали знал сумму 13. Тогда заранее он не мог определить, какая из пар (4, 9), (5, 8) и (6, 7) загадана. Но, услышав первую реплику Али, мудрый Вали отбросил бы варианты (5, 8) и (6, 7). Аналогично, сумма не могла равняться 12 и 4 (то есть числу, которое встречается в скобках всего один раз).

Во втором столбце представлены возможные произведения (и суммы в скобках), известные Али после первой реплики Вали. Ясно, что если бы Али знал произведение 4, то теперь он бы догадался, что загаданы 2 и 2. Но он не догадался, значит произведение — не 4.

И так далее.

В самом правом столбце представлены произведения (и суммы), которые мог знать Али после 4-й реплики Вали. Поскольку Али догадался, какие цифры загаданы, значит он знал то произведение, для которого осталась одна возможная сумма. Отсюда следует, что загаданы были цифры 2 и 8.

Обратите внимание (и в этом изюминка задачи), что реплику «Я знаю эти цифры!» можно было бы поставить на любое место с третьего по девятое и всякий раз мы получали бы новый единственный ответ. В то же время, если бы пятая реплика Али не отличалась от предыдущих, дальнейшие констатации визирей, что они не могут определить загаданные цифры, не продвигали бы их к решению (ведь каждая из оставшихся сумм встречается дважды и не может быть отброшена).

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

Задача 3. Математик С решил проверить, насколько сообразительны два его коллеги А и В. Он сказал им:
– Я загадал два различных натуральных числа, каждое из которых больше 1, но меньше 100. Сейчас я сообщу А их произведение, а В — их сумму. Ваша задача, назвать загаданные числа.

После этого С шепотом на ухо сообщил А произведение, а В — сумму. Озадаченные математики разговорились:
А: — Я не могу однозначно определить, что это за числа.
В: — Мог бы и не говорить. Я заранее это знал.
А: — Тогда я знаю эти числа!
В: — Тогда и я знаю!

Что это за числа?

Заметим, что первая реплика A служит лишь для выстраивания диалога, поскольку в информативном плане перекрывается первой репликой B (кстати, в нашей задаче аналогичная первая реплика Б тоже выполняет лишь художественную роль: Б не сможет определить граф, загаданный A, ни при каком \(n\)). Поэтому поиск решения начинается с анализа первого комментария математика, знающего сумму.

Во-первых, отметим, что это число не должно представляться в виде суммы двух различных простых чисел. Иначе существовал бы вариант, при котором математик, знающий произведение, легко определил бы сомножители. На этом основании мы можем отбросить все четные числа. Читатель может возразить, что знаменитая гипотеза Гольдбаха о том, что всякое четное число, большее 4, представляется в виде суммы двух простых, до сих пор не доказана. Это так. Но она проверена для всех чисел, на много порядков превосходящих суммы двузначных чисел. Поэтому четные числа сразу отбрасываем. Но и многие нечетные числа могут быть суммами двух простых. Понятно, что это в точности числа, на 2 большие нечетных простых чисел. Следовательно, нас интересуют лишь нечетные числа, на 2 превосходящие составные. Это числа 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53...

Да, многовато получается! Ведь на основании условия следует вести перебор до 197. А вот и нет! Оказывается, мы уже перечислили все возможные суммы! Уже следующее нечетное число, на 2 большее составного, не может быть суммой, известной B. В самом деле, если B знает число 57, то он не может исключить, что A знает число 212 = 53·4. Но тогда A сможет определить загаданные числа. Ведь в альтернативном разложении числа 212 возникают трехзначные множители. По той же причине можно отбросить и все числа, большие 57.

Итак, на основании того, что каждое из загаданных чисел меньше 100, нам удалось доказать, что их сумма не превосходит 53! Это и есть обещанный неожиданный вывод.

Дальнейшие шаги, основанные на анализе вторых реплик A и B, и приводящие к единственному решению, читатель может проделать самостоятельно. Отметим лишь, что для сокращения необходимого в задаче перебора очень помогает представление возможных чисел, известных B, в виде суммы простого числа и степени двойки. Дело в том, что произведение таких чисел имеет единственное представление в виде сомножителей, сумма которых нечетна.

Интересную модификацию последней задачи предложил Макс Алексеев. Все условия те же, за исключением диалога A и B, который выглядит так:

А: — Я не могу однозначно определить, что это за числа.
В: — Мог бы и не говорить. Я заранее это знал.
А: — А я заранее знал, что ты заранее будешь это знать.
В: — Но я не знаю, что это за числа.
А: — Зато я знаю!

Для подобных задач характерна рекурсия не только в рассуждениях, но и в условии. Приведем пример такой задачи-матрешки.

Задача 4. Ведущий Математического марафона придумал задачу. Но, прежде чем помещать ее в Марафон, он решил протестировать задачу и рассказал ее своему коллеге.

– Бывшие одноклассники Петр и Николай встретились на мероприятии, посвященном 40-летию выпуска из школы, и разговорились.
П: — Да-а... разбросала нас жизнь, 40 лет тебя не видел и ничего о тебе не слышал. А ведь раньше не разлей вода были, за одной партой сидели. Ну и как ты? Семьей обзавелся?
Н: — А как же! У меня три красавца сына!
П: — Ну ты даешь! И сколько же им лет?
Н: — Надеюсь, ты по-прежнему любишь головоломки? Тогда догадайся сам. Сумма их возрастов равна номеру квартиры, в которой ты жил в школьные годы, а произведение возрастов равно...

... Ведущий Марафона для удобства коллеги написал нужное число на бумажке и продолжил:

– Петр достал ручку и на несколько минут погрузился в вычисления...
П: — Ты знаешь, этих данных мне мало.
Н: — Ах, да! Забыл добавить, что среднего я назвал в твою честь.
П: — Спасибо! Теперь информации достаточно.
Сколько лет сыновьям Николая?

Коллега ведущего погрузился в вычисления (более продолжительные, чем Петр из задачи). Но его комментарий, не отличался от комментария Петра:
– Ты знаешь, этих данных мне мало — сказал он ведущему Марафона.
– Ах, да! — осознал ошибку ведущий. — Тогда пусть Петром зовут не среднего, а старшего сына Николая.
– К сожалению, это не спасет задачу. А вот если Николай назовет Петром своего младшего сына, тогда задача будет иметь единственное решение!

Что за число написал ведущий?

А что же графы? Они, почему-то, не частые гости в подобных задачах. По мере сил, автор пытается восполнить этот пробел. Результаты его усилий можно найти в конкурсе «Математический марафон», а также в статье «Логические задачи на нестандартном материале».