м, что математику превратили в эффектный карточный фокус. И сделал это не Гудунни. Он, по обыкновению, просто стащил этот фокус у его изобретателя Артура Бенджамина – математика и иллюзиониста из колледжа Харви Мадда в Калифорнии.
Парадокс с зигзагом
Ни одна из представленных фигур не является треугольником. У первой «гипотенуза» слегка выпирает вверх, у второй – слегка уходит вниз. Именно в этом месте скрывается недостающий квадратик.
Дверца страха
Сомс удовлетворенно кивнул.
– Я понял, Ватсап, как надо! Ветрянка выходит, Геморрой выходит, Аневризма выходит, Ветрянка возвращается внутрь, Ботулизм выходит, Ветрянка выходит.
Мы начали деликатный процесс выманивания кошек через кошачью дверцу и запихивания их обратно внутрь.
– Осторожно, Сомс! – прошептал я. – Одна ошибка, и весь этот район превратится в дымящуюся воронку. Я пока не хочу предстать перед райскими вратами, да и кошек своих туда отправлять тоже не хочу. На мне брюки неглаженные, да и кошек неплохо бы причесать.
– Не беспокойтесь, Ватсап, – отозвался Сомс, хватая Ветрянку, пока несчастное животное не успело сигануть через изгородь. – Мое решение верно, не сомневайтесь.
– Я и не сомневаюсь в вашем решении, Сомс, – ответил я, лихорадочно пытаясь отыскать рядом что-нибудь прочное, за чем можно было бы спрятаться. – Э-э… а как вы пришли к этим выводам?
Он позаимствовал у меня блокнот и карандаш.
– Существует 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, P4 = 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².
То есть
r² – 34r + 145 = 0.
Я уставился на записанные символы, временно остановившись.
– Квадратный двучлен раскладывается на множители, Ватсап:
(r – 29) (r – 5) = 0.
– Да, точно! И это означает, что его решения равны r = 29 и r = 5.
– Да. Но вы должны помнить, что диаметр колеса равен 2r, то есть 58 или 10. Однако решение 10 дюймов нам не подходит, поскольку диаметр тележного колеса не может быть меньше 20 дюймов. Значит, остается только…
– …58 дюймов, – закончил я за него.
Загадка гусиного клина
Florian Muijres and Michael Dickinson, Bird flight: Fly with a little flap from your friends, Nature 505 (16 January 2014) 295–296.
Steven J. Portugal and others, Upwash exploitation and downwash avoidance by flap phasing in ibis formation flight, Nature 505 (16 January 2014) 399–402.
Поразительные квадраты
Основная идея здесь может быть выражена в совершенно общем виде с использованием алгебры, но я обойдусь без формальностей и проиллюстрирую ее примером. Взгляните на процесс в обратном порядке: начинаем
с 9² + 5² + 4² = 8² + 3² + 7²
и расширяем до
89² + 45² + 64² = 68² + 43² + 87².
Первое равенство несложно проверить, с этого все и начинается, но почему второе уравнение тоже верно?
Реальная величина двузначного числа [ab] составляет 10a + b. Поэтому левую часть уравнения можно записать как
(10 × 8 + 9)² + (10 × 4 + 5)² + (10 × 6 + 4)²,
что равняется
100 (8² + 4² + 6²) + 20 (8 × 9 + 4 × 5 + 6 × 4) + 9² + 5² + 4².
Аналогично правая часть уравнения превращается в
100 (6² + 4² + 8²) + 20 (6 × 8 + 4 × 3 + 8 × 7) + 8² + 3² + 7².