Головоломок вишенка в коктейле
| Вид материала | Документы |
- Психологическое сопровождение замещающих семей, 219.46kb.
- Психологическая коррекция агрессивного поведения детей, 219.57kb.
- С. В. Левина Н. А. Задворочнова публичный доклад, 193.66kb.
- Проектный метод в деятельности доу, 187.91kb.
- Проектный метод в деятельности доу, 214.46kb.
- Альтергот Оксана Петровна. Детский сад является юридическим лицом, имеет полный пакет, 211.9kb.
ГЛАВА 15
Драконова кривая и другие задачи
^ 1. ПРЕРВАННАЯ ПАРТИЯ В БРИДЖ
Приятели собрались сыграть в бридж, хозяин дома сдал около половины колоды, но в этот момент зазвонил телефон. Когда он, поговорив, вернулся к столу, то никто не мог вспомнить, кому он сдал последнюю карту. Как ему продолжить сдавать карты так, чтобы у всех игроков оказалось их равное число, как и должно быть, при этом не считая ни сколько карт он уже сдал любому из игроков, ни сколько их осталось в колоде?
2. НОРА Л. АРОН
У одной студентки было необычное палиндромное имя: Нора Лил Арон. Её друг, также студент-математик, скучая на лекции, развлекался, пытаясь составить интересную числовую загадку. Он записал имя своей подруги в виде простого математического примера:
НОРА
Л
АРОН
Можно ли заменить все буквы цифрами так, чтобы получилось верное равенство? К удивлению студента, это оказалось возможным, причем единственным образом. И вы наверняка без особого труда найдете решение. Предполагается, что ни одно четырёхзначное число не может начинаться с 0.
^ 3. ЗАДАЧКА С ЧЕТЫРЁХЦВЕТНЫМИ ПОЛИОМИНО
Полиомино — фигуры, составленные из соединенных квадратных единиц. Один квадрат называется мономино, двойной — домино. Из трёх квадратов можно составить два вида тримино, из четырёх — пять тетрамино и т. д. Недавно меня заинтересовало, из какого минимального полиомино можно путем четырёхкратного повторения составить такую фигуру, чтобы каждая пара имела общий граничный сегмент? Мне кажется, что это — октомино, хотя у меня и нет доказательства. Джон Харрис из Калифорнии нашел пять решений этой задачи (см. рис. 97), хотя на самом деле их больше. Если представить каждую фигуру как участок карты, то легко увидеть, что для того, чтобы соседние регионы были разного цвета, требуется четыре разных цвета для раскрашивания такой карты.
Теперь давайте снимем ограничение на четырёхкратное повторение и посмотрим, из какого наименьшего полиомино при повторении можно составить фигуру, требующую для составления карты четырёх цветов? Необязательно, чтобы любые четыре составные части фигуры соприкасались друг с другом. Требуется лишь, чтобы повторяющиеся полиомино были расположены так, чтобы при раскрашивании их четырьмя разными цветами две соприкасающиеся составные части не были бы одинаковы по цвету. Участки, образующиеся между повторяющимися полиомино, не считаются областями «карты». Они остаются незакрашенными. Подсказка: в ответе фигурирует полиомино, порядок которого существенно меньше восьми.
^ 4. СКОЛЬКО ТОЧЕК?
Эта двойная задача была предложена Д. Моллисоном из Тринити-колледжа для студентов—членов Кембриджского математического общества.
Первый вопрос: каково максимальное число точек, которое можно расположить внутри фигуры, изображенной на рис. 98, с условием, что каждые две точки разделяются расстоянием не менее квадратного корня из 2?
п_
Рис. 97.
Октомино Джона Харриса
Второй вопрос: сколькими разными способами можно расположить эти точки, если не считать повороты и отражения? Пунктирные линии на рисунке показывают, что фигура составлена из четырёх квадратов, окруженных четырьмя половинками квадратов.
Рис. 98.
Задача Моллисона
^ 5. ТРИ МОНЕТКИ
Вы должны отвернуться, а кто-то из ваших товарищей в это время выкладывает на стол три разных монетки (например, по 5, 10 и 50 копеек). Он должен положить их таким образом, чтобы не все они лежали одной стороной вверх (орлом или решкой).
Вам нужно, не оборачиваясь, дать товарищу такие инструкции, чтобы он, переворачивая по одной монетке, положил их все одной стороной (орлом или решкой) вверх. Например, вы можете попросить его перевернуть десятикопеечную монету. После этого он должен сказать вам, лежат ли теперь все монеты одной стороной. Если этого не произошло, вы опять должны попросить его перевернуть одну монетку. Эта процедура продолжается до тех пор, пока все монетки не будут лежать одной стороной.
Ваши шансы на успех с первого раза равны При использовании наилучшей стратегии каковы ваши шансы на успех решить задачу за два или менее хода? Каково минимальное число ходов, гарантирующее вам успех?
Вам может показаться, что эту задачу легко решить, но можно несколько усложнить её. Ситуация остается такой же, как прежде, только на этот раз ваша цель — чтобы все монетки лежали орлом вверх. Допускается любое их начальное расположение, кроме трёх орлов. Так же как и раньше, после каждого хода вам должны говорить, достигли ли вы цели. При условии применения наилучшей стратегии каково минимальное число ходов, гарантирующее успех? Какова вероятность достичь успеха за два или менее хода, за три или менее хода и т. д.?
^ 6. 25 КОНЕЙ
На доске 5x5 клеток в каждой клетке стоит по шахматному коню. Можно ли пойти всеми 25 конями одновременно так, чтобы все 25 клеток снова оказались заняты? Кони должны ходить по обычным шахматным правилам: на две клетки вперед и на одну в любую из сторон.
^ 7. ДРАКОНОВА КРИВАЯ
Уильям Дж. Картер подготовил для семинара исследовательского центра НАСА в Кливленде буклет с загадочным рисунком на обложке (см. рис. 99). Эта «драконова кривая», как он назвал её, была придумана его коллегой Джоном Хайуэем и затем исследована Картером, Хайуэем и ещё одним физиком из НАСА, Джоном Бэнксом. Эта кривая начерчена по клетчатой бумаге, но каждый поворот на 90° закруглен, чтобы показать, что она никогда не пересекается сама с собой. Вы можете увидеть, что кривая отдаленно напоминает морского змея, который загребает влево когтистыми лапами и слегка выставляет над водой морду и закрученный хвост.
От вас требуется найти простой способ получения драконовой кривой. В ответах я предлагаю три варианта: один из них основан на последовательности чисел в двоичном коде, второй — на способе складывания листа бумаги и третий — на геометрическом построении. Именно на основании второго способа драконова кривая была придумана впервые. Также я объясню важность 12 отмеченных точек, которые показывают, что порядок этой кривой — именно 12. Получается, что эти 12 точек лежат на логарифмической спирали, хотя обнаружено это было лишь недавно, для открытия данной кривой никакого значения не имело.
^ 8. ДЕСЯТЬ СОЛДАТ
Десять солдат, все разного роста, стоят в шеренгу. Существует 10!, или 3 628 800, способов расставить их, однако в любом случае как минимум четверо будут стоять по возрастанию или убыванию их роста (они могут стоять не рядом, но если все остальные солдаты выйдут из строя, то оставшиеся окажутся стоящими строго по росту).
Вы можете убедиться в этом, проведя эксперимент с десятью игральными картами рангом от 1 до 10. Значения карт будут соответствовать росту солдат. Неважно, в каком порядке вы разложите карты, но четыре или более из них окажутся лежащими в порядке возрастания или убывания. Предположим, например, что вы положили карты следующим образом: 5, 7, 9, 2, 1, 4, 10, 3, 8, 6. Ряд 5, 7,9, 10 представляет собой возрастающий порядок. Допустим, вы уберете из него 10 и положите её между 7 и 9. В таком случае вы получите убывающий ряд — 10, 9, 8, 6.
Пусть максимальное число солдат, составляющих убывающий или возрастающий ряд, будет /?. Общее число солдат обозначим п. Задача не слишком проста: докажите, что при п = 10 р = 4. Пытаясь
Драконова кривая и другие задачи
^ 1. ПРЕРВАННАЯ ПАРТИЯ В БРИДЖ
Приятели собрались сыграть в бридж, хозяин дома сдал около половины колоды, но в этот момент зазвонил телефон. Когда он, поговорив, вернулся к столу, то никто не мог вспомнить, кому он сдал последнюю карту. Как ему продолжить сдавать карты так, чтобы у всех игроков оказалось их равное число, как и должно быть, при этом не считая ни сколько карт он уже сдал любому из игроков, ни сколько их осталось в колоде?
2. НОРА Л. АРОН
У одной студентки было необычное палиндромное имя: Нора Лил Арон. Её друг, также студент-математик, скучая на лекции, развлекался, пытаясь составить интересную числовую загадку. Он записал имя своей подруги в виде простого математического примера:
НОРА
Л
АРОН
Можно ли заменить все буквы цифрами так, чтобы получилось верное равенство? К удивлению студента, это оказалось возможным, причем единственным образом. И вы наверняка без особого труда найдете решение. Предполагается, что ни одно четырёхзначное число не может начинаться с 0.
^ 3. ЗАДАЧКА С ЧЕТЫРЁХЦВЕТНЫМИ ПОЛИОМИНО
Полиомино — фигуры, составленные из соединенных квадратных единиц. Один квадрат называется мономино, двойной — домино. Из трёх квадратов можно составить два вида тримино, из четырёх — пять тетрамино и т. д. Недавно меня заинтересовало, из какого минимального полиомино можно путем четырёхкратного повторения составить такую фигуру, чтобы каждая пара имела общий граничный сегмент? Мне кажется, что это — октомино, хотя у меня и нет доказательства. Джон Харрис из Калифорнии нашел пять решений этой задачи (см. рис. 97), хотя на самом деле их больше. Если представить каждую фигуру как участок карты, то легко увидеть, что для того, чтобы соседние регионы были разного цвета, требуется четыре разных цвета для раскрашивания такой карты.
Теперь давайте снимем ограничение на четырёхкратное повторение и посмотрим, из какого наименьшего полиомино при повторении можно составить фигуру, требующую для составления карты четырёх цветов? Необязательно, чтобы любые четыре составные части фигуры соприкасались друг с другом. Требуется лишь, чтобы повторяющиеся полиомино были расположены так, чтобы при раскрашивании их четырьмя разными цветами две соприкасающиеся составные части не были бы одинаковы по цвету. Участки, образующиеся между повторяющимися полиомино, не считаются областями «карты». Они остаются незакрашенными. Подсказка: в ответе фигурирует полиомино, порядок которого существенно меньше восьми.
^ 4. СКОЛЬКО ТОЧЕК?
Эта двойная задача была предложена Д. Моллисоном из Тринити-колледжа для студентов—членов Кембриджского математического общества.
Первый вопрос: каково максимальное число точек, которое можно расположить внутри фигуры, изображенной на рис. 98, с условием, что каждые две точки разделяются расстоянием не менее квадратного корня из 2?
п_
Рис. 97.
Октомино Джона Харриса
Второй вопрос: сколькими разными способами можно расположить эти точки, если не считать повороты и отражения? Пунктирные линии на рисунке показывают, что фигура составлена из четырёх квадратов, окруженных четырьмя половинками квадратов.
| л/Т/ | | |
| 1 | /1 | |
| | | 1 x x |
Рис. 98.
Задача Моллисона
^ 5. ТРИ МОНЕТКИ
Вы должны отвернуться, а кто-то из ваших товарищей в это время выкладывает на стол три разных монетки (например, по 5, 10 и 50 копеек). Он должен положить их таким образом, чтобы не все они лежали одной стороной вверх (орлом или решкой).
Вам нужно, не оборачиваясь, дать товарищу такие инструкции, чтобы он, переворачивая по одной монетке, положил их все одной стороной (орлом или решкой) вверх. Например, вы можете попросить его перевернуть десятикопеечную монету. После этого он должен сказать вам, лежат ли теперь все монеты одной стороной. Если этого не произошло, вы опять должны попросить его перевернуть одну монетку. Эта процедура продолжается до тех пор, пока все монетки не будут лежать одной стороной.
Ваши шансы на успех с первого раза равны При использовании наилучшей стратегии каковы ваши шансы на успех решить задачу за два или менее хода? Каково минимальное число ходов, гарантирующее вам успех?
Вам может показаться, что эту задачу легко решить, но можно несколько усложнить её. Ситуация остается такой же, как прежде, только на этот раз ваша цель — чтобы все монетки лежали орлом вверх. Допускается любое их начальное расположение, кроме трёх орлов. Так же как и раньше, после каждого хода вам должны говорить, достигли ли вы цели. При условии применения наилучшей стратегии каково минимальное число ходов, гарантирующее успех? Какова вероятность достичь успеха за два или менее хода, за три или менее хода и т. д.?
^ 6. 25 КОНЕЙ
На доске 5x5 клеток в каждой клетке стоит по шахматному коню. Можно ли пойти всеми 25 конями одновременно так, чтобы все 25 клеток снова оказались заняты? Кони должны ходить по обычным шахматным правилам: на две клетки вперед и на одну в любую из сторон.
^ 7. ДРАКОНОВА КРИВАЯ
Уильям Дж. Картер подготовил для семинара исследовательского центра НАСА в Кливленде буклет с загадочным рисунком на обложке (см. рис. 99). Эта «драконова кривая», как он назвал её, была придумана его коллегой Джоном Хайуэем и затем исследована Картером, Хайуэем и ещё одним физиком из НАСА, Джоном Бэнксом. Эта кривая начерчена по клетчатой бумаге, но каждый поворот на 90° закруглен, чтобы показать, что она никогда не пересекается сама с собой. Вы можете увидеть, что кривая отдаленно напоминает морского змея, который загребает влево когтистыми лапами и слегка выставляет над водой морду и закрученный хвост.
От вас требуется найти простой способ получения драконовой кривой. В ответах я предлагаю три варианта: один из них основан на последовательности чисел в двоичном коде, второй — на способе складывания листа бумаги и третий — на геометрическом построении. Именно на основании второго способа драконова кривая была придумана впервые. Также я объясню важность 12 отмеченных точек, которые показывают, что порядок этой кривой — именно 12. Получается, что эти 12 точек лежат на логарифмической спирали, хотя обнаружено это было лишь недавно, для открытия данной кривой никакого значения не имело.
^ 8. ДЕСЯТЬ СОЛДАТ
Десять солдат, все разного роста, стоят в шеренгу. Существует 10!, или 3 628 800, способов расставить их, однако в любом случае как минимум четверо будут стоять по возрастанию или убыванию их роста (они могут стоять не рядом, но если все остальные солдаты выйдут из строя, то оставшиеся окажутся стоящими строго по росту).
Вы можете убедиться в этом, проведя эксперимент с десятью игральными картами рангом от 1 до 10. Значения карт будут соответствовать росту солдат. Неважно, в каком порядке вы разложите карты, но четыре или более из них окажутся лежащими в порядке возрастания или убывания. Предположим, например, что вы положили карты следующим образом: 5, 7, 9, 2, 1, 4, 10, 3, 8, 6. Ряд 5, 7,9, 10 представляет собой возрастающий порядок. Допустим, вы уберете из него 10 и положите её между 7 и 9. В таком случае вы получите убывающий ряд — 10, 9, 8, 6.
Пусть максимальное число солдат, составляющих убывающий или возрастающий ряд, будет /?. Общее число солдат обозначим п. Задача не слишком проста: докажите, что при п = 10 р = 4. Пытаясь
Рис. 99.
юконова кривая 12-го порядка
найти это доказательство, вы, скорее всего, найдете общее правило, согласно которому легко высчитать р для любого п.
^ 9. ЛЮБОПЫТНОЕ МНОЖЕСТВО ЦЕЛЫХ ЧИСЕЛ
У множества целых чисел 1, 3, 8 и 120 имеется занятная особенность: произведение любой пары из них на 1 меньше, чем квадрат какого-нибудь целого числа. Найдите пятое число, которое можно добавить к этому множеству, чтобы данная особенность сохранилась.
ОТВЕТЫ
^ 1. Сдающий должен сдать нижнюю карту из колоды себе, а затем продолжать сдавать так же снизу, против часовой стрелки, всем остальным игрокам.
2. Выражение НОРА х Л = АРОН имеет единственное решение в числах: 2178 х 4 = 8712. Если бы средний инициал в этом имени был не Л, а А, тогда единственным решением было бы: 1089 х 9 = 9801. Числа 2178 и 1089 - единственные числа, меньшие 10 000, имеющие кратное, состоящее из тех же цифр в обратном порядке (мы не считаем банальные палиндромные числа 3443, умноженные на 1). В середину каждого из этих чисел можно вставить девятки и получить более крупные (но не представляющие интереса) числа, обладающие той же особенностью, например 21 999 978 х 4 = 87 999 912.
Подробнее о таких числах в различных системах счисления можно прочитать в статье Алана Сатклиффа с причудливым названием ^ Integers That Are Multiplied When Their Digits Are Reversed («Целые числа, превращающиеся при умножении в обратную запись самих себя»), Mathematics Magazine, т. 39, № 5, ноябрь 1966, с. 282—287.
Более крупные числа можно также составить путем повтора каждой четырёхзначной комбинации: 217 821 782 178 х 4 = = 871 287 128 712, а 108 910 891 089 х 9 = 980 198 019 801. Само собой, числа типа 21 999 978 также можно повторять и получать числа-«пе-ревертыши». Леонард Клозински и Дэннис Смоларски в статье On the Reversing of Digits («О переворачивании чисел»), Mathematical Magazine, т. 42, сентябрь 1969, с. 208—210, показывают, что 4 и 9 — это единственные числа, которые можно использовать в качестве множителей для перевертывания непалиндромных чисел. Можно выразить то же самое иначе. Если целое число представляет собой множитель для своего «перевертыша», то большее из этих двух чисел должно делиться на меньшее с получением строго 4 или 9.
Тот факт, что 8712 и 9801 — единственные четырёхзначные числа, дающие при умножении на целое число число-«перевертыш», упоминает в своем знаменитом «Оправдании математика» (Mathematician's Apology) Дж. X. Гарди в качестве примера несерьёзного в математике. Для тех, кому симпатичны подобные курьезы, я привожу здесь следующую таблицу, присланную мне Бер-наром Гайенни, указывающую на любопытные отношения между парами чисел:
1089 6534
2178 7623
3267 8712
4356 9801
5445
Эти девять чисел, естественно, являются кратными 1089. Обратите внимание на то, как меняются цифры в каждом разряде при движении вверх и вниз. Если первые пять чисел помножить соответственно на 9, 4, 2 Уз> 1 {/2 и 1, то в результате получатся вторые пять чисел в обратном порядке. 1,4 и 9 — это первые три квадратных числа, и кажется, что два других множителя, 2 а/3 и 1 ]/2, совершенно не имеют к ним отношения.
3. На рисунке 100 показано, как всего из 6 домино можно составить такую сложную фигуру, чтобы для её раскрашивания потребуется минимум 4 краски, чтобы два соседних домино не были одинакового цвета.
Рис. 100.
Шесть домино, четыре цвета
Это мое собственное решение. Но, к моему удивлению, двое читателей (Бент Шмидт-Нильсен и Э.С. Эйнли) нашли способ добиться того же самого результата, взяв 11 мономино (одинарных квадратов). Это решение показано на рис. 101. Винсент Крон и У.Х. Гриндли предложили неформальное доказательство того, что 11 — это минимальное число мономино.
Если задаться вопросом, какое максимальное число мономино можно сложить так, чтобы каждая пара имела общую границу, то очевидно, что ответом будет 3. Однако на этот вопрос труднее ответить, если в качестве единичных составных частей взять кубы. Вопрос тогда звучит так: какое максимальное число кубиков можно сложить так, чтобы каждая пара обладала общей поверхностью? Эта поверхность может быть не целой гранью куба, однако это должна быть именно поверхность, а не линия и не точка. Ответ — 6. Прекрасное решение показано на рис. 102. Три куба, обозначенные сплошными линиями, стоят на трёх, обозначенных пунктиром.
4. На фигуре можно разместить 5 точек так, как показано на рис. 103. Тогда расстояние между любыми двумя точками будет равно квадратному корню из 2 или больше его. Каждая точка может быть слегка передвинута, то есть число различных решений фактически
Рис. 101.
Решение задачи с мономино
Рис. 103.
Решение головоломки с точками
бесконечно. Ну как, удалось ли вам не попасться в тщательно расставленную ловушку и не начать пытаться располагать точки по вершинам фигуры?
Эта задача была опубликована в журнале архимедовского общества Eureka в октябре 1966 года.
5. Наилучший способ сделать так, чтобы все три монеты лежали одинаковыми сторонами, — это потребовать перевернуть их все, затем — через одну, а затем — первую из упомянутых. Вероятность успеха при первом перевороте — 1/з- Если вам не повезет, тогда на втором ходе вероятность успеха составит {/2. Можно подумать, что шансы на достижение успеха за 2 или менее ходов равны сумме этих вероятностей, но это неверно. Рассмотрим влияние первых двух ходов на каждое из шести начальных положений: OOP, ОРО, ОРР, POO, POP, РРО. Принцип симметрии позволяет за первые два хода перевернуть любые две монетки. Это приведет к успеху в 4 из 6 случаев, так что вероятность достичь его за 2 или менее хода равна четырем шестым, или 2/з-
Если вы хотите повернуть все три монетки орлами, то успех гарантирован за семь ходов. Из восьми начальных положений исключается только ООО. Таким образом, для того, чтобы рано или поздно получить искомые ООО, вам нужно перебрать как максимум семь вариантов. Самуэль Шварц предложил легко запоминающуюся стратегию: пронумеровать монетки 1, 2, 3 и переворачивать их в таком порядке: 1, 2, 3, 2, 1,2, 3. Вероятность успеха на первом ходе составляет 1/7, на втором или раньше — 2/у и так далее, до 7/7 или 1, на седьмом ходе или ранее.
Если число монет — я, то очевидно, что требуется 2п — 1 ходов. Последовательность действий соответствует последовательности чисел в двоичном циклическом коде. Руфус Айзеке и Энтони Риддл проанализировали данную ситуацию с позиций теории игр. Игрок, прячущий монеты, старается увеличить число ходов второго игрока, который в свою очередь стремится к обратному. Лучшая стратегия для первого игрока — выбрать одно из семи возможных начальных сочетаний монет случайным образом. Наилучшая стратегия для второго — пронумеровать грани кубика двоичными числами от I до 8, а затем нарисовать на его гранях гамильтонов путь. Последовательность ходов соответствует последовательности бинарных чисел, полученных, начиная от угла, соответствующего 111 или ООО, при выборе с равной вероятностью одного из двух направлений пути, а затем прохождении этого пути. Если оба игрока используют оптимальную стратегию, то ожидаемое число ходов — четыре.
^ В журнале American Mathematical Monthly за декабрь 1938 года была помещена обобщенная задача такого типа. В её условии говорилось об п выключателях, которые включали свет только тогда, когда были повернуты все. Общая теория подобных поисковых игр дана в книге «Дифференциальные игры» (Differential Games) Руфуса Айзекса.
6. 25 коней не могут одновременно перейти на другие клетки.
Это легко доказать проверкой четности. Конь, делая ход, переходит
на клетку, которая отличается по цвету от той, на которой он стоял
вначале. На доске 5x513 клеток одного цвета и 12 другого. Очевид-
но, что 13 коней не могут перейти на 12 клеток без того, чтобы ка-
кие-то два из них не оказались на одной и той же клетке. Это дока-
зательство действует для любой доски с нечетным числом клеток.
Если вместо коней взять ладьи, причем ограничить их ходы одной клеткой, задача будет иметь такой же ответ с таким же доказательством невозможности. И, конечно, то же самое будет справедливо и для любого сочетания коней с такими ладьями.
7. Каждую драконову кривую можно описать последовательнос-
тью чисел в двоичной системе, где единицы будут обозначать пово-
роты влево, а нули — вправо по ходу кривой от «хвоста» до «морды».
Для каждого порядка кривой формула выводится из формулы кри-
вой на один порядок ниже следующим образом: добавляем единицу,
затем приписываем все цифры, предшествующие этой единице
(только меняем центральную цифру ряда). У дракона первого по-
рядка формула представляет собой просто 1. В данном случае после
добавления 1 слева есть лишь одна цифра, и она же является «цент-
ральной». Мы заменяем её на 0 и получаем формулу для дракона
второго порядка: ПО. Чтобы получить формулу третьего порядка, после предыдущей формулы пишем 1, затем — ПО с замененной центральной цифрой, и получаем: 1101100. Точно так же получаются и формулы всех последующих порядков. Легко заметить, что каждый дракон состоит из пары драконов порядка на один ниже, соединенных морда к морде.
На рис. 104 показаны драконовы кривые порядка от 0 до 6. Все они изображены от хвоста к голове и повернуты так, что «плывут» направо, высунув кончик хвоста и нос над водой. Если принять за символ правого поворота не 0, а 1, и наоборот, мы получим формулы драконов, «плывущих» в другую сторону. Точки на каждой кривой соответствуют центральным единицам в формулах для последовательности порядков от 1 до данного. Все эти точки у любого дракона лежат на логарифмической спирали.
Драконова кривая была открыта физиком Джоном Хайуэем в результате совершенно других действий. Сложите пополам листок бумаги, потом раскройте его так, чтобы половинки поднимались вверх под прямыми углами, и посмотрите на лист с «торца». Вы увидите дракона первого порядка. Если сложить тот же лист дважды, всегда в одном и том же направлении, а затем снова развернуть под прямыми углами, то противоположные края листа будут представлять собой двух «зеркальных» драконов 2-го порядка. Сложив лист три раза, вы получите дракона 3-го порядка, как показано на рис. 105. В общем, п сгибов бумаги дают дракона я-ного порядка.
Само собой, двоичную формулу можно применить и для сложенной бумажной ленты, из которой можно получить модели драконов более высоких порядков. Допустим, единица обозначает «горку» (изгиб вверх), а ноль — «долину» (изгиб вниз). Начиная с одного конца ленты, складывайте её согласно формуле. Если затем отпустить ленту, позволив каждой складке раскрыться под прямым углом, вы получите дракона, соответствующего формуле.
Физик Брюс Бэнкс открыл геометрический метод построения, показанный на рис. 106. Её первая ступень — большой прямой угол. Затем, с каждым шагом, линейный сегмент заменяется на прямой угол, образованный более мелкими сегментами, как изображено на рисунке. Эта процедура подобна складыванию «снежинки», описанному мной в книге Sixth Book of Mathematical Games from Scientific American («Шестая книга математических игр от Scientific Атепсап»). Читатель наверняка сможет понять, почему это приводит к такому же результату, как и складывание листа бумаги.
0 1 2
Уильям Дж. Хартер, третий из физиков, первыми анализировавших драконову кривую, нашел множество фантастических способов точного совмещения драконов наподобие «паззла» на плоскости, в том числе и в виде симметричных фигур.
Их можно соединять морда к морде, хвост к хвосту, морда к хвосту, спина к спине, спина к брюху и так далее. На рис. 107 показаны четыре дракона 6-го порядка, соединенных хвостами. Если вы хотите самостоятельно изобразить подобную головоломную конструкцию, попробуйте соединить таким же способом четырёх драконов 12-го порядка, таких как изображенный на рис. 99. Если каждая из кривых будет иметь бесконечную длину, они полностью займут поверхность в том смысле, что каждая сторона каждой клетки базовой решетки будет пройдена точно по одному разу. Для экспериментов по соединению драконов лучше пользоваться прозрачной бумагой, которую можно по-разному накладывать слой на слой.
Дональд Кнут, кибернетик из Стэнфордского университета, и Чендлер Дэвис, математик из университета Торонто, провели наиболее обширное исследование драконовых кривых. Их публикация Number Representation and Dragon Curves («Числовое представление и драконовы кривые») в журнале Journal of Recreational Mathematics (т. 3, апрель и июль 1970 года) содержит большой объем информации о способах построения драконовой кривой и последовательностей кривых вместе с их вариациями и обобщениями, а также их свойствами. Также вы можете обратиться к статье Кнута и его супруги Джилл, опубликованной в том же журнале в т. 6, лето 1971 года,
1101100111001001-
1101100011001001-1101100111001000-ПОН 0001 100100
Рис. 104.
Драконы порядков от 1 до 6 с их двоичными формулами
2
3
где они рассказывают, как с использованием трёх видов керамической плитки выложили драконову кривую 9-го порядка на стене в своем доме.
8. Если поставить в ряд п солдат разного роста, по меньшей мере р из них будут стоять по убыванию или возрастанию роста. Число р — квадратный корень их самого маленького квадрата, большего или равного п.
Для доказательства этого обозначим каждого солдата двумя буквами, а и d. Пусть а — это максимальное число солдат, стоящих слева от данного, включая его самого, по возрастанию роста. (Говоря «слева», я имею в виду справа с вашей точки зрения, если вы стоите лицом к шеренге.) Пусть d — максимальное число солдат слева от данного, включая его самого, стоящих по убыванию роста. Легко показать (я оставляю это вам), что у каждого из солдат будут разные числовые обозначения. У двух солдат могут совпадать значения а или d, но не оба эти числа одновременно.
Предположим, 10 солдат стоят так, что в самой длинной последовательности по возрастанию или убыванию роста среди них р человек, то есть минимальное возможное число. Ни у одного из них не может быть значения а или d, превосходящего р. Так как у любых
Рис. 107.
Четыре дракона 6-го порядка, соединенные хвостами
двоих солдат пары чисел а и d различаются, р должно быть достаточным для того, чтобы существовало не менее одной различающейся пары чисел а и d.
Может ли р быть равно 3? Нет, так как в этом случае будет существовать только З2 = 9 пар чисел:
я 1 1 1 2 2 2 3 3 3 d 1 2 3 1 2 3 1 2 3
Любое число р даст нам р2 пар чисел and. Так как З2 = 9, у нас недостаточно пар для 10 солдат. Однако 4 — уже 16, то есть более
чем достаточно. Мы можем заключить, что вне зависимости от того, как стоят солдаты, по меньшей мере четверо из них будут стоять по возрастанию или убыванию роста. 4 остается числом р для групп числом до 16 человек. Но для группы в 17 солдат нам придется перейти кр, равному 5, для того, чтобы получить достаточно пар а и d.
Если поставить в ряд 100 солдат разного роста, хотя бы 10 из них будут стоять по росту. Однако, если солдат станет всего на одного больше, число р тут же возрастет до 11.
Эта проблема хорошо освещена в разделе 7 части о комбинаторном анализе из сборника Mathematical Sciences, вышедшего в издательстве Массачусетского технологического института в 1969 году. Автор этой части сборника — Джан-Карло Рота. В обобщенном и расширенном виде эта задача обсуждается в двух статьях: Monotonic Subsequences («Монотонные подпоследовательности») Дж. Б. Крус-кала-мл., Proceedings of the American Mathematical Society, вып. 4, 1953, с. 264—274, и Longest Increasing and Decreasing Subsequences («Самые длинные восходящие и нисходящие подпоследовательности») Крэйга Шенстеда, Canadian Journal of Mathematics, вып. 13, 1961, с. 179-191.
9. Пятое число — это 0. Естественно, этот ответ элементарен и является шуточным. Но отсюда возникает весьма сложный вопрос: существует ли пятое положительное число (отличное от 1, 3, 8 и 120), которое можно было бы добавить к этому множеству, не нарушая его свойства (произведение двух любых членов множества должно быть на 1 меньше, чем квадрат какого-либо целого числа)?
Эта необычно сложная задача из области диофантовой математики восходит исторически к Ферма и Эйлеру. Об этом можно прочесть в книге Л.Э. Диксона History of Number Theory («История теории чисел»), т. 2, с. 517f. У этой задачи действительно богатая история, а окончательное разрешение она получила лишь в 1968 году. Один из студентов К. Баукампа из технологического университета г. Эйндховена в Нидерландах увидел эту задачу в журнале и рассказал о ней Баукампу. Тот, в свою очередь, показал её коллеге, Дж. X. Ван Линту. Ван Линт в 1968 году показал, что если 120 и может быть заменено другим положительным целым числом без нарушения свойства множества, то в нем должно быть более 1 700 000 разрядов. Затем Алан Бейкер из Кембриджа соединил результаты Ван Линта с одной из собственных сложных теорем и, наконец, разрешил проблему. В статье Бейкера и Д. Дэвенпорта во втором выпуске Quaterly
Journal of Mathematics, т. 78, 1969, доказывается, что 120 не может быть заменено другим целым числом, и, следовательно, множество не может иметь пятого члена. Это доказательство весьма сложно и требует в том числе подсчета ряда чисел до 1040 знаков после запятой.
Известно, что существует бесконечное число наборов из 4 положительных чисел с упомянутым свойством: 1, 3, 8 и 120 — это один из них, имеющий наименьшую сумму. В Journal of Recreational Mathematics, вып. 4, апрель 1971, в статье Андервуда Дадли и Дж. X. Хантера, посвященной этой проблеме, приводятся 20 других вариантов подобных множеств. В 3-м выпуске № 26 Quaterly Journal of Mathematics за 1975 год П. Канагасабапати и Т. Поннудурай в своей статье дают менее сложное доказательство несуществования пятого члена множества 1, 3, 8, 120. Этой же задаче посвящена и статья А Problem of Fermat and the Fibonacci Sequence («Задача Ферма и последовательность Фибоначчи») В. Э. Хоггатта-мл. и Дж. Э. Бергама в журнале Fibonacci Quaterly, вып. 15, декабрь 1977.
Существует ли на самом деле множество из пяти членов, которые были бы целыми числами и обладали желаемым качеством? Насколько известно мне, пока этого никто не выяснил.