Хаим Шапира - Восемь этюдов о бесконечности. Математическое приключение

Мудрость – это знать, что не знаешь того, чего не знаешь, и знаешь то, что знаешь. Глупость – это думать, что знаешь то, чего не знаешь, или не знаешь того, что знаешь.

Пал Эрдёш был математиком исключительно плодовитым. Его превосходную биографию можно найти в книге Пола Хофмана «Человек, который любил только числа» (The Man Who Loved Only Numbers, 1998). Он написал более 1400 научных статей. Эрдёш был страстным поборником командной работы и сотрудничества, и за годы его научной деятельности вместе с ним над его статьями работали целых 511 математиков. Любому математику, который когда-либо писал статью в соавторстве с самим Эрдёшем, присваивается престижное число Эрдёша, равное 1. Те, кто сотрудничал с его соавторами, но не с самим Эрдёшем, получают число Эрдёша, равное 2. Аналогичным образом по мере все большего удаления присваиваются числа Эрдёша, равные 3, 4 и так далее. Общее правило таково: если вы сотрудничаете с человеком, наименьшее число Эрдёша которого равно k , то ваше число Эрдёша равно k + 1. Сам Эрдёш был единственным человеком с числом Эрдёша, равным 0. На противоположном конце спектра находятся те, кто никогда не писал статей с Эрдёшем и никогда не писал статей ни с кем из имеющих конечное число Эрдёша: их число Эрдёша равно бесконечности (∞). «Бесконечное число Эрдёша» звучит весьма престижно – может быть, даже престижнее, чем, скажем, «число Эрдёша 7», – но многие из вас, наверное, удивятся, узнав, что ваше собственное число Эрдёша (как и у большей части человечества) как раз и равно бесконечности. Я сам не пишу статей, но однажды принимал участие в совместной работе над статьей с математиком, число Эрдёша которого равнялось 3, так что я, даже не стремясь к тому, стал гордым обладателем числа Эрдёша, равного 4.

Это напоминает популярную салонную игру «Шесть шагов до Кевина Бейкона». Знаменитый голливудский актер Кевин Бейкон заявил однажды, что все до единого актеры в Голливуде либо снимались с ним вместе (Бейкон‐1), либо снимались с кем-нибудь, с кем снимался и он (Бейкон‐2), либо с кем-нибудь, кто снимался с кем-нибудь, кто… (Бейкон‐3, 4 и т. д.). В целом, утверждал он, «число Бейкона» почти всех актеров и актрис Голливуда не превышает 6. Например, у Элвиса Пресли оно равно 2. Связь между ними вы можете восстановить самостоятельно {1} 1 Для этого можно ввести в Google поисковый запрос «Elvis Presley Kevin Bacon». Элвис Пресли снимался в фильме «Смена привычки» (Change of Habit, 1969) с Эдвардом Аснером. Эдвард Аснер играл в фильме «Джон Ф. Кеннеди. Выстрелы в Далласе» (JFK, 1991), в котором снимался и Кевин Бейкон. Следовательно, у Аснера число Бейкона равно 1, а у Пресли (который никогда не играл в тех же фильмах, что и Бейкон) – 2. . Кажется, что мир действительно тесен: в нем есть люди, у которых есть и число Эрдёша, и число Бейкона. Например, у Рона Грэма число Эрдёша равно 1, а число Бейкона – 2. А у знаменитой израильской актрисы Натали Портман число Эрдёша равно 5, а число Бейкона – 1 (этого вы не ожидали, правда?).

Вернемся наконец к доказательству гипотезы Коллатца. Его не существует, и, по правде говоря, я знаю множество способов заработать 500 долларов, гораздо более простых, чем возня с этой задачей.

Я несколько сомневался, говорить ли о следующей загадке. На самом деле она очень проста. Тем не менее после бурного спора с самим собой я решил все-таки рассказать о ней, потому что она весьма знаменита, причем и сама загадка, и ее решение замечательно красивы.

Рассмотрим сетку размером 8 × 8 ячеек.

Очевидно, всю эту сетку легко покрыть 32 костяшками домино размером 1 × 2 ячейки. А теперь уберем две клетки, расположенные в противоположных углах.

Можно ли покрыть получившуюся сетку всего 31 костяшкой?

Мои друзья (все они не математики, но по большей части люди весьма умные) в большинстве своем уверены, что можно, – нужно только сообразить, как именно их следует расположить.

Но правильный ответ на этот вопрос – «нет». Что бы мы ни делали, 31 костяшка домино не может покрыть сетку с удаленными противоположными угловыми клетками.

Почему это так, немедленно становится ясно, если взять вместо такой незакрашенной сетки черно-белую шахматную доску.