Вернемся наконец к доказательству гипотезы Коллатца. Его не существует, и, по правде говоря, я знаю множество способов заработать 500 долларов, гораздо более простых, чем возня с этой задачей.
Загадка шахматной доски
Я несколько сомневался, говорить ли о следующей загадке. На самом деле она очень проста. Тем не менее после бурного спора с самим собой я решил все-таки рассказать о ней, потому что она весьма знаменита, причем и сама загадка, и ее решение замечательно красивы.
Рассмотрим сетку размером 8 × 8 ячеек.
Очевидно, всю эту сетку легко покрыть 32 костяшками домино размером 1 × 2 ячейки. А теперь уберем две клетки, расположенные в противоположных углах.
Можно ли покрыть получившуюся сетку всего 31 костяшкой?
Мои друзья (все они не математики, но по большей части люди весьма умные) в большинстве своем уверены, что можно, – нужно только сообразить, как именно их следует расположить.
Но правильный ответ на этот вопрос – «нет». Что бы мы ни делали, 31 костяшка домино не может покрыть сетку с удаленными противоположными угловыми клетками.
Почему это так, немедленно становится ясно, если взять вместо такой незакрашенной сетки черно-белую шахматную доску.
Как видно на рисунке, каждая костяшка домино может закрыть одну черную клетку и одну белую; поэтому 31 костяшка может закрыть в точности 31 белую клетку и 31 черную. Поскольку две клетки, удаленные с доски, одного и того же цвета – белые, – в обрезанной доске осталось 30 белых клеток и 32 черные. Много лет назад, когда я учился на математическом факультете в Тель-Авиве, я вел для «интересующейся наукой молодежи» курс под названием «Парадоксы, загадки и числа». Я давал эту задачу молодым слушателям своего курса. Каждый раз происходила одна любопытная вещь. Многие ученики решительно не соглашались с доказательством, которое показывает, что 31 костяшка домино не может покрыть доску с удаленными противоположными угловыми клетками. Интересно отметить, что в их число входили и ученики, казалось бы, вполне понимавшие объяснение этого доказательства; тем не менее они упорно раскладывали костяшки домино так и эдак, стараясь покрыть эту самую доску с обрезанными углами. Я даже не пытался убедить их в бессмысленности этого занятия – каждый должен учиться на собственных ошибках.
История учит нас, что люди и народы ведут себя мудро после того, как они исчерпают все остальные возможности.
Докажите, что, если из шахматной доски удалить любые две клетки разных цветов, все оставшиеся клетки всегда можно покрыть 31 костяшкой домино.
Бесконечные крестики-нолики
Когда я учился в начальной школе в Литве, в своем родном Вильнюсе, одним из самых значительных моих достижений было обретение виртуозного умения играть на уроках в стратегические игры с карандашом и бумагой и не попадаться учителям. Моей любимой игрой был бесконечный вариант крестиков-ноликов. Эта игра не раз спасала меня от скуки на занятиях, на которых меня заставляли сидеть.
Позвольте объяснить вам правила игры.
Вы, несомненно, знакомы с обычными крестиками-ноликами, в которые играют на поле размером 3 × 3 клетки. Эта игра подходит для детей лет до шести. После этого возраста каждая партия должна неизменно заканчиваться вничью, если только один из игроков не заснет в процессе игры (что, бесспорно, возможно, учитывая, насколько эта игра скучна).
В бесконечном варианте играют на бесконечном поле, и каждый игрок стремится выстроить ряд из пяти крестиков или ноликов. Как и в исходном варианте, ряд может быть горизонтальным, вертикальным или диагональным. Игроки по очереди ставят на поле крестики и нолики, и первый, выстроивший ряд из пяти своих символов, считается победителем.
a)
б)
a) У ноликов нет хода, который позволил бы заблокировать две «открытые» тройки крестиков; нолики проигрывают
б) Пример еще одной партии, которую только что выиграли крестики
В начальной школе, когда я «открыл» эту игру, я думал, что сам ее и изобрел, но впоследствии узнал, что это не так: существует игра под названием «гомоку», очень похожая на бесконечные крестики-нолики. Она особенно популярна в Японии и Вьетнаме. Слово го означает по-японски «пять».
Вы наверняка слышали об игре го. Однако, хотя в гомоку часто играют на такой же доске, какую используют для этой прославленной великой игры, между ними нет никакой связи. Го – древняя китайская игра, которая даже упоминается в «Аналектах»[2] Конфуция. Поскольку она попала на Запад через Японию, мы используем ее японское название, но, как я уже сказал, го – это не гомоку[3]{2}.
Несмотря на тот опыт, который я накопил, играя на уроках – а иногда и на переменах (хотя на переменах играть не так интересно – потому что это не запрещено!), я не мог понять, всегда ли игрок, начинающий первым (то есть играющий крестиками), выигрывает, если он применяет правильную стратегию, независимо от того, как играет его противник, или же партия всегда заканчивается вничью (точнее, не может закончиться никогда), если оба ее участника играют правильно. Интуиция подсказывала мне, что должна существовать какая-то стратегия, обеспечивающая победу игроку, делающему первый ход в партии.
По совести, я должен признаться, что не играл в эту игру уже несколько десятков лет. Я вспомнил о ней, когда писал эту книгу. Но вопросы о стратегических аспектах игры и о существовании некой выигрышной стратегии занимают меня до сих пор. Я даже готов поспорить, что такая выигрышная стратегия существует. Когда я буду старше и у меня будет больше свободного времени, я собираюсь всерьез заняться поисками этой стратегии, но, пока эти мои планы относятся к отдаленному будущему, вы вполне можете попытаться найти ее раньше меня и избавить меня от этой работы.
Монах и его задача{3}: взгляд с обеих сторон
Однажды ранним утром, на самом восходе солнца, старый буддийский монах начал подниматься по крутому и извилистому горному склону к монастырю, стоявшему на вершине. Монах взбирался по узкой, извивающейся тропе – единственному пути в монастырь. Подъем был поистине изнурительным.
Он шел то быстрее, то медленнее, время от времени останавливаясь передохнуть, бормоча мантры, а иногда задерживаясь, чтобы немного поесть или попить воды. До монастыря на вершине он добрался в тот самый момент, когда солнце начинало садиться. Старый монах провел в монастыре несколько дней, уча молодых монахов о сострадании, о Четырех благородных истинах, о шуньяте (пустотности), об иллюзорности самосознания, о сансаре и страдании, о карме и спокойствии, о Благородном восьмеричном пути, об учении Нагарджуны и о желании избавиться от желаний.
Когда же монах закончил свои поучения, пришло время спуститься с горы и вернуться в свою деревню. Он начал спускаться в то же время, когда начинал подниматься – с появлением первых солнечных лучей, – и шел в точности по тому же пути, что и раньше. Спускался старый монах, разумеется, гораздо быстрее, чем поднимался. Когда он дошел до конца спуска, ему в голову пришло, что на тропе, несомненно, есть такая точка, которую он проходил на подъеме и на спуске в точности в одно и то же время суток.
Как монах пришел к этому выводу? Если вы еще не нашли ответа на этот вопрос за десять секунд размышлений, вот вам вполне очевидная подсказка:
Пусть два монаха отправляются в путь на рассвете, причем один из них поднимается от подножия горы, а второй спускается с ее вершины. В какой-то точке они неизбежно встретятся.
Математика тенниса: бесконечность – это сколько?
В 1953 г. английский математик Джон И. Литлвуд (1885–1977) предложил следующий парадокс, известный теперь под названием «парадокс Росса – Литлвуда».
Перед входом в огромную пустую комнату выложен бесконечный ряд теннисных мячей, пронумерованных по порядку: 1, 2, 3, 4… Близится полночь. За тридцать секунд до 0:00 в комнату вносят мячи 1 и 2 и мяч номер 1 немедленно выносят из нее. За пятнадцать секунд (четверть минуты) до 0:00 в комнату вносят мячи 3 и 4, а мяч номер 2 выносят. За одну восьмую минуты до 0:00 в комнату вносят мячи 5 и 6, а мяч номер 3 выносят – и так далее. На языке математики мы бы сказали, что за (½)n минуты до 0:00 в комнату вносят мячи 2n – 1 и 2n, а мяч номер n из нее выносят.
Спрашивается, сколько мячей будет в комнате ровно в 0:00?
Те, кто пытается ответить на этот вопрос, замечают, что возможных ответов существует два, и у обоих почти что поровну сторонников: бесконечно много или ни одного. Как такое может быть? Рассмотрим логические обоснования обоих ответов.
Бесконечно много. В конце процесса в комнате будет бесконечно много мячей, потому что на каждом из бесконечного количества этапов в ней прибавляется по одному мячу (два заносят в комнату, но один из нее выносят). Математики формулируют это утверждение так: для любого n можно точно определить момент, в который число мячей равно n + 1. Следовательно, в 0:00 в комнате окажется бесконечно много мячей.
Ни одного. В 0:00 в комнате не будет ни одного мяча, потому что для любого мяча можно точно указать момент, в который его выносят из комнаты. Мяч номер 1 выносят, когда часы показывают полминуты до полуночи, мяч номер 2 – за четверть минуты до полуночи и так далее. Говоря математическим языком, n-й мяч выносят из комнаты в точности за ½ в n-й степени минуты до полуночи.
Если бы на эту тему проводился опрос, за какой ответ проголосовали бы вы?
Здесь важно понимать – хотя согласиться с этой мыслью может быть немного трудно, – что количество моментов, остающихся до полуночи, бесконечно, потому что оставшийся промежуток всегда можно разделить на два.
Я бы сказал, что правильный ответ – «бесконечно много», и даже рискнул бы утверждать, что те, кто выбирает второй ответ, вероятно, не могут отрешиться от схемы конечных рассуждений. Их стремление узнать, сколько мячей окажется в комнате «в конце» процесса, похоже на стремление узнать, какие числа находятся «в конце» последовательности натуральных чисел, то есть «в конце» ряда 1, 2, 3, 4, 5, 6, 7, 8, 9, …, 12 367, 12 368…
Все мы знаем и понимаем, что множество натуральных чисел бесконечно, и никто на свете не может сказать, какие числа находятся «в конце» их ряда, просто потому, что у этого ряда нет никакого конца.
Интересно отметить, что Блаженный Августин (354–430) полагал, что Бог видит и знает все бесконечное количество натуральных чисел и их свойства и тем самым каким-то образом превращает их в конечное множество (но это, разумеется, лишь точка зрения Блаженного Августина).
Вот две другие вариации парадокса Росса – Литлвуда.
У нас снова есть бесконечный ряд теннисных мячей с номерами 1, 2, 3, 4… выложенный перед входом в огромную пустую комнату. За полминуты до полуночи в комнату вносят мячи 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10 и выбрасывают из нее мяч номер 1. За четверть минуты до полуночи в комнату вносят мячи 11, 12, 13, 14, 15, 16, 17, 18, 19 и 20 и выбрасывают из нее мяч номер 2 – и так далее.
Вопрос, разумеется, остается тем же: сколько мячей будет в комнате ровно в полночь?
В этом случае на каждом этапе в комнату добавляют 10 мячей, а убирают только один, то есть в ней становится на девять мячей больше. Поскольку эта процедура повторяется бесконечное число раз, кажется совершенно ясным, что в полночь в комнате будет бесконечно много мячей (можно даже сказать, девять раз по бесконечно много!).
Можете ли вы сказать, какие именно мячи будут в комнате? То есть номер(а) мячей, которые останутся в комнате.
Перед огромной пустой комнатой по-прежнему выложен все тот же ряд теннисных мячей с номерами 1, 2, 3, 4… За полминуты до полуночи в комнату вносят мячи 1 и 2, причем мяч 2 сразу же из нее выкидывают. За четверть минуты до полуночи в комнату вносят мячи 3 и 4, причем мяч 4 сразу же из нее выкидывают. И так далее. Тот же вопрос: сколько мячей будет в комнате в полночь?
Внезапно все становится кристально ясно.
Поскольку мы выкидываем все мячи с четными номерами, в полночь в комнате будет бесконечно много мячей, и у всех у них будут нечетные номера. Так что мы знаем, какие именно мячи останутся в комнате в полночь: 1, 3, 5, 7, 9, 11, 13, 15…
Разумеется, количество нечетных чисел бесконечно, и все они будут в комнате. Четные числа также образуют бесконечное множество, но они окажутся снаружи.
Можно ли сказать, что множества нечетных чисел и четных чисел меньше, чем множество всех натуральных (то есть целых положительных) чисел?
На первый взгляд можно решить, что это утверждение должно быть справедливым. Казалось бы, логично считать, что, например, множество четных чисел должно быть в два раза меньше множества всех натуральных чисел (в которое входят числа как четные, так и нечетные).
Однако посмотрим на этот вопрос вот с какой стороны: каждому натуральному числу можно сопоставить натуральное число.
Теперь мы начинаем осознавать эту умопомрачительную концепцию: хотя в множестве четных чисел пропущено каждое второе число (по сравнению с множеством всех натуральных чисел), количество элементов обоих множеств все равно одинаково. Говорят, что это множества одинаковой мощности. В этой книге мы еще поговорим о концепции мощности множества гораздо подробнее.
А это, по сути, подводит нас к вопросу еще более глубокому: можно ли вообще сравнивать бесконечные множества чисел и спрашивать, какое из них больше? Имеют ли слова «больше» и «меньше», «крупнее» и «мельче» вообще хоть какой-нибудь смысл, когда речь идет о бесконечных величинах?
Читайте дальше!
Концепция бесконечности сложна и глубока и иногда действительно кажется невообразимой. Имеет смысл вспомнить, что говорил на эту тему Галилей:
[Это] относится к числу затруднений, происходящих вследствие того, что, рассуждая нашим ограниченным разумом о бесконечном, мы приписываем последнему свойства, известные нам по вещам конечным и ограниченным. Между тем это неправильно, так как такие свойства, как большая или меньшая величина и равенство, неприменимы к бесконечному, относительно которого нельзя сказать, что одна бесконечность больше или меньше другой или равна ей[4].