WikiDer > Загадка суммы и произведения

Sum and Product Puzzle

В Загадка суммы и произведения, также известный как Невозможная головоломка потому что кажется недостаточно Информация для решения, является логическая головоломка. Впервые он был опубликован в 1969 г. Ганс Фройденталь,[1][2] и имя Невозможная головоломка был придуман Мартин Гарднер.[3] Загадка разрешима, хотя и нелегко. Подобных вариантов головоломок существует множество.

Головоломка

Икс и Y два разных целых числа больше 1. Их сумма не больше 100, и Y больше, чем Икс. S и P - два математика (и, следовательно, совершенные логики); S знает сумму Икс + Y и P знает продукт Икс × Y. И S, и P знают всю информацию в этом абзаце.

Происходит следующий разговор (оба участника говорят правду):

  • S говорит: "P не знает Икс и Y."
  • P говорит: "Теперь я знаю Икс и Y."
  • S говорит: "Теперь я тоже знаю Икс и Y."

Что Икс и Y?

Решение

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

Первоначально P не знает решения, так как

52 = 4 × 13 = 2 × 26

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

Объяснение

Проблема довольно легко решается, если прояснить концепции и перспективы. Вовлечены три стороны: S, P и О. S знает сумму X + Y, P знает продукт X · Y, а наблюдатель O не знает ничего, кроме исходной постановки задачи. Все три стороны хранят одну и ту же информацию, но интерпретируют ее по-разному. Тогда это становится информационной игрой.

Назовем разбиение числа А на два срока А = В + С 2-сплит. Нет необходимости в каких-либо дополнительных знаниях, таких как Гипотеза Гольдбаха или тот факт, что для продукта ДО Н.Э такого разбиения на 2 числа должно быть уникальным (т.е. нет двух других чисел, которые также при умножении дают тот же результат). Но с гипотезой Гольдбаха, а также с тем фактом, что P немедленно узнал бы X и Y, если бы их продукт был полупервичный, можно сделать вывод, что сумма x + y не может быть четной, так как каждое четное число может быть записано как сумма двух простых чисел. Тогда произведение этих двух чисел будет полупростым.

Шаг 1. S (Сью), P (Пит) и O (Отто) составляют таблицы всех продуктов, которые могут быть сформированы из двух частей сумм в диапазоне, то есть от 5 до 100 (Икс > 1 и Y> X требует, чтобы мы начали с 5). Например, 11 можно разделить на 2 + 9, 3 + 8, 4 + 7 и 5 + 6. Соответствующие продукты - 18, 24, 28 и 30, и игроки ставят галочки напротив каждого из этих продуктов в своих таблицах (Таблица 1). Когда они закончены, на некоторых числах нет отметок, на некоторых - одна, а на некоторых - больше одной.

Шаг 2. Сью теперь смотрит на свою сумму и все ее деления на 2. Она видит, что у всех 2-разбиений есть продукты, которые не являются уникальными, т.е. существует другая факторизация, которая представляет собой 2-разбиение некоторой другой возможной суммы. Она видит это в таблице на шаге 1, где все ее продукты отмечены более чем одной галочкой. Она понимает, что из-за этого Пит не сможет однозначно определить факторы. Икс и Y посмотрев на продукт (это потребовало бы, чтобы хотя бы один из продуктов-кандидатов имел только одну отметку). Таким образом она восклицает: «P не может знать Икс и Y». Когда Пит и Отто слышат это, они получают информацию о том, что ни один из продуктов, связанных с суммой Сью, не является уникальным. Перебирая возможные суммы одну за другой, Сью, Пит и Отто теперь могут, каждый отдельно, составить список всех подходящих сумм (Таблица 2). Таблица содержит те суммы, у которых все 2-разбиения имеют продукты, которые не являются уникальными, т.е. имеют более одной отметки в таблице 1. Сью, Пит и Отто создали таблицу сумм кандидатов (Сью, конечно, уже знает ее сумма, но необходимо проследить мышление Пита).

Шаг 3. Учитывая новую информацию в Таблице 2, Пит еще раз смотрит на свой продукт. Суммы всех возможных 2-разбиений его продукта, кроме одного, исчезли из таблицы 2 по сравнению со всеми числами от 5 до 100, которые с самого начала считались суммами. Единственное, что осталось, должно быть суммой двух скрытых чисел. Икс и Y чей продукт X · Y он знает. По сумме и произведению легко узнать отдельные числа, и поэтому он говорит Сью: «Теперь я знаю Икс и Y». Пит закончил и выходит из игры.

