У профессора Снейпа 64 карточки, пронумерованные последовательными целыми числами от 2 до 65.…
Головоломка
У профессора Снейпа есть 64 карты, пронумерованные последовательными целыми числами от 2 до 65. Он выбирает две карты и делится их суммой с Гарри и их произведением с Драко. Далее следует блестящий обмен мнениями:
Гарри: «Я вижу, что ты не знаешь чисел».
Драко: «Теперь я знаю числа!»
Гарри: «Теперь я тоже знаю!»
Можете ли вы вывести числа на двух карточках?
Найдите время, чтобы подумать о проблеме. Если у вас есть идеи, попробуйте разработать алгоритм и написать программу для его решения.
Если вы просто хотите проверить ответ, прокрутите статью до конца.
Эту проблему на самом деле можно решить без компьютера. Это требует немного теории чисел, особенно концепции уникальной простой факторизации. Вот шаги.
Заявление 1
Гарри: «Я могу сказать, что ты не знаешь чисел».
Из трех сделанных утверждений это самое сложное для интерпретации.
Гарри полагается на две части информации:
- сумма чисел, которые он точно знает
- тот факт, что Драко знает только продукт
Из этих двух фрагментов информации Гарри делает вывод, что Драко не может однозначно идентифицировать пару чисел.
Если бы Драко смог вывести пару чисел, произведение должно было бы быть уникальным для одной пары целых чисел в наборе {2,3,4,…,65}. Давайте рассмотрим более простой пример, чтобы понять эти уникальные продукты.
Начнем с более простого примера
Скажем, у Снейпа были только карточки с номерами от 2 до 10. В таблице ниже перечислены все возможные продукты.
Большинство товаров уникальны. Полезно разделить эти уникальные продукты на несколько групп:
1. Произведение двух простых чисел (2 × 3 = 6, 3 × 5 = 15 и т. д.)
2. Куб простого числа (2 × 2² = 8, 3 × 3² = 27 и т. д.)
3. Число, все другие пары множителей которого содержат слишком большие множители (4 × 9 = 36, 5 × 10 = 50 и т. д.).
Теперь, учитывая, что Гарри знает, что продукт не уникален, что мы можем сказать о сумме?
Опять же, я думаю, что полезно перечислить суммы для футляра из 10 карт.
Суммы ведут себя гораздо более регулярно, чем произведения, с одинаковыми суммами, выстраивающимися по диагоналям таблицы.
Зная сумму, Гарри может ограничить возможные пары одной диагональю. Например, если сумма равна 9, Гарри может ограничить возможные пары до {2,7}, {3,6} или {4,5}. Но {2,7} оба являются простыми числами, а это означает, что Драко сможет идентифицировать числа. Если Гарри уверен, что Драко не знает чисел, сумма не может равняться 9.
Та же логика исключает любую сумму, для которой хотя бы одна пара на диагонали имеет уникальный продукт.
Другой пример: сумма не может быть равна 14, потому что пара {6,8} ее исключает. Все остальные пары множителей из 48, то есть {1,48}, {2,24}, {3,16}, {4,12}, содержат множитель, который больше, чем самая большая карта (10).
Теперь мы можем применить эту концепцию к исходной задаче с 64 картами.
Возможные пары, оставшиеся после утверждения 1
- Исключение всех сумм, которые могут быть выражены в виде суммы двух простых чисел, уже исключает большинство сумм. В частности, удаляет
- любая сумма, которая на 2 больше, чем простое число
- любая четная сумма (то, что все четные числа являются суммой двух простых, называется гипотезой Гольдбаха. Не буду вдаваться в доказательство, оно слишком длинное, чтобы уместиться на полях 😉)
2. Исключение кубов простых чисел удалит суммы 2 + 2² = 6, 3 + 3² = 12, 5 + 5² = 30 и т. д., но как только мы поймем, что все эти суммы равны, нам не нужно беспокоиться.
3. Исключение всех сумм с коэффициентом больше 64 удаляет все нечетные суммы больше 37. Чтобы понять, почему, возьмем, например, сумму 41. Это можно сделать из пары {4,37}. Эта пара множителей должна быть уникальной в данных картах, потому что любая другая пара множителей должна содержать кратное простому числу 37, что уже больше 65. Точно так же 43 можно составить из {6,37}, 45 можно составить из {8,37}, и применяется та же логика.
Возможные суммы, которые у нас остались, равны {11, 17, 23, 27, 29, 35, 37}.
Заявление 2
Драко: «Теперь я знаю числа!»
Из этого утверждения мы можем сделать вывод, что в пределах оставшихся возможных пар чисел произведение теперь должно быть уникальным.
Мы могли бы найти их, составив таблицу, как в примере ниже, но мы можем сэкономить время, рассмотрев это утверждение и следующее вместе.
Заявление 3
Гарри: «Теперь я тоже!»
Учитывая оставшиеся возможные пары чисел после операторов 1 и 2, теперь сумма должна быть уникальной.
Учитывая, что одинаковые суммы встречаются на одной диагонали, это означает, что должна быть диагональ только с одной оставшейся парой.
В сочетании с требованиями утверждений 1 и 2 должна быть одна диагональ с суммой в {11, 17, 23, 27, 29, 35, 37}, которая имеет только одну пару с уникальным произведением.
Это означает, что нам не нужно проверять каждую оставшуюся пару. Мы можем исключить всю диагональ, просто найдя по крайней мере 2 пары, у которых есть уникальный продукт.
Например, чтобы исключить сумму 11, мы можем заметить, что {2,9} и {4,7} имеют уникальные произведения.
Чтобы исключить сумму 23, мы можем заметить, что {4,19} и {7,16} имеют уникальные произведения. Обе эти пары имеют форму {2ⁿ, p}, где p — простое число. Произведение должно быть уникальным среди оставшихся пар, потому что любая другая пара факторов будет иметь два четных фактора, которые мы уже исключили в утверждении 1.
Используя этот шаблон, мы можем исключить сумму 27 из-за {8,19} и {11,16}.
Мы можем исключить сумму 29 из-за {4,23} и {13,16}.
Мы можем исключить сумму 35 из-за {4,31} и {16,19}.
Мы можем исключить сумму 37 из-за {8,29} и {5,32}.
Остается только сумма 17, для которой нам действительно нужно проверить все пары…
{2,15} имеет тот же продукт, что и {5,6}.
{3,14} имеет тот же продукт, что и {2,21}.
{4,13} является уникальным.
{5,12} имеет тот же продукт, что и {4,15}.
{6,11} имеет тот же продукт, что и {2,33}.
{7,10} имеет тот же продукт, что и {2,35}.
{8,9} имеет тот же продукт, что и {3,24} .
Отвечать
Цифры должны быть 4 и 13.
Что происходит с большим количеством карт?
Если вы написали программу и хотите ее проверить, попробуйте ту же задачу для случая, когда у Снейпа есть карты от 2 до 2022. В этом случае есть несколько решений. Вы можете публиковать решения или ссылки на код в комментариях. Я также опубликую решения после недели или около того.
