Математические головоломки профессора Стюарта Стюарт Иэн
– Нет.
– Настаивали ли вы, что эти цифры должны непременно разделяться пробелом?
– Может быть, мой рисунок и выглядит неоднозначно, но я ничего не говорил о пробеле.
– Я так и думал. Удовлетворит ли это вашим условиям? – и Ватсап написал:
49.
– Что равняется 7.
Геомагические квадраты
Какую форму имеет апельсиновая кожура?
См. Laurent Bartoldi and Andr Henriques. Orange peels and Fresnel integrals, Mathematical Intelligencer 34 No. 4 (2012) 1–3.
Статья доступна на сайте: www.arxiv.org/abs/1202.3033
Как выиграть в лотерею?
Нет, это неверно. Все утверждения, сделанные по ходу дела, верны, но вывод ошибочен.
Чтобы понять почему, рассмотрим лотерею, которая проводится еженедельно в небольшой известной провинции Лиллипутии. Шаров здесь всего три – 1, 2, 3 – и вынимаются два из них. Вы выигрываете, если заранее правильно называете эти два шара.
Существует три возможных результата розыгрыша:
12 13 23,
и все они равновероятны.
Первым числом является 1 с вероятностью 2/3 (это максимальная вероятность), 2 с вероятностью 1/3 или 3 с вероятностью 0.
Второе число – это 3 с вероятностью 2/3 (максимальная вероятность), 2 с вероятностью 1/3 или 1 с вероятностью 0.
Таким образом, по той же логике игрокам, чтобы максимально увеличить свои шансы, следует выбирать 13. Однако на самом деле все три варианта равновероятны, так что это попросту чепуха.
В общем и целом 1 с большей вероятностью окажется наименьшим числом в розыгрыше, поскольку в этом случае чисел, превышающих заданное число (то есть единицу), больше, чем в любом другом случае. А вовсе не потому, что единица может быть вытащена с большей вероятностью, чем какое бы то ни было другое число. Тот же эффект действует и в отношении других позиций, но не настолько очевидно.
КражаСлучай с зелеными носками
– Глубокое знание лондонского преступного мира позволяет мне сразу же определить, кто злодей, – объявил Сомс.
– Кто?
– Это не имеет значения, пока у нас нет формальных доказательств его вины, Ватсап. Только доказательства способны убедить инспектора Роулейда из лондонской полиции, когда мы представим ему свои выводы. Во-первых, мы должны составить список возможных способов распределения цветов одежды между подозреваемыми.
– Это я могу, – сказал Ватсап. – Я немного владею элементарной комбинаторикой. Она весьма полезна, когда нужно определить, какую конечность ампутировать первой.
И он написал:
КЗБ КБЗ ЗКБ ЗБК БКЗ БЗК
– Буквы обозначают цвета предметов одежды в следующем порядке: пиджак, брюки, носки, – объяснил Ватсап. – Цвета нигде не повторяются, потому что об этом говорят свидетели, так что возможные варианты сводятся к данным перестановкам этих трех букв.
– Очень хорошо, – сказал Сомс. – И каким же должен быть наш следующий шаг?
– Э-э… составить таблицу всех способов распределения предметов одежды между тремя мужчинами. На это потребуется некоторое время, Сомс, поскольку сочетаний существует… э-э, 6 5 4… 120 штук.
– Не так, Ватсап. Подумав немного, мы сможем с самого начала исключить большинство сочетаний. Сосредоточимся для начала только на одном подозреваемом – скажем, на Джордже Грине. Предположим, к примеру, что Грин носит зеленый пиджак, коричневые брюки и белые носки: случай ЗКБ.
– Уф, но так ли это на самом деле?
– Это мое предположение, которое позволяет рассуждать дальше. Если мое предположение верно, из этого следует, что никто из остальных двух подозреваемых не может носить зеленый пиджак, или коричневые брюки, или белые носки, ведь только один из трех предметов каждого рода может быть заданного цвета. Так что для этих двоих мы можем исключить варианты ЗБК, КЗБ и БКЗ из оставшихся пяти возможных вариантов. Это оставляет нам только варианты КБЗ и БЗК. Которые, обратите внимание, представляют собой циклические перестановки варианта ЗКБ. Мы можем распределить эти варианты между Биллом Брауном и Уолли Уайтом только двумя способами, – Сомс начал заполнять таблицу.
– Но, Сомс, – воскликнул Ватсап, – может быть, Джордж Грин не носит одежду цветов ЗКБ!
– Вполне возможно, – невозмутимо ответил Сомс. – Это всего лишь две верхние строки моей таблицы. Я могу провести аналогичные рассуждения для пяти остальных вариантов одежды Джорджа Грина. Разумеется, при этом перестановки тоже получатся циклическими. Внесем в таблицу все 12 возможных вариантов.
Ватсап скопировал себе в блокнот итоговую таблицу (см. ниже).
Когда он закончил, Сос кивнул.
– А теперь, мой дорогой Ватсап, нам остается только исключить невозможные комбинации при помощи имеющихся у нас данных…
– Потому что в результате то, что останется, каким бы невероятным оно ни казалось, должно быть истиной! – воскликнул Ватсап.
– Я и сам не сумел бы сказать лучше. Хотя в данном случае самое невероятное – это то, что только один из этих негодяев оказался замешан в вашем деле. Я скорее ожидал бы сговора. В любом случае, констебль Уаггинс – достойный человек, Ватсап, и хватка у него железная. Недостаток воображения он компенсирует настойчивостью. Так вот, он заявил, что носки у Брауна были того же цвета, что пиджак у Уайта. Это означает, что тройка букв Брауна должна оканчиваться той же буквой, какой начинается тройка Уайта. Это позволяет исключить строки 1, 3, 5, 7, 9 и 11 и уменьшает нашу таблицу до следующего состояния:
– Далее я определяю, какие комбинации в ней соответствуют второму условию достойного констебля: тому, что человек, фамилия которого соответствует цвету брюк Уайта, был в носках, цвет которых не соответствовал фамилии человека в белом пиджаке. Чтобы понять это, нужно просто посмотреть внимательно. К примеру, в четвертой строке на Уайте коричневые брюки, что соответствует фамилии Браун. Носки у Брауна белые. Отличается ли при этом цвет пиджака Уайта от белого? Нет, пиджак на нем как раз белый. Убираем строку 4.
– Не уверен, что я до конца…
– Ну, хорошо, позвольте мне составить другую таблицу! – и Сомс написал:
– Остаются только строки 2 и 8. Что снова уменьшает нашу таблицу до вида:
– Наконец, констебль Ваггинс говорит нам, что цвет пиджака человека, чья фамилия соответствует цвету носков Грина, отличается от цвета брюк Брауна.
– Это позволяет исключить строку 8. Остается строка 2.
– Таким образом, нам остается только посмотреть, кто носил зеленые носки в строке 2. Как я и подозревал с самого начала, это был Уолли Уайт, одетый по схеме КБЗ.
Последовательные кубы
23 + 24 + 25 = 12 167 + 13 824 + 15 625 = 41 616 = 204.
Эти числа можно найти простым перебором. Систематический метод состоит в том, чтобы обозначить среднее число n и записать, что (n – 1) + n + (n + 1) = 3n + 6n = m для некоторого числа m. Таким образом, m = 3n (n + 2). Множители 3, n, n + 2 не имеют общих делителей, кроме, может быть, чисел 2 и 3. Поэтому любой простой делитель больше 3 должен присутствовать как в n, так и в n + 2 в четной степени (возможно, нулевой). Первые два числа, удовлетворяющие этому условию, – это 4 и 24, причем 24 является решением, а 4 не является.
Adonis Asteroid Mousterian
Буквы соответствуют следующим числам:
квадрат 3 3: A = 0, D = 3, I = 2, N = 0, O = 1, S = 6;
квадрат 4 4: A = 0, D = 12, E = 1, I = 2, N = 0, O = 3, S = 0, T = 4;
квадрат 5 5: A = 0, E = 1, I = 2, M = 0, N = 5, O = 3, R = 10, S = 15, T = 20, U = 4.
Теперь квадраты выглядят так:
Про магические квадраты и подобные конструкции см.: Jeremiah Farrell, Magic square magic, Word Ways 33 (2012) 83–92.
Статья доступна на сайте: http://digitalcommons.butler.edu/wordways/vol33/iss2/2
Два коротких вопроса на квадраты
1. 923 187 456, квадрат числа 30 384.
Поскольку нам нужно наибольшее число такого типа, можно смело предположить, что ответ начинается с 9, так что на самом деле этот вариант следует опробовать первым, даже если наше предположение окажется неверным. Таким образом, искомое число должно лежать между 912 345 678 и 987 654 321; следует также помнить, что все цифры различны и что нуля среди них нет. Квадратные корни из граничных чисел равны 30 205,06 и 31 426,96. Все, что нам остается сделать, – это проверить числа от 30 206 до 31 426 и посмотреть, какое из них даст нам ответ из девяти разных цифр. В этом интервале лежит 1221 число. Начав с числа 31 426 и продвигаясь в обратном направлении, мы рано или поздно доберемся до числа 30 384. Теперь, когда мы нашли решение задачи, начинающееся с цифры 9, нам не стоит волноваться о числах, начинающихся с 8 и остальных цифр.
2. 139 854 276, квадрат числа 11 826.
Ищется это число аналогичным способом.
Дело о картонных коробках
1. Размеры коробок составляли 6 6 1 и 9 2 2.
Пусть размеры коробок равны x, y, z и X, Y, Z. Тогда их объемы равны xyz и XYZ. Длина ленты равна 4 (x + y + z) и 4 (X + Y + Z). Исключив общий множитель 4, получим уравнения, которые необходимо решить:
xyz= XYZ
x + y + z = X + Y + Z
в ненулевых целых числах. То есть нужно найти две тройки чисел, произведение и сумма которых взаимно одинаковы. Наименьшее решение равно (x, y, z) = (6, 6, 1) и (X, Y, Z) = (9, 2, 2). Произведение равно 36, сумма равна 13.
2. Наименьшее решение для трех коробок равно (20, 15, 4), (24, 10, 5) и (25, 8, 6). Теперь произведение равно 1200, а сумма – 39.
По ходу дела мы можем ответить и на третий вопрос, который не фигурировал в расследовании Сомса.
3. Что, если коробки перевязаны лентами, как обычно (как на левом рисунке), где x – ширина, y – глубина, а z – высота? Тогда уравнения примут вид:
xyz = XYZ
x + y+ 2z = X + Y + 2Z.
Если мы заменим x, y, z на x, y, 2z и аналогично для X, Y, Z, то получится, что мы снова ищем тройки чисел с одинаковыми произведением (теперь это 2xyz = 2XYZ) и суммой. Однако при этом числа z и Z должны быть четными.
Это условие выполняется в решении (1), если мы расставим длины сторон в нужном порядке, что позволит нам получить наименьшее решение (6, 1, 3) и (9, 2, 1).
Мое внимание к этой задаче привлек Молой Де из Калькутты (Индия), нашедший также наименьшие наборы из четырех, пяти и шести чисел с одинаковыми произведениями и суммами.
Четыре набора:
(54, 50, 14) (63, 40 15) (70, 30, 18) (72, 25, 21)
Сумма = 118, произведение = 37 800.
Пять наборов:
(90, 84, 11) (110, 63, 12) (126, 44, 15) (132, 35, 18) (135, 28, 22)
Сумма = 185, произведение = 83 160.
Шесть наборов:
(196, 180, 24) (245, 128, 27) (252, 120, 28) (270, 98, 32) (280, 84, 36) (288, 70, 42)
Сумма = 400, произведение = 846 720.
RATS-последовательность
Следующий член последовательности – 1345.
Правило зашифровано аббревиатурой RATS и выглядит так: Reverse, Add, Then Sort («Перевернуть, сложить, затем сортировать»). Под «сортировать» подразумевается «расставить цифры в порядке возрастания». Любые нули при этом отбрасываются. К примеру:
16 + 61 = 77, порядок получается правильный;
77 + 77 = 154, переставляем цифры – получаем 145;
145 + 541 = 686, переставляем цифры – получаем 668;
668 + 866 = 1534, переставляем цифры – получаем 1345.
Джон Хортон Конвей предположил, что, с какого бы числа вы ни начали, со временем эта последовательность либо войдет в повторяющийся цикл, либо превратится в бесконечно возрастающую последовательность
123n4444 556n7777 123n+14444 556n+17777 …,
где n обозначает не n-ю степень, а n одинаковых цифр подряд.
Математические даты
Следующий тройной палиндром будет 21:12 21/12 2112.
Следующий простой палиндром был 20:02 30/03 2002.
Собака Баскетболлов
– В самом деле, мадам, доктор Ватсап прав, – подтвердил Сомс. – Достаточно сообразить, что сдвинуто было всего четыре шара, и требуемая расстановка шаров становится очевидной.
– Но какая же это расстановка?
– Эту информацию, мадам, согласно вашему же собственному заявлению, мы можем раскрыть только старшему ныне живущему мужчине в роду.
– А именно лорду Эдмунду Баске, – уточнил я, – который в настоящий момент находится в коме. Что делает нашу задачу весьма слож…
– Чепуха! – заявила леди Иакинф. – Вы можете сказать мне все.
По ее лицу было очевидно, что ничто на свете не заставит ее свернуть с избранного пути.
– Очень хорошо, – сказал Сомс, делая быстрый набросок. – Должно быть, пуд… э-э, гигантская слюнявая псина… сдвинула четыре каменных шара, изображенных здесь белым цветом, на позиции, обозначенные черным. Или, может быть, все произошло в соответствии с одной из двух других схем, которые возникают при повороте данного решения. Но вы сказали, что ориентация этой структуры не имеет значения.
Теперь я понял смысл загадочного вопроса, заданного им немного раньше.
– Чудесно! – обрадовалась леди Иакинф. – Я велю Вилликинсу поставить их обратно.
– Но разве это не нарушит условий церемонии? – поинтересовался я.
– Разумеется, доктор Ватсап. Но у нас нет никаких рациональных причин бояться каких бы то ни было неблагоприятных последствий. Этот древний запрет – лишь проявление старого… э-э… суеверия.
Месяцем позже Сомс вручил мне номер газеты Manchester Garble[36].
– Господи Боже! – воскликнул я. – Лорд Баске умер, а Баскет-холл выгорел дотла! Страховая компания, в которой было застраховано семейство, отказало в выплате, потому что действия Вредоносных сил абсолютного зла не подпадают под страховой случай. Род Баске разорен! Леди Иакинф помещена в лечебницу для неизлечимых душевнобольных!
Сомс кивнул.
– Чистое совпадение, я уверен, – сказал он. – Сейчас, задним числом, ясно, что мне, может быть, следовало сказать леди Иакинф насчет пуделя.
Цифровые кубы
370, 371 и 407.
Несмотря на то что эта задача вроде бы не имеет никакого математического значения, нужно обладать хорошими знаниями математики, чтобы найти все четыре ее решения, и очень хорошими, чтобы доказать, что других решений не существует.
Я попробую кратко описать один из возможных подходов.
Поскольку числа с начальными нулями исключаются, нам остается проверить всего 900 возможных комбинаций. Но их количество можно сократить. Кубы всех десяти цифр равны 0, 1, 8, 27, 64, 125, 216, 343, 512 и 729. Сумма трех кубов составляет не более 999, поэтому можно заранее исключить числа, содержащие две девятки, две восьмерки, восьмерку и девятку и т. д.
Предположим, одна из цифр – это нуль. Тогда искомое число представляет собой сумму двух кубов из нашего списка. Из 55 подобных пар лишь две, 343 + 27 = 370 и 64 + 343 = 407, обладают нужным свойством.
Далее мы можем считать, что ни одна из цифр числа не равна 0. Предположим, одна из них равна 1. Аналогичные вычисления дают нам 125 + 27 + 1 = 153 и 343 + 27 + 1 = 371.
Теперь мы можем считать, что ни одна из цифр не равна ни 0, ни 1. Список кубов, с которыми можно дальше работать, при этом немного сокращается. И т. д.
Кое-какие уловки, к примеру учет четности или нечетности чисел, также помогают сократить объем вычислений. Этот довольно медленный, но систематический подход – а Сомс рекомендует ко всему подходить систематически – приводит нас к результату без каких бы то ни было серьезных препятствий на пути.
Самовлюбленные числа
Здесь мы разрешим начальные нули:
четвертые степени: 0000 0001 1634 8208 9474;
пятые степени: 00000 00001 04150 04151 54748 92727 93084.
Без улик!
– Сомс! – воскликнул я. – Я ее решил!
– Да, убийца – графиня Лизелотта фон Финкельштейн, она ехала верхом на своем чистокровном жеребце по кличке Князь Игорь и вела в поводу трех упряжных лошадей, чтобы замаскировать следы на…
– Нет-нет, Сомс, речь не о вашем деле! Я о задаче!
Он бросил короткий взгляд на решение, которое я нацарапал на полях газеты.
– Верно. Случайное попадание, без сомнения.
– Нет, Сомс, я вывел его путем логических рассуждений на основе принципов, которые вы вложили в мою голову. Во-первых, я понял, что сумма чисел в каждой области должна равняться 20.
– Потому что полная сумма чисел во всех ячейках составляет (1 + 2 + 3 + 4) 4 = 40 и ее следует поделить поровну между двумя областями, – не задумываясь отозвался Сомс.
– Именно. Далее, как только я решил сосредоточиться на большей области, решение начало складываться. В этой области четыре клетки в нижней строке – там должны быть числа 1, 2, 3, 4, расположенные в каком-то порядке; каким бы ни был порядок, сумма этих чисел равна 10. Так что оставшиеся три строки все вместе в сумме тоже должны дать 10. Единственный способ этого добиться – поставить в верхнюю строку числа 1, 2, 3 в каком-то порядке, а во вторую строку – 1 и 2 в каком-то порядке; третья строка в любом случае должна содержать 1.
– Почему?
– Любое другое число на этом месте сделает сумму слишком большой.
– Вы в самом деле учитесь, Ватсап. Очень хорошо: продолжайте.
Я улыбнулся в ответ на эту слабую похвалу, ведь услышать хоть какую-нибудь похвалу из уст Сомса не легче, чем выжать воду из камня.
– Ну, хорошо… теперь несложно проверить, что способ правильного заполнения ячеек только один. Числа во второй области расставляются вынужденно: так, в крайней правой клетке верхней строки должна стоять четверка, а затем четверки должны идти вниз по диагонали; затем две тройки также вынужденно встают на свои места, и, наконец, две двойки занимают оставшиеся пустыми клетки.
Эту задачу придумали Джерард Баттерс, Фредерик Хенле, Джеймс Хенле и Колин МакГоги, а опубликована она в журнале The Mathematical Intelligencer 33 No. 3 (Fall 2011) 102–105. См. также на сайте: http://www.math.smith.edu/~jhenle/clueless/
Краткая история судоку
Приведем два принципиально разных решения головоломки Озанама:
Не забывайте: каждое из этих решений путем перестановок достоинств и мастей порождает 576 родственных решений, поэтому не удивляйтесь, если ваши решения выглядят не так, как приведенные. Если вы начинаете с ряда A K Q J (или можете привести свое решение в такую форму), вам достаточно подумать только о том, как преобразовать остальные три ряда.
Раз, два, три
Дело о четырех тузах
– Все это просто трюк, Ватсап. При надлежащей подготовке он работает автоматически, какую бы последовательность складывания ни выбрали зрители.
– Чертовски умно, да? – заметил я.
Сомс хмыкнул.
– Когда Гудунни готовил колоду, он поместил тузы на 1 = e, 6, 11 и 16-е места, если считать сверху вниз. Поэтому, когда из колоды выложили квадрат, тузы легли вдоль диагонали из верхнего левого угла в правый нижний. Но лежали они рубашкой кверху, поэтому вы, разумеется, и не подозревали о подвохе.
– Представьте себе, что получится, если перевернуть диагональные карты лицом кверху. Тогда весь квадрат будет выглядеть как шахматная доска с тузами вдоль большой диагонали:
– Так вот, такой расклад обладает замечательным математиеским свойством. Как бы вы ни складывали квадратное поле, на любом этапе карты, которые оказываются в результате на определенной позиции, будут смотреть лицом в одну и ту же сторону: либо вверх, либо вниз.
– Правда?
– Давайте попробуем. К примеру, мы могли бы начать со складывания вдоль центральной вертикальной линии. Представьте, как лягут при этом карты верхнего ряда. Третья (смотрит вверх) переворачивается (и смотрит вниз) и ложится сверху на вторую карту – она заранее лежит лицом вниз. Четвертая карта (вниз) тоже переворачивается (вверх) и ложится сверху на первую (тоже вверх).
Я начал смутно понимать, как все это работает.
– То же самое происходит и с остальными рядами?
– Точно. После первого складывания образуется прямоугольник из карт или маленьких стопочек карт. Карты в каждой стопочке смотрят в одну сторону (вверх или вниз), а весь набор стопочек имеет тот же вид шахматной доски, где чередуются карты лицом вверх и карты лицом вниз, как в первоначальном раскладе. Поэтому ровно то же самое происходит и при следующем складывании, и при следующем. К тому моменту, когда у нас образуется единая стопка, все карты в ней окажутся повернутыми лицом в одну сторону.
– Да, но ведь когда мы начинали, карты на диагонали лежали не той стороной, которая нужна для шахматного порядка, – заметил я.
Этой фразой я, откровенно говоря, хотел возразить Сомсу, но он буквально просиял от моей догадливости.
– Вот именно! Поэтому после складывания они снова лягут не той стороной. Поэтому вместо стопки из 16 карт, сложенных лицом в одну сторону, получится стопка из 12 карт, повернутых в одну сторону, и 4 – в другую.
Чертовски изобретательно!
Шахматный расклад обладает свойством, которое математики называют «цветовой симметрией». Линии складывания работают как зеркала, и зеркальное отражение каждой карты ложится на карту, которая смотрит в противоположную сторону. Эта идея используется при изучении расположения атомов в кристаллах. Изобретательность здесь проявилась в том, что математику превратили в эффектный карточный фокус. И сделал это не Гудунни. Он, по обыкновению, просто стащил этот фокус у его изобретателя Артура Бенджамина – математика и иллюзиониста из колледжа Харви Мадда в Калифорнии.
Парадокс с зигзагом
Ни одна из представленных фигур не является треугольником. У первой «гипотенуза» слегка выпирает вверх, у второй – слегка уходит вниз. Именно в этом месте скрывается недостающий квадратик.
Дверца страха
Сомс удовлетворенно кивнул.
– Я понял, Ватсап, как надо! Ветрянка выходит, Геморрой выходит, Аневризма выходит, Ветрянка возвращается внутрь, Ботулизм выходит, Ветрянка выходит.
Мы начали деликатный процесс выманивания кошек через кошачью дверцу и запихивания их обратно внутрь.
– Осторожно, Сомс! – прошептал я. – Одна ошибка, и весь этот район превратится в дымящуюся воронку. Я пока не хочу предстать перед райскими вратами, да и кошек своих туда отправлять тоже не хочу. На мне брюки неглаженные, да и кошек неплохо бы причесать.
– Не беспокойтесь, Ватсап, – отозвался Сомс, хватая Ветрянку, пока несчастное животное не успело сигануть через изгородь. – Мое решение верно, не сомневайтесь.
– Я и не сомневаюсь в вашем решении, Сомс, – ответил я, лихорадочно пытаясь отыскать рядом что-нибудь прочное, за чем можно было бы спрятаться. – Э-э… а как вы пришли к этим выводам?
Он позаимствовал у меня блокнот и карандаш.
– Существует 16 возможных вариантов того, какие из кошек находятся в доме: АБВГ, АБВ, АБГ и т. д. вплоть до полного их отсутствия (обозначим это состояние *). Стрелкой обозначим возможный переход от состояния к состоянию: он соответствует проходу одной кошки сквозь дверцу в ту или другую сторону.
– Первое условие исключает из числа возможных состояния АВ и АБВ. Второе исключает БГ и БВГ. Третье исключает АГ. Четвертое условие исключает ВГ. Пятое исключает переход А *. Шестое исключает переход Б *.
Я понял, что рассказ будет длинным.
– Далее, АБВГ АВГ или АБГ. Однако АВГ АВ, АГ или ВГ, а все эти комбинации исключены. Поэтому АБВГ АБГ. Поскольку АБГ АГ и АБГ БГ исключены, мы должны принять АБГ АБ. Но АБ А бессмысленно, потому что А не в состоянии выйти наружу, если никого рядом нет. Так что АБ Б. Однако Б после этого не может выйти, поэтому какая-то другая кошка должна будет войти. Но в варианте Б АБ возвращаться придется А, которая только что вышла, а вариант Б Г исключен, так что Б БВ. Далее БВ В *.
– То же самое можно показать визуально, что в некоторых отношениях даже проще, – добавил он и набросал небольшую схему. – На этом рисунке показаны все 16 возможных комбинаций с кошками, а тонкие линии представляют возможные переходы между ними, когда кто-то из кошек выходит или входит. Черные точки исключены, два крестика исключают две линии перехода. Жирная линия – это единственный путь от АБВГ к * с использованием только разрешенных точек и линий и без возвратов.
Вскоре после этого я воссоединился со своими пушистыми друзьями.
– Сомс, как я смогу вас отблагодарить? – воскликнул я, радостно прижимая животных к своей груди.
Он взглянул на свой пиджак.
– Сможете, Ватсап, если станете почаще вычесывать своих кошек.
Блинные числа
1. Нет, не любую.
2. Некоторые стопки из четырех блинов требуют четырех переворачиваний; пример вы видите на рисунке. На рисунке вы можете найти еще две такие комбинации. Никакая стопка из четырех блинов не требует больше четырех переворачиваний.
А вот систематический способ доказать эти утверждения. На схеме показана требуемая конечная конфигурация 1234, где размеры блинов указаны сверху вниз. Мы будем двигаться от нее в обратном порядке. Во второй строке показаны конфигурации, которые можно получить из 1234 одним переворотом. Одновременно это те конфигурации, которые можно упорядочить (то есть из которых можно получить 1234) одним переворотом. (Один и тот же переворот, повторенный дважды, возвращает стопку к первоначальной конфигурации.) В третьей строке показаны все конфигурации, которые можно получить из конфигураций первой строки одним переворотом. Они же – конфигурации, которые можно упорядочить до 1234 двумя переворотами. Обратите внимание: ровно одну конфигурацию третьей строки можно получить из двух конфигураций второй строки; это 1324. Поэтому схема в этом месте выглядит слегка асимметрично.
Строки 1, 2, 3 содержат 21 из 24 возможных конфигураций стопки. Не хватает трех: 2413, 3142 и 4231. В строке 4 показано, как их можно получить из строки 3 при помощи еще одного переворота – или, рассматривая переворот в обратном порядке, как из них можно получить 1234 за четыре переворота. (Остальные связи, ведущие к строке 4, опущены, поскольку они сильно усложняют схему и не нужны нам.) На рисунке выше наглядно показаны перевороты конфигурации 2413, необходимые для ее упорядочивания.
3. Наибольший блин либо находится на самом верху, либо нет. Если нет, вставляем лопаточку под него и переворачиваем все, что выше. Теперь самый большой блин находится на самом верху. Вставляем лопаточку под самый низ стопки и всю ее переворачиваем. Теперь самый большой блин находится в самом низу. Таким образом, нам потребовалось не более двух переворотов, чтобы самый большой блин оказался внизу. Оставляем его там и повторяем всю процедуру для следующего по величине блина: не более чем за два переворота он оказывается сверху, на самом большом, вторым снизу. Повторяем процедуру для третьего по размеру блина и т. д. Каждый раз требуется не более двух переворотов, чтобы поместить очередной блин на нужное место, так что не более чем за 2n переворотов мы сможем упорядочить всю стопку из n блинов.
4. P1 = 0, P2 = 1, P3 = 3, P = 4, P5 = 5.
Задачу о сортировке блинов предложил Джейкоб Гудман в 1975 г.; он опубликовал ее под псевдонимом Харри Дуэйтер, что по-английски звучит как «издерганный официант». Решение задачи известно для всех n вплоть до 19, а вот для 20 неизвестно. Результаты выглядят так:
Блинные числа, как правило, идут группами, увеличиваясь на единицу с увеличением n. К примеру, Pn = 3, 4, 5, 6 для n = 3, 4, 5, 6. Но эта закономерность нарушается при n = 7, так как P7 = 8, а не 7. После этого наблюдается скачок на 2 при n = 11 и еще один при n = 19.
Верхнюю оценку в 2n переворотов – мой ответ на вопрос 3 – можно улучшить. В 1975 г. Уильям Гейтс (да-да, тот самый Билл Гейтс) и Христос Пападимитриу заменили эту оценку на (5n + 5)/3.
Кроме того, Гейтс и Пападимитриу рассмотрели задачу о горелом блине. В ней все блины подгорели с одной стороны, которая может оказаться снизу или сверху, а вы должны сделать так, чтобы блины не просто встали в правильном порядке по размеру, но и все легли горелой стороной книзу. В 1995 г. Дэвид Коэн доказал, что задача о сортировке горелых блинов требует по крайней мере 3n/2 переворотов и может быть решена не более чем за 2n – 2 переворотов.
Если вы подумываете о том, чтобы решить задачу сортировки блинов для n = 20, имейте в виду, что для этого числа блинов существует 2 432 902 008 176 640 000 начальных конфигураций.
Дело о таинственном колесе
– Диаметр колеса, разумеется, равен 58 дюймам, – сказал Сомс. – Это элементарное следствие из теоремы Пифагора.
Я обдумал это заявление. Следует отметить, что у меня есть некоторый опыт в области геометрии и алгебры.
– Позвольте мне попробовать, Сомс. Я считаю, что радиус колеса равен r. Заштрихованный треугольник на вашем чертеже – прямоугольный, его гипотенуза равна r, а две другие стороны равны r – 8 и r – 9. Таким образом, мы, как вы и намекали, можем применить теорему Пифагора и получить
(r – 8) + (r – 9) = r.
То есть
Читать бесплатно другие книги:
