Восемь этюдов о бесконечности. Математическое приключение
Шрифт:
Пал Эрдёш был математиком исключительно плодовитым. Его превосходную биографию можно найти в книге Пола Хофмана «Человек, который любил только числа» (The Man Who Loved Only Numbers, 1998). Он написал более 1400 научных статей. Эрдёш был страстным поборником командной работы и сотрудничества, и за годы его научной деятельности вместе с ним над его статьями работали целых 511 математиков. Любому математику, который когда-либо писал статью в соавторстве с самим Эрдёшем, присваивается престижное число Эрдёша, равное 1. Те, кто сотрудничал с его соавторами, но не с самим Эрдёшем, получают число Эрдёша, равное 2. Аналогичным образом по мере все большего удаления присваиваются числа Эрдёша, равные 3, 4 и так далее. Общее правило таково: если вы сотрудничаете с человеком, наименьшее число Эрдёша которого равно k, то ваше число Эрдёша равно k + 1. Сам Эрдёш был единственным человеком с числом Эрдёша, равным 0. На противоположном конце спектра находятся те, кто никогда
Это напоминает популярную салонную игру «Шесть шагов до Кевина Бейкона». Знаменитый голливудский актер Кевин Бейкон заявил однажды, что все до единого актеры в Голливуде либо снимались с ним вместе (Бейкон-1), либо снимались с кем-нибудь, с кем снимался и он (Бейкон-2), либо с кем-нибудь, кто снимался с кем-нибудь, кто… (Бейкон-3, 4 и т. д.). В целом, утверждал он, «число Бейкона» почти всех актеров и актрис Голливуда не превышает 6. Например, у Элвиса Пресли оно равно 2. Связь между ними вы можете восстановить самостоятельно {1} . Кажется, что мир действительно тесен: в нем есть люди, у которых есть и число Эрдёша, и число Бейкона. Например, у Рона Грэма число Эрдёша равно 1, а число Бейкона – 2. А у знаменитой израильской актрисы Натали Портман число Эрдёша равно 5, а число Бейкона – 1 (этого вы не ожидали, правда?).
1
Для этого можно ввести в Google поисковый запрос «Elvis Presley Kevin Bacon». Элвис Пресли снимался в фильме «Смена привычки» (Change of Habit, 1969) с Эдвардом Аснером. Эдвард Аснер играл в фильме «Джон Ф. Кеннеди. Выстрелы в Далласе» (JFK, 1991), в котором снимался и Кевин Бейкон. Следовательно, у Аснера число Бейкона равно 1, а у Пресли (который никогда не играл в тех же фильмах, что и Бейкон) – 2.
Вернемся наконец к доказательству гипотезы Коллатца. Его не существует, и, по правде говоря, я знаю множество способов заработать 500 долларов, гораздо более простых, чем возня с этой задачей.
Загадка шахматной доски
Я несколько сомневался, говорить ли о следующей загадке. На самом деле она очень проста. Тем не менее после бурного спора с самим собой я решил все-таки рассказать о ней, потому что она весьма знаменита, причем и сама загадка, и ее решение замечательно красивы.
Рассмотрим сетку размером 8 x 8 ячеек.
Очевидно, всю эту сетку легко покрыть 32 костяшками домино размером 1 x 2 ячейки. А теперь уберем две клетки, расположенные в противоположных углах.
Можно ли покрыть получившуюся сетку всего 31 костяшкой?
Мои друзья (все они не математики, но по большей части люди весьма умные) в большинстве своем уверены, что можно, – нужно только сообразить, как именно их следует расположить.
Но правильный ответ на этот вопрос – «нет». Что бы мы ни делали, 31 костяшка домино не может покрыть сетку с удаленными противоположными угловыми клетками.
Почему это так, немедленно становится ясно, если взять вместо такой незакрашенной сетки черно-белую шахматную доску.
Как видно на рисунке, каждая костяшка домино может закрыть одну черную клетку и одну белую; поэтому 31 костяшка может закрыть в точности 31 белую клетку и 31 черную. Поскольку две клетки, удаленные с доски, одного и того же цвета – белые, – в обрезанной доске осталось 30 белых клеток и 32 черные. Много лет назад, когда я учился на математическом факультете в Тель-Авиве, я вел для «интересующейся наукой молодежи» курс под названием «Парадоксы, загадки и числа». Я давал эту задачу молодым слушателям своего курса. Каждый раз происходила одна любопытная вещь. Многие ученики решительно не соглашались с доказательством, которое показывает, что 31 костяшка домино не может покрыть доску с удаленными противоположными угловыми клетками. Интересно отметить, что в их число входили и ученики, казалось бы, вполне понимавшие объяснение этого доказательства; тем не менее они упорно раскладывали костяшки домино так и эдак, стараясь покрыть эту самую доску с обрезанными углами. Я даже не пытался убедить их в бессмысленности этого занятия – каждый должен учиться на собственных ошибках.
История учит нас, что люди и народы ведут себя мудро после того, как они исчерпают все остальные возможности.
Докажите, что, если из шахматной доски удалить любые две клетки разных цветов, все оставшиеся клетки всегда можно покрыть 31 костяшкой домино.
Бесконечные крестики-нолики
Когда я учился в начальной школе в Литве, в своем родном Вильнюсе, одним из самых значительных моих достижений было обретение виртуозного умения играть на уроках в стратегические игры с карандашом и бумагой и не попадаться учителям. Моей любимой игрой был бесконечный вариант крестиков-ноликов. Эта игра не раз спасала меня от скуки на занятиях, на которых меня заставляли сидеть.
Позвольте объяснить вам правила игры.
Вы, несомненно, знакомы с обычными крестиками-ноликами, в которые играют на поле размером 3 x 3 клетки. Эта игра подходит для детей лет до шести. После этого возраста каждая партия должна неизменно заканчиваться вничью, если только один из игроков не заснет в процессе игры (что, бесспорно, возможно, учитывая, насколько эта игра скучна).
В бесконечном варианте играют на бесконечном поле, и каждый игрок стремится выстроить ряд из пяти крестиков или ноликов. Как и в исходном варианте, ряд может быть горизонтальным, вертикальным или диагональным. Игроки по очереди ставят на поле крестики и нолики, и первый, выстроивший ряд из пяти своих символов, считается победителем.
a)
б)
a) У ноликов нет хода, который позволил бы заблокировать две «открытые» тройки крестиков; нолики проигрывают
б) Пример еще одной партии, которую только что выиграли крестики
В начальной школе, когда я «открыл» эту игру, я думал, что сам ее и изобрел, но впоследствии узнал, что это не так: существует игра под названием «гомоку», очень похожая на бесконечные крестики-нолики. Она особенно популярна в Японии и Вьетнаме. Слово го означает по-японски «пять».
Вы наверняка слышали об игре го. Однако, хотя в гомоку часто играют на такой же доске, какую используют для этой прославленной великой игры, между ними нет никакой связи. Го – древняя китайская игра, которая даже упоминается в «Аналектах» [2] Конфуция. Поскольку она попала на Запад через Японию, мы используем ее японское название, но, как я уже сказал, го – это не гомоку [3] {2} .
<2
Китайское название – «Лунь юй», первая из четырех книг конфуцианского канона. В русских переводах называется также «Беседы и суждения». – Здесь и далее, если не указано иное, постраничные примеч. перев.
3
Более того, даже кажущееся сходство названий этих игр случайно. Го моку означает по-японски «пять камней». Название же игры го происходит от слов и-го, японского перевода китайского названия вэй-ци, которое традиционно переводится на русский как «облавные шашки».
2
Го – это абстрактная стратегическая настольная игра для двух игроков, задача которых – окружить большую территорию, чем противник. Эта игра требует стратегического и тактического мастерства и большой наблюдательности. Гомоку (которую называют также «гобан», или «пять в ряд») – тоже абстрактная стратегическая настольная игра, и в нее традиционно играют шашками («камнями») для го на доске для го размером 15 x 15 или 19 x 19 клеток. Однако задача участника этой игры – первым выстроить ряд из пяти шашек. В эту игру также можно играть с карандашом и бумагой.
Несмотря на тот опыт, который я накопил, играя на уроках – а иногда и на переменах (хотя на переменах играть не так интересно – потому что это не запрещено!), я не мог понять, всегда ли игрок, начинающий первым (то есть играющий крестиками), выигрывает, если он применяет правильную стратегию, независимо от того, как играет его противник, или же партия всегда заканчивается вничью (точнее, не может закончиться никогда), если оба ее участника играют правильно. Интуиция подсказывала мне, что должна существовать какая-то стратегия, обеспечивающая победу игроку, делающему первый ход в партии.