Четыре решения головоломок раскрывают разные способы угадать чьё-то скрытое число, имея невероятно мало информации. Комментарий Сохранить статью Прочитать позже
Введение
В нашей последней задаче «Insights» я предложил читателям разобраться, как работают некоторые фокусы. Речь идёт о фокусах, где фокусник каким-то образом угадывает ваши загаданное число или игральные карты. Но как фокусник может правильно определить, что у вас на уме, основываясь, казалось бы, на полном отсутствии информации? Как мы увидим ниже, секрет заключается в том, чтобы извлечь ровно столько информации, чтобы раскрыть тайну с помощью неумолимой логики математики.
Головоломка 1
Наша первая головоломка представляла собой элементарный арифметический трюк, подходящий для увлечения ребенка:
Попросите ребёнка задумать трёхзначное число, не называя его. Затем скажите, что вы отгадаете число, показав два его экземпляра рядом! Сначала попросите ребёнка умножить число на 7. Затем попросите его умножить ответ на 11. Наконец — и в этот момент можно изобразить сосредоточенность и произнести соответствующие магические фразы — попросите его умножить второй ответ на 13.
Если ребёнок всё сделал правильно, вы можете заметить, что его лицо озаряется улыбкой. Вопрос к вам или к ребёнку постарше: почему это работает?
Причина, как верно заметили многие читатели, в том, что 7 × 11 × 13 = 1001, а это именно то число, на которое вы фактически просите ребёнка умножить. То, что в результате получится копия исходного трёхзначного числа (например, 457), очевидно, если записать умножение обычным способом.
Информация, благодаря которой этот трюк сработал, заключается в том, что число трёхзначное. Как заметил Джордж, для четырёхзначного числа пришлось бы умножить на 73 и 137.
Головоломка 2
Есть два неизвестных числа от 2 до 9. Эти два числа могут включать в себя 2 или 9, и оба могут быть одним и тем же числом. S и P — два математика с идеальной логикой. S дана только сумма двух чисел, а P — только их произведение. И S, и P знают всё, что мы только что указали. Вот их последующий разговор.
С: Я не могу определить, что это за два числа.
П: Я тоже не могу.
С: Ага! Теперь я знаю, что это за два числа!
П: Я тоже!
На первый взгляд это похоже на магическое чтение мыслей — откуда они могли взять новую информацию для решения задачи? Сможете ли вы вычислить эти два числа (есть два варианта ответа)? Можете ли вы объяснить, как S и P это сделали?
Сначала мы составляем таблицу всех возможных сумм и произведений. Лучший способ сделать это — создать таблицу размером 8х8 с числами от 2 до 9 по обеим осям. В каждой ячейке мы можем указать как сумму, так и произведение, разделив их запятой, как впервые описал Дабед. Как показано ниже, нам нужно рассмотреть только одну треугольную половину этой таблицы, поскольку порядок чисел не имеет значения. Все пары чисел с одинаковой суммой выстраиваются вдоль одной диагонали, как показано стрелками.
Далее давайте рассмотрим каждое утверждение.
1. Когда S говорит, что не может определить, какие это числа, она имеет в виду, что полученная ею сумма может быть получена более чем одним способом из заданного диапазона чисел. В нашем списке есть четыре числа, сумма которых может быть получена только одним способом: 4 (2 + 2), 5 (2 + 3), 17 (8 + 9) и 18 (9 + 9). Их можно исключить из списка, и они выделены серым цветом на рисунке.
2. Когда P говорит, что он тоже не может их вывести, это означает, что данное ему произведение может быть получено более чем одним способом из заданного диапазона чисел. В списке произведений только пять чисел, которые могут быть получены более чем одним способом: 12 (2 × 6, 3 × 4), 16 (2 × 8, 4 × 4), 18 (2 × 9, 3 × 6), 24 (3 × 8, 4 × 6) и 36 (4 × 9, 6 × 6). Эти произведения выделены красным цветом. Все остальные можно отбросить.
3. Теперь S может вывести произведение. Это означает, что среди всех произведений, связанных с её суммой, всё ещё возможно только одно. Поэтому нам нужно рассмотреть каждую из диагоналей суммы и принять только те, у которых есть одно произведение, обозначенное красным цветом. Это справедливо для диагоналей сумм, равных 7, 9, 12 и 13 (показаны красными стрелками), для которых допустимыми произведениями являются 12, 18, 36 и 36 соответственно.
4. Теперь P может вывести сумму. Это возможно только в том случае, если его произведению соответствует одна сумма. Это не относится к числу 36, сумма которого может быть равна 12 или 13. Таким образом, единственными приемлемыми парами суммы и произведения являются (7, 12) и (9, 18), которые соответствуют парам исходных чисел (3, 4) и (3, 6) .
Обратите внимание, что хотя это требует от нас проделать довольно много работы, для S и P всё гораздо проще. Для первого решения (3, 4) S дана сумма 7. Она сразу понимает, что не может быть уверена в решении, потому что это может быть (2, 5) или (3, 4). Поэтому она говорит об этом в своём первом утверждении. Теперь у P есть произведение 12, поэтому он тоже не может быть уверен, является ли исходная пара (3, 4) или (2, 6). В этот момент S уверен, что пара — это (3, 4), поскольку P мог бы сказать, была ли это (2, 5), потому что её уникальное произведение равно 10. И это позволяет P тоже это выяснить, потому что (2, 6) находится на неприемлемой диагонали, на которой есть два красных произведения. Поэтому, когда S и P даны сумма и произведение, соответственно, одного из решений, они могут вывести уникальную пару чисел. С другой стороны, мы можем только вывести полный набор возможных решений, которые будут работать, не имея возможности указать, какие именно из них на самом деле есть у S и P.
Оба ответа (3, 4) и (3, 6) удовлетворяют условиям задачи и являются правильными. Читатель Дэмион Зандрюс, однако, выразил мнение, что существует только один правильный ответ (3, 4). Хотя технически это неверно, можно утверждать, что (3, 4) — лучший ответ. Как мы увидим в следующей головоломке, ответы в таких головоломках могут измениться, если увеличить верхний предел диапазона. Это оказывается именно так. Если мы просто увеличим верхний предел диапазона с 9 до 10, то (3, 4) останется решением, (3, 6) перестанет быть таковым, и возникнет совершенно новое решение. Таким образом, мы можем рассматривать (3, 4) как устойчивое решение нашей исходной задачи. Решения, подобные (3, 6), которые появляются и исчезают при изменении диапазона чисел, называются «фантомными решениями».
Следующие читатели правильно описали два решения этой головоломки: Дабед, Фабьен Фридли, Сет Коэн, Роб Корлетт и Джордж.
Головоломка 3
Снова два неизвестных числа, которые могут быть равны, но теперь они находятся в диапазоне от 2 до 70. Снова S дана только сумма двух чисел, а P — только их произведение. Вот как на этот раз происходит их диалог.
П: Я не могу определить, что это за два числа.
С: Я мог бы вам это сказать, хотя я тоже не могу вывести цифры.
П: Ага! Теперь я знаю, что это за два числа!
С: Я тоже!
Снова найдите два числа и объясните, как это сделали P и S. Используя принципы теории чисел, какое наименьшее количество случаев (сумм и произведений) вам придётся проверить вручную после разумного исключения?
На этот раз диапазон слишком широк, чтобы мы могли легко найти решение, используя метод, описанный для головоломки 2. Однако первое утверждение S даёт нам дополнительную подсказку, позволяющую сократить количество возможных случаев, которые необходимо рассмотреть. Обозначим сумму s как s, а произведение — как p, и будем систематически исключать варианты s, следуя следующим правилам.
1. Поскольку число P не может быть выведено из двух простых чисел, число p не может быть произведением двух простых чисел. Следовательно, число s не может быть суммой двух простых чисел. Здесь мы сталкиваемся с гипотезой Гольдбаха, пожалуй, самой известной недоказанной гипотезой в теории чисел. Гипотеза утверждает, что все чётные числа, большие 2, можно представить в виде суммы двух простых чисел. Хотя эта знаменитая гипотеза ещё не доказана окончательно, её истинность подтверждена для всех чётных чисел до 4 × 1018. Поскольку наш диапазон гораздо меньше этого, мы можем с уверенностью утверждать, что число s не может быть чётным .
2. Один из аспектов правила 1, который я назову правилом 2, заключается в том, что s не может быть суммой нечётного простого числа и 2, поскольку 2 — простое число. Например, s не может быть равно 9, которое является суммой 7, простого числа, и 2, которое также является простым числом, поскольку их произведение 14 можно разложить на множители только одним способом: 2 × 7. В этом случае P сразу бы узнал, что это за два числа.
3. Наконец, s не может быть равно или больше суммы 2 и наименьшего простого числа, большего половины верхней границы диапазона. При верхней границе диапазона 70 наименьшее простое число, большее половины 70 (35), равно 37. По этому правилу s не может быть больше или равно 39. Почему? Мы можем доказать это, начав с 39 и двигаясь вверх. Во-первых, по нашему правилу 2, s не может быть равно 39, что равно 37 + 2 (оба числа простые). Аналогично, s не может быть следующим нечётным числом 41, потому что это 37 + 4, что даёт произведение 37 × 4 = 148. Единственный другой способ разложить число 148 на множители — 74 × 2, но 74 больше нашего верхнего предела 70, потому что это удвоенное число, которое больше половины 70. Это верно для следующего нечетного числа, которое можно записать как 37 + 6, и для следующего, которое равно 37 + 8, и так далее… вплоть до 70. Обобщая, любое нечетное число больше 39 можно выразить как 37 + x, где x — четное, и такое число можно разложить на множители только как 37 × x, если мы хотим ограничиться числами меньше 70.
Используя указанные выше ограничения, мы можем сократить число возможных кандидатов на s до 11, 17, 23, 27, 29, 35 и 37, используя первые три утверждения, сделанные S и P. Это хорошо, но мы можем сделать лучше! Ключевым моментом является то, что для того, чтобы S сделал утверждение 4, должно быть единственное уникальное произведение p, которое дает сумму s. Теперь рассмотрим s = 11, что можно выразить как 3 + 8 или 3 + 23, а также как 7 + 4 или 7 + 22. Если P пришел к выводу, что s равно 11, он мог бы сделать это с ap, равным 24, рассуждая: «Числа могут быть 3 и 8, что дает 11, что допустимо, или 2 и 12, что дает 14, которое четно и не подходит по правилу 1, или 4 и 6, что дает 10, что также четно и, следовательно, не подходит»; или он мог бы иметь ap = 28 и рассуждать так: «Числа могли бы быть 7 и 4, что даёт 11, что допустимо, или 2 и 14, что даёт 16, что чётно и недопустимо». Таким образом, когда s = 11, у S нет способа определить, равно ли p 24 или 28. Это даёт нам четвёртое правило: сумма s не должна быть выражена в виде y + 2n, где y — нечётное простое число, более чем одним способом.
Рассматривая наши кандидаты на роль s, мы видим, что 11 уже исключено из рассмотрения выше. Также исключены 23 (19 + 4 и 7 + 16), 27 (23 + 4, 19 + 8 и 11 + 16), 35 (31 + 4, 19 + 16 и 3 + 32) и 37 (29 + 8 и 5 + 32). Остаются только 17 и 29 в качестве возможных сумм, и нам нужно вручную проверить всего 20 произведений. Таким образом, мы можем исключить 29, поскольку 13 + 16 — возможное решение, как и 25 + 4, и для S должно быть только одно решение, чтобы сделать своё второе утверждение.
Возможные варианты для s из 17 перечислены в таблице ниже. В первом столбце указана пара чисел-кандидатов, а во втором столбце — произведение p, которое было бы дано P. На основе этого P мог бы придумать возможные альтернативные пары, отличные от пары-кандидата. Они показаны в столбце 3. Затем в столбцах 4 и 5 мы имеем P, проверяющего, является ли сумма для этих альтернативных пар допустимой, как определено выше (то есть она должна быть одной из 11, 17, 23, 27, 29, 35 и 37). Если хотя бы одна из альтернативных пар получает Y в столбце 5, P не может сказать, что он знает числа (столбец 6), потому что вместе с парой в столбце 1 это составило бы две допустимые пары. Как показано, есть только одна пара, 4 и 13, у которой нет других «Y» в столбце 5, и это единственное решение головоломки.
В исходном условии этой головоломки верхний предел был ошибочно установлен равным 50, и решения не было. Dabed, Jeff L, toma&co., Fabien Friedli и Rob Corlett – все указали на это. Можно спросить: почему 4 и 13 не являются решением в этом случае? Ответ заключается в том, что, как мы видели в правиле 3 выше, 35 и 37 не входят в допустимый список для s в диапазоне 50, потому что они больше 31 (суммы 2 и 29, наименьшего простого числа, большего 25). Таким образом, и (6, 11), и (7, 10) не будут иметь Y в столбце 4. Следовательно, для s, равного 17, будет более одного решения, и S не сможет сказать, что знает эти числа.
Читатели Дэбед, Роб Корлетт, Фабьен Фридли и Джордж предложили полное решение этой головоломки. Корлетт, Фридли и Джордж также отметили её связь с гипотезой Гольдбаха. Эта головоломка называется задачей Фрейденталя в честь голландского математика немецкого происхождения Ганса Фрейденталя, опубликовавшего первую подобную задачу в 1969 году. Мартин Гарднер популяризировал её как «невозможную головоломку», потому что на первый взгляд кажется, что в ней слишком мало информации для её решения. После публикации в журнале Quanta я получил электронное письмо от инженера Boeing Мэтью Томаса, который проектирует истребители и использует эту задачу, чтобы научить молодых инженеров важности продумывания задач в, казалось бы, экстремальных обстоятельствах — часто необходимого в его области!
Головоломка 4
«Математик-маг» подготавливает колоду из 32 карт, отбрасывая карты от 2 до 6. Она раскладывает оставшиеся карты в определённом порядке и кладёт колоду рубашкой вверх на стол. Пять человек случайным образом выбираются для игры. Каждый из них по очереди снимает колоду. Затем первый берёт верхнюю карту и передаёт её второму, который берёт верхнюю карту, и так далее по порядку. После того, как каждый игрок разберёт по карте, последний кладёт колоду обратно на стол рубашкой вниз, и все возвращаются на свои места.
Теперь артистка просит пятерых человек телепатически передать ей свои карточки. Её лицо сосредоточенно хмурится. Наконец она смиренно качает головой. «В последнее время это становится всё сложнее», — говорит она. «Расширение Вселенной вызывает красное смещение, которое искажает цвета, которые я получаю. Пожалуйста, встаньте, у кого красные карточки».
Второй и пятый участники встают. На лице математика-мага появляется облегчение. «Теперь всё ясно», — говорит она. «У тебя десятка червей и король бубен». И действительно. Она продолжает угадывать карты остальных троих.
Как ей это удалось? Подсказка: рассмотрим последовательность 00010111. Она содержит циклически все восемь возможных троек, образованных из нуля и единицы: 000, 001, 010, 101, 011, 111, 110 и 100. Что произойдёт, если «разрезать» её, как колоду карт?
Была ли шутка артиста на сцене всего лишь театральной постановкой или она была неотъемлемой частью трюка?
Вот решение, описанное Джорджем:
Последовательность 00010111 называется последовательностью де Брейна порядка 3 от 0 и 1. Разрезание ее как колоды карт эквивалентно циклическому перебиранию ее некоторое количество раз, и она сохраняет свойство содержать все возможные триплеты 0 и 1. Мы можем построить аналогичную последовательность для всех возможных групп из 5 B и R — например, BBBBBRBBBRRBBRBRBBRRRBRBRRBRRRRRRR и она будет иметь длину 25 = 32 цифры, что совпадает с количеством карт, которые у нас есть, — и расположить карты так, чтобы каждая B в последовательности де Брейна соответствовала черной карте, а каждая R — красной. Каждая комбинация B и R встречается ровно один раз, поэтому, как только вы узнаете, где находятся красные карты (в примере 2-я и 5-я), вы будете знать всю последовательность из пяти карт (BRBBR). Затем просто (!) запоминайте порядок карт, пока не найдете пять, которые образуют эту серию, и у вас будет ответ. Подшучивание необходимо для того, чтобы найти красные позиции и зафиксировать, какой набор из пяти карт был вытащен (хотя, очевидно, вместо этого вы можете показать черные карты).
Правильно!
Что касается порядка карт, вы можете использовать любой, который вам легко запомнить. Вот видео на YouTube с этим карточным фокусом, где используется последовательность де Брейна 4-го порядка с 16 картами.
Эта головоломка — один из многих карточных фокусов, основанных на математике, из книги «Волшебная математика: математические идеи, оживляющие великие фокусы» знаменитых фокусников-математиков Перси Диакониса и Рона Грэма. Читатели Дабед, Фабьен Фридли, Роб Корлетт и Джордж предложили решение этого фокуса, а последние трое обнаружили его зависимость от последовательности де Брейна, названной в честь другого голландского математика, Николаса де Брейна.
Последовательность де Брейна широко используется в различных типах кодирования, как вы можете себе представить, и, что удивительно или, возможно, неизбежно, она находит применение в попытках построить генетические сборки с использованием генетического кода ДНК.
Спасибо всем, кто внёс свой вклад в решение этих увлекательных головоломок. Некоторые работы были очень качественными, и как минимум четыре человека достойно разгадали их. Но приз может быть присужден только один — Дабеду, который первым обратил внимание на то, что головоломка 3 в заявленном виде не имеет решения, и проиллюстрировал «диагональный метод» решения головоломок типа Фрейденталя.
Увидимся в следующий раз для новых идей!
Источник: www.quantamagazine.org
