Ознакомительная версия.
Строки 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².
Сравнивая эти выражения, обнаруживаем, что первые слагаемые в них равны, потому что 6² + 4² + 8² (это то же, что 8² + 4² + 6², только в другом порядке); третьи слагаемые равны, потому что мы, собственно, с этого начали. Поэтому нам достаточно посмотреть, равны ли в этих выражениях вторые слагаемые, то есть действительно ли
8 × 9 + 4 × 5 + 6 × 4 = 6 × 8 + 4 × 3 + 8 × 7.
Если посчитать, то и другое равно 116.
Все вышесказанное сработало бы нисколько не хуже, если бы мы вместо 8, 4 и 6 использовали любые другие три однозначных числа. Так что нам, чтобы сделать конечные выражения верными, нужно просто выбрать эти числа.
Дальнейшие этапы можно объяснить аналогично.
С некоторыми подсказками и наводящими вопросами Сомса я через некоторое время понял, что ключом к этой загадке является уравнение 111 = 3 × 37. Оказалось, что трехзначные числа, которые после моей процедуры дают длинный ряд одинаковых цифр, кратны 3. К примеру, именно так обстоит дело для чисел 123, 234, 345, 456 и 126. Для таких чисел моя процедура эквивалентна умножению меньшего числа, равного трети от исходного, на 3 × 37, то есть на 111.
В качестве примера рассмотрим предложенное Сомсом число 486. Это 3 × 162. Поэтому умножить 486486486486486486 на 37 – это то же самое, что умножить 162162162162162162 на 111. Поскольку 111 = 100 + 10 + 1, это можно сделать путем сложения чисел
16216216216216216200
1621621621621621620
162162162162162162
Начиная справа налево, получаем 0 + 0 + 2 = 2, затем 0 + 2 + 6 = 8. После этого получаем 2 + 6 + 1, 6 + 1 + 2, 1 + 2 + 6 снова и снова, пока не доберемся до левого конца. Складывая одни и те же три числа в разном порядке, получаем в каждом случае, естественно, один и тот же результат – а именно 9.
Когда Сомс в первый раз объяснил мне все это, у меня нашлось возражение.
– Да, но что если при сложении этих трех чисел получается больше 9? Возникнет перенос в следующий разряд!
Он ответил кратко и по существу.
– Ну да, Ватсап, каждый раз один и тот же перенос.
В конце концов я понял, что это означало все то же самое – многократное повторение одной и той же цифры.
– Существуют, конечно, и более формальные доказательства, – заметил Сомс, – но мне кажется, этот пример вполне проясняет общую идею.
После этого он вернулся в кресло с кипой газет и весь остальной вечер молчал, а я спустился вниз, чтобы выпросить у миссис Сопсвудс тарелку сэндвичей с горгонзолой.
[На написание этой главы меня вдохновили кое-какие наблюдения Стивена Гледхилла.]
Мы используем не то среднее. Нам нужно среднее гармоническое (что это такое, объясняется ниже), а не среднее арифметическое.
Обычно мы определяем «среднюю скорость» какого-то путешествия как полное проделанное расстояние, деленное на полное затраченное время. Если путешествие разбито на несколько этапов, то средняя скорость, как правило, не является средним арифметическим скоростей на этих отрезках. Если отрезки преодолеваются за равное время, среднее арифметическое годится, но если они имеют равную длину (как и обстоит дело в нашем случае), то это не так.
Сначала рассмотрим случай с равными временны́ми отрезками. Предположим, что машина едет со скоростью a время t, а затем со скоростью b то же время t. Полное расстояние, равное at + bt, занимает время 2t. Поэтому средняя скорость равна (at + bt)/2t, что равно (a + b)/2, то есть среднему арифметическому скоростей.
Ознакомительная версия.