Шаг 4. Сью и Отто пересчитывают Таблицу 1, на этот раз подсчитывая только произведения 2-разбиений из сумм, которые находятся в Таблице 2, а не из всех чисел в диапазоне от 5 до 100, как в исходной Таблице 1. Эта обновленная таблица называется Таблицей 1Б. Сью смотрит на все произведения двух частей своей суммы и обнаруживает, что появляется только одно из них. ровно один раз в таблице 1B. Тогда это должно быть произведение Пита, и она может вывести два числа из их суммы и произведения так же легко, как и Пит. Таким образом, она говорит Отто (Пита уже нет), что «Теперь я также знаю Икс и Y». Сью тоже закончила и выходит из игры, остается только Отто.

Шаг 5. На основе информации, представленной на шаге 4, Отто просматривает все суммы в таблице 2 в поисках одной из которых только для одного разбиения на 2 имеется одна отметка в таблице 1B. У желаемого может быть только одна отметка, иначе Сью не смогла бы знать Икс и Y с уверенностью. Наконец, Отто приходит к желаемой сумме, которая также оказывается единственной, обладающей этими свойствами, что делает исходную проблему разрешимой с помощью единственного решения. Задача Отто теперь тоже выполнена.

Другие решения

Проблема может быть обобщена.[2] Граница Икс + Y ≤ 100 выбрано достаточно сознательно. Если предел Икс + Y изменяется, количество решений может измениться. За Икс + Y <62, решения нет. Сначала это может показаться нелогичным, поскольку решение Икс = 4, Y = 13 помещается в границу. Но за счет исключения продуктов с коэффициентами, которые суммируются с числами между этими границами, больше не существует нескольких способов факторизации всех нерешений, что приводит к тому, что информация вообще не дает решения проблемы. Например, если Икс = 2, Y = 62, Икс + Y = 64, Икс·Y= 124 не рассматривается, то остается только одно произведение 124, а именно. 4 · 31, что дает сумму 35. Затем 35 исключается, когда S заявляет, что P не может знать коэффициенты продукта, чего не было бы, если бы сумма 64 была разрешена.

С другой стороны, когда предел Икс + Y ≤ 1685 или выше, появляется второе решение Икс = 4, Y = 61. Таким образом, с этого момента проблема неразрешима в том смысле, что больше не существует единственного решения. Аналогично, если Икс + Y ≤ 1970 и выше появляется третье решение (Икс = 16, Y = 73). Все эти три решения содержат одно простое число. Первое решение без простого числа - это четвертое, которое появляется в Икс + Y ≤ 2522 или выше со значениями Икс = 16 = 2 · 2 · 2 · 2 и Y = 111 = 3·37.

Если условие Y > Икс > 1 заменяется на Y > Икс > 2, есть уникальное решение для порогов Икс + Y ≤ т для 124 < т <5045, после чего есть несколько решений. На уровне 124 и ниже решений нет. Неудивительно, что порог решения поднялся. Интуитивно понятно, что проблемное пространство стало «разреженным», когда простое число 2 больше не использовалось в качестве множителя. Икс, создавая меньше возможных продуктов X · Y от заданной суммы А. Когда есть много решений, то есть для более высоких т, некоторые решения совпадают с решениями исходной задачи с Y > Икс > 1, например Икс = 16, Y = 163.

Если условие Икс + Y ≤ т за какой-то порог т обменивается на X · Y ≤ ты вместо этого проблема меняет внешний вид. Становится проще решить с меньшими затратами на вычисления. Разумная стоимость для ты может быть ты = т·т/ 4 для соответствующего т на основе наибольшего произведения двух факторов, сумма которых равна т существование (т/2)·(т/ 2). Теперь задача имеет единственное решение в диапазонах 47 < т < 60, 71 < т < 80, 107 < т <128 и 131 < т <144 и нет решения ниже этого порога. Результаты альтернативной формулировки не совпадают с результатами исходной формулировки ни по количеству решений, ни по содержанию.

Смотрите также

Рекомендации

  1. ^ Ганс Фройденталь, Nieuw Archief Voor Wiskunde, Серия 3, Том 17, 1969, страница 152
  2. ^ а б Родился, А .; Hurkens, C.A.J .; Вегингер, Дж. Дж. (2006). «Проблема Фрейденталя и ее разветвления (Часть I)» (PDF). Бюллетень Европейской ассоциации теоретической информатики, EATCS. 90: 175–191.
  3. ^ Гарднер, Мартин (Декабрь 1979 г.), «Математические игры: гордость проблем, в том числе и задача, которая практически невозможна», Scientific American, 241: 22–30, Дои:10.1038 / scientificamerican0979-22.

внешняя ссылка