Головоломка с суммой и произведением
Головоломка о сумме и произведении , также известная как невозможная головоломка, поскольку в ней недостаточно информации для решения, представляет собой логическую головоломку . Впервые оно было опубликовано в 1969 году Гансом Фройденталем . [1] [2] а название «Невозможная головоломка» было придумано Мартином Гарднером . [3] Загадка разрешима, хотя и не легко. Существует много подобных головоломок.
Головоломка
[ редактировать ]X и Y — два целых числа больше 1, Y > X. а Их сумма не превосходит 100. S и P — два математика (а следовательно, совершенные логики); S знает сумму X + Y а P знает произведение X × Y. , И С, и П знают всю информацию в этом параграфе.
В следующем разговоре оба участника всегда говорят правду:
- S говорит: «P не знает X и Y ».
- P говорит: «Теперь я знаю X и Y ».
- S говорит: «Теперь я также знаю X и Y ».
Что такое X и Y ?
Объяснение
[ редактировать ]Проблему довольно легко решить, если прояснить концепции и перспективы. В решении участвуют три стороны: S, P и O. S знает сумму X+Y , P знает произведение X·Y , а наблюдатель O не знает ничего, кроме исходной постановки задачи. Все три стороны хранят одну и ту же информацию, но интерпретируют ее по-разному. Тогда это становится информационной игрой.
Назовем разбиение числа A на два слагаемых A=B+C 2-разбиением. Нет необходимости в каких-либо дополнительных знаниях, таких как гипотеза Гольдбаха или тот факт, что произведение B · C такого 2-разбиения будет уникальным (т.е. не существует двух других чисел, которые также при умножении дают тот же результат). Но с учетом гипотезы Гольдбаха, а также того факта, что P немедленно знал бы X и Y, если бы их произведение было полупростым , можно сделать вывод, что сумма x+y не может быть четной, поскольку каждое четное число можно записать как сумму двух простые числа. Тогда произведение этих двух чисел будет полупростым.
Следующие шаги дают решение:
- S (Сью), P (Пит) и O (Отто) составляют таблицы всех продуктов, которые могут быть сформированы из 2-разбиений сумм в диапазоне, т.е. от 5 до 100 ( X > 1 и Y > X требует от нас начать с 5). Например, число 11 можно разделить на 2: 2+9, 3+8, 4+7 и 5+6. Соответствующие продукты — 18, 24, 28 и 30, и игроки ставят галочку рядом с каждым из этих продуктов в своих таблицах (Таблица 1). Когда они будут завершены, на некоторых числах отметок не будет, на некоторых будет одна, а на некоторых их будет больше одной.
- Теперь Сью смотрит на свою сумму и все ее двойные дроби. Она видит, что все 2-разложения имеют продукты, которые не уникальны, т. е. существует другая факторизация, которая представляет собой 2-разбиение некоторой другой возможной суммы. Она видит это из таблицы на шаге 1, где все ее продукты отмечены более чем одной галочкой. Она понимает, что из-за этого Пит не сможет однозначно определить факторы X и Y , глядя на продукт (для этого потребовалось бы, чтобы хотя бы один из продуктов-кандидатов имел только одну галочку). При этом она восклицает: «Р не может знать X и Y ». Когда Пит и Отто слышат это, они получают информацию о том, что ни одно из произведений, связанных с суммой Сью, не является уникальным. Просматривая возможные суммы одну за другой, Сью, Пит и Отто теперь могут каждый по отдельности составить список всех подходящих сумм (таблица 2). Таблица содержит те суммы, все 2-разбиения которых имеют продукты, которые не являются уникальными, т.е. имеют более одной отметки в таблице 1. Сью, Пит и Отто создали таблицу сумм-кандидатов (Сью, конечно, уже знает ее сумма, но нужно проследить ход мыслей Пита).
- Учитывая новую информацию в Таблице 2, Пит еще раз смотрит на свой продукт. Суммы всех возможных двойных разбиений его произведения, кроме одного, исчезли из таблицы 2 по сравнению со всеми числами от 5 до 100, которые с самого начала считались суммами. Остается только сумма двух скрытых чисел X и Y , произведение которых X·Y ему известно. Из суммы и произведения легко узнать отдельные числа, и поэтому он говорит Сью: «Теперь я знаю X и Y ». Пит закончил и выходит из игры.
- Сью и Отто пересчитывают Таблицу 1, на этот раз считая произведения 2-разбиения только из сумм, которые находятся в Таблице 2, а не из всех чисел в диапазоне от 5 до 100, как в исходной Таблице 1. Эта обновленная таблица называется Таблицей 1B. Сью просматривает все произведения двух частей своей суммы и обнаруживает, что только одно из них появляется ровно один раз в таблице 1B . Тогда это должно быть произведение, которое есть у Пита, и она может вывести два числа из их суммы и произведения так же легко, как это сделал Пит. Таким образом, она говорит Отто (Пит уже ушел), что «Теперь я также знаю X и Y ». Сью тоже закончила и выходит из игры, остается только Отто.
- На основе информации, полученной на шаге 4, Отто просматривает все суммы в таблице 2 в поисках той, из которой только одно 2-разбиение имеет одну галочку в таблице 1B. Желаемый может иметь только одну галочку, иначе Сью не смогла бы знать X и Y. точно Наконец, Отто приходит к искомой сумме, которая также оказывается единственной, обладающей этими свойствами, что делает исходную задачу разрешимой с единственным решением. Задача Отто теперь выполнена.
Решение
[ редактировать ]В решении X и Y равны 4 и 13, причем P изначально знает, что произведение равно 52, а S знает, что сумма равна 17.
Изначально P не знает решения, так как
- 52 = 4 × 13 = 2 × 26
и S знает, что P не знает решения, поскольку все возможные суммы до 17 в пределах ограничений дают одинаково неоднозначные продукты. Однако как только P узнает, что S считает, что для данного произведения существует несколько возможных решений, P может исключить 2 x 26, так как в этом случае сумма равна 28. Если бы S сказали, что 28, она не могла бы с уверенностью заявить, что P не Я не знаю значений, поскольку возможная пара будет 5 и 23, и если бы P сказали, что сумма равна 5 x 23, то эти два числа являются единственным возможным решением.Итак, P теперь знает, что числа — 4 и 13, и сообщает S, что он знает эти числа. Благодаря этому S теперь знает, что из возможных пар, основанных на сумме (а именно 2+15, 3+14, 4+13, 5+12, 6+11, 7+10, 8+9), только одна имеет продукт, который позволил бы P вывести ответ: 4 + 13.Тогда читатель сможет вывести единственно возможное решение, основываясь на том факте, что S смог его определить. Обратите внимание, что, например, если бы S сказали 97 (48 + 49), а P сказали 2352 (48 * 49), P смог бы вывести единственное возможное решение, но S не смог бы, поскольку 44 и 53 все равно были бы логически возможная альтернатива.
Другие решения
[ редактировать ] | Этот раздел нуждается в дополнительных цитатах для проверки . ( Август 2018 г. ) |
Проблема может быть обобщена. [2] Граница X + Y ≤ 100 выбрана весьма сознательно. Если изменить предел X + Y , количество решений может измениться. Для X + Y < 62 решения нет. На первый взгляд это может показаться нелогичным, поскольку решение X = 4, Y = 13 укладывается в границы. Но из-за исключения продуктов с коэффициентами, сумма которых равна числам между этими границами, больше не существует множества способов факторизации всех нерешений, что приводит к тому, что информация вообще не дает решения проблемы. Например, если не рассматривать X = 2, Y = 62, X + Y = 64, X · Y =124, то из 124 остается только одно произведение, а именно. 4·31, что дает сумму 35. Затем 35 исключается, когда S заявляет, что P не может знать множители произведения, чего не было бы, если бы была разрешена сумма 64.
С другой стороны, когда предел X + Y ≤ 1685 или выше, появляется второе решение X = 4, Y = 61. Таким образом, с этого момента задача неразрешима в том смысле, что больше не существует решения. уникальное решение. Аналогично, если X + Y ≤ 1970 или выше, появляется третье решение ( X = 16, Y = 73). Все эти три решения содержат одно простое число. Первое решение без простого числа является четвертым, которое появляется при X + Y ≤ 2522 или выше со значениями X = 16 = 2·2·2·2 и Y = 111 = 3·37.
Если условие Y > X > 1 изменить на Y > X > 2, существует единственное решение для порогов X + Y ≤ t для 124 < t < 5045, после чего существует несколько решений. При 124 и ниже решений нет. Неудивительно, что порог решения поднялся. Интуитивно понятно, что проблемное пространство стало «разреженным», когда простое число 2 больше не доступно в качестве множителя , создавая меньше возможных произведений X·Y из заданной суммы A. X Когда решений много, то есть при более высоких t , некоторые решения совпадают с решениями исходной задачи с Y > X > 1, например X = 16, Y = 163.
Если вместо этого условие X + Y ≤ t для некоторого порога t заменить на X·Y ≤ u , проблема меняет внешний вид. Решать становится проще, требуется меньше вычислений. Разумным значением для u может быть u = t · t /4 для соответствующего t, основанного на наибольшем произведении двух факторов, сумма которых t равна ( t /2)·( t /2). Теперь проблема имеет единственное решение в диапазонах 47 < t < 60, 71 < t < 80, 107 < t < 128 и 131 < t < 144 и не имеет решения ниже этого порога. Результаты для альтернативной постановки не совпадают с результатами исходной постановки ни по количеству решений, ни по содержанию.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Ганс Фройденталь , Новый архив математики, серия 3, том 17, 1969, стр. 152
- ^ Перейти обратно: а б Борн, А.; Хюркенс, CAJ; Вегингер, Дж.Дж. (2006). «Проблема Фрейденталя и ее последствия (Часть I)» (PDF) . Бюллетень Европейской ассоциации теоретической информатики, EATCS . 90 : 175–191.
- ^ Гарднер, Мартин (декабрь 1979 г.), «Математические игры: гордость задач, включая ту, которая практически невозможна», Scientific American , 241 : 22–30, doi : 10.1038/scientificamerican0979-22 .
Внешние ссылки
[ редактировать ]- «Невозможная проблема» , Торстен Силке
- Задача двух математиков на mathforum
- Задача о сумме и произведении в MathWorks Cody
- Контрольная сумма модели и произведение