Головоломка о сумме и произведении — это логическая головоломка, известная также как невозможная головоломка, поскольку кажется, что отсутствует достаточно информации для решения. Головоломка была впервые опубликована в 1969 году Гансом Фройденталем, а название невозможная головоломка дал задаче Мартин Гарднер. Головоломка решаема, хотя и нелегко. Существует множество похожих головоломок.

Головоломка и — два целых числа больших 1 и . Их сумма не больше 100. S и P — два математика (а потому прекрасные логики). S знает сумму , а P знает произведение . У S и P это вся информация, которой они обладают.

В следующем разговоре оба математика говорят правду:

S говорит: «P не знает и .» P говорит: «Теперь я знаю и .» S говорит: «Теперь я тоже знаю и .»

Чему равны и ?

Объяснение

Как только концепции и перспективы становятся понятными, проблема легко решается. Имеется три вовлечённых лица — S, P и O. S знает сумму , P знает произведение , а наблюдатель O ничего не знает, кроме как начальное утверждение задачи.

Назовем 2-разложением числа на два слагаемых . Для этого не требуется никаких специальных знаний, таких как проблема Гольдбаха или факт, что произведение таких 2-разложений единственно (то есть, нет других двух чисел, дающих в произведении тот же результат). Но с гипотезой Гольдбаха и факта, что P немедленно узнал бы и , если их произведение полупростое, можно вывести, что сумма не может быть чётной, поскольку любое чётное число можно записать в виде суммы двух простых чисел.

Следующие шаги дают решение:

S (Сью), P (Пит) и O (Отто) создают таблицу всех произведений, которые могут быть образованы 2-разбиением чисел в диапазоне 5 до 100 ( и приводят к тому, что начинать нужно с 5). Например, 11 может быть разбит на и . Соответствующими произведениями будут 18, 24, 28 и 30. Игроки отмечают каждое из этих произведений в своих таблицах (Таблица 1). Когда они закончат, некоторые числа не будут иметь пометок, некоторые будут иметь одну пометку а некоторые будут иметь более одной метки. Сью теперь смотрит на сумму (которую она знает) и все их 2-разложения. Она видит, что все 2-разложения имеют произведения, которые не единственны. То есть, существует другое разложение на множители, являющееся 2-разложением некоторой другой возможной суммы. Она понимает что по этой причине Пит не может однозначно определить множители и исходя из произведения (для этого потребовалось бы, чтобы хотя бы одно из возможных произведений имело только одну галочку). Тогда она восклицает: «P не может знать и ». Когда Пит и Отто слышат это, они получают информацию, что ни одно из произведений, связанных с суммой у Сью, не является уникальным. Просматривая все возможные суммы одну за одной, Сью, Пит и Отто может теперь, каждый самостоятельно, составить список всех подходящих сумм (Таблица 2). Таблица содержит суммы, все 2-расщепления которых имеют произведения, не являющиеся уникальными, то есть имеющие более одной галочки в Таблице 1. Сью, Пит и Отто создали таблицу возможных сумм (Сью, конечно, уже знает свою сумму, но ей нужно проследить ход мыслей Пита). Учитывая новую информацию из Таблицы 2, Пит снова рассматривает своё произведение. Суммы всех возможных 2-разложений, соответствующих произведению, не попали в таблицу 2, Единственная оставшаяся сумма должна быть суммой двух неизвестных чисел и , произведение которых он знает. Из суммы и произведения легко узнать индивидуальные числа, и он произносит: «Теперь я знаю и ». На этом Пит заканчивает и выходит из игры. Сью и Отто пересчитывают Таблицу 1, на этот раз учитывая только произведения парных разбиений сумм, которые находятся в Таблице 2, а не все числа в диапазоне от 5 до 100, как в исходной Таблице 1. Эта обновленная таблица будет Таблицей 1B. Сью рассматривает все произведения парных разбиений своей суммы и обнаруживает, что только одно из них встречается ровно один раз в Таблице 1B. Это должно быть произведение, которое есть у Пита, и она может вывести два числа по их сумме и произведению так же легко, как это сделал Пит. Таким образом, она говорит Отто (Пит уже ушел): «Теперь я тоже знаю и ». На этом Сью также заканчивает и выходит из игры, остается только Отто. На основе информации из Шага 4 Отто просматривает все суммы в Таблице 2, ища ту, для которой существует только одно 2-разложение с одной галочкой в Таблице 1B. Искомая сумма может иметь только одну галочку, иначе Сью не смогла бы с уверенностью определить и . Наконец, Отто находит нужную сумму, которая также является единственной обладающей такими свойствами, что делает исходную задачу решаемой с единственным ответом. На этом задача Отто также завершена.

Решение Решение состоит из чисел и , равных 4 и 13. Изначально P знает, что произведение равно 52, а S знает, что сумма равна 17.

Изначально P не знает решения, поскольку

а S знает, что P не знает решения, поскольку все возможные суммы, дающие 17 в рамках заданных ограничений, приводят к столь же неоднозначным произведениям. Однако, когда P узнаёт, что существует несколько возможных решений, исходя из произведения, P может исключить вариант 2 x 26. В этом случае сумма равна 28, а четные суммы исключаются в соответствии с гипотезой Гольдбаха, как указано выше.

Итак, P теперь знает, что числа — это 4 и 13, и сообщает S, что он знает эти числа. Из этого S теперь понимает, что из всех возможных пар, основанных на сумме (а именно, ), только у одной произведение таково, что P смог бы определить ответ, а именно . Читатель может затем сделать вывод о единственном возможном решении, исходя из того, что S смог его определить. Обратите внимание, что, например, если бы S получил сумму 97 () а P было названо число 2352 (), P смог бы определить единственное возможное решение, но S — нет, поскольку 44 и 53 остались бы логически возможной альтернативой.

Другие решения Задачу можно обобщить. Ограничение выбрано намеренно. Если изменить предел суммы , число решений может измениться. При решений нет. На первый взгляд это может показаться нелогичным, поскольку решение укладывается в это ограничение. Однако из-за исключения произведений, множители которых в сумме дают числа в пределах этих границ, больше нет множества способов разложить на множители все произведения, не являющиеся решениями, что приводит к тому, что информация не дает никакого решения задачи. Например, если не рассматривается, то остаётся только одно произведение 124, а именно , дающее в сумме 35. Тогда 35 исключается, когда S заявляется, что P не может знать множители произведения, чего бы не произошло, если бы сумма 64 была разрешена.

С другой стороны, если сумма или выше, возникает второе решение: . С этого момента задача теряет однозначность, поскольку появляется несколько решений. Аналогично, при или выше, появляется третье решение (). Все эти три решения включают одно простое число простое число. Первое решение, не содержащее простых чисел, является четвертым и возникает при или выше со значениями и .

Если условие заменить на , имеется единственное решение для порога при , после чего решений становится несколько. При t равном 124 и ниже решений нет. Неудивительно, что порог для существования решения повысился. Интуитивно, пространство задач стало «разреженнее», поскольку простое число 2 больше не доступно в качестве множителя , при заданной сумме . Когда решений много, то есть при более высоких значениях , некоторые решения совпадают с решениями исходной задачи с условием , например, при .

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

Смотрите также Головоломка о возрасте трёх детей День рождения Шерил

Примечания

Ссылки The Impossible Problem by Torsten Sillke Two Mathematicians Problem on mathforum Sum and Product problem on MathWorks Cody Model Checking Sum and Product

Категория:Логические игры