Математические головоломки профессора Стюарта Стюарт Иэн

Четыре псевдоку без указаний

Эти головоломки также исходят от Джерарда Баттерса, Фредерика Хенле, Джеймса Хенле и Колина МакГоги. См.: Gerard Butters, Frederick Henle, James Henle, and Colleen McGaughey. Creating clueless puzzles, The Mathematical Intelligencer 33 No. 3 (Fall 2011) 102–105.

Загадка похищенных бумаг

– Вор – Волверстон, – объявил Сомс.

– Ты уверен, Хемлок? От твоей правоты многое зависит.

– Никаких сомнений быть не может, Спайкрафт. Вот их заявления:

Арбатнот: Это сделал Берлингтон.

Берлингтон: Арбатнот лжет.

Волверстон: Это не я.

Гамильтон: Это сделал Арбатнот.

Мы знаем, что кто-то один из этих людей говорит правду, а остальные трое лгут. Существует четыре возможных варианта. Рассмотрим их по очереди.

Если только Арбатнот говорит правду, то из его слов нам становится известно, что виновен Берлингтон. Однако в этом случае Волверстон лжет, следовательно, виновен именно Волверстон. Это логическое противоречие, делаем вывод о том, что Арбатнот не говорит правду.

– Если только Берлингтон говорит правду, то…

– Волверстон лжет! – воскликнул я. – Так что виновен Волверстон!

Сомс сердито взглянул на меня – ведь я сорвал его эффектное выступление.

– Это так, Ватсап, и остальные заявления этому не противоречат. Так что мы уже знаем, что вор – Волверстон. Однако имеет смысл проверить и остальные два варианта, чтобы избежать даже малейшей возможности ошибки.

– Все абсолютно ясно, дружище, – сказал я.

Сомс достал трубку, но не стал ее зажигать.

– Если только Волверстон говорит правду, то заявление Берлингтона ложно, следовательно, Арбатнот говорит правду. Снова противоречие, поскольку известно, что он лжет. Если только Гамильтон говорит правду, возникает это же противоречие. Поэтому единственный возможный вариант – тот, где правду говорит только Берлингтон, и тогда вор – Волверстон. Как Ватсап проницательно заметил.

– Благодарю вас, джентльмены, – сказал Спайкрафт. – Я знал, что могу на вас положиться.

По его жесту в комнату тенью проскользнула какая-то фигура. Короткий разговор шепотом, и человек вновь исчез.

– В жилище доктора будет немедленно проведен обыск, – сказал Спайкрафт. – Я уверен, что документ будет найден.

– Значит, мы спасли империю! – воскликнул я.

– До следующего раза, когда кто-нибудь оставит секретные документы на сиденье какого-нибудь кэба, – сухо заметил Сомс.

По пути домой я прошептал на ухо своему спутнику:

– Сомс, если Спайкрафт – специалист по простым числам, то что он делает в контрразведке? Ведь здесь не может быть никакой связи, правда?

Он внимательно посмотрел на меня и покачал головой. Что имелось в виду – отсутствие связи, о которой я говорил, или предупреждение и совет не развивать эту тему, – мне неизвестно.

Еще одна любопытная числовая закономерность

123456  8 + 6 = 987654;

1234567 8 + 7 = 9876543;

12345678 8 + 8 = 98765432;

123456789 8 + 9 = 987654321.

Здесь не до конца ясно, что «должно» идти следующим: может быть,

234567890  8 + 10,

что равно 9876543130, так что закономерность на этом прекращается. Но, может быть, мне следовало взять (123456789) 10 + 10 = 12345678900. Тогда

12345678900 8 + 10 = 9876543210.

Далее

(12345678900) 10 + 11 = 123456789011,

что приводит нас к

12345689011 8 + 11 = 98765432099

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

Промежутки между простыми числами

Гипотеза Эллиота – Халберстама[37] носит очень специальный характер. Пусть (x) – число простых чисел, меньших или равных x. Для любого положительного целого q и a, не имеющего с q общих делителей, за исключением 1, пусть (x; q, a) – число простых чисел, меньших или равных x и равных a (mod q). Это приблизительно равно (x) / (q), где  – это пси-функция Эйлера, число целых чисел от 1 до q – 1, не имеющих с q общих делителей. Рассмотрим максимальную возможную ошибку:

Гипотеза Эллиота – Халберстама говорит о том, насколько велика эта ошибка: гипотеза утверждает, что для любых < 1 и A> 0 существует постоянная C> 0 такая, что

Знак одного. Часть вторая

Вот одно такое решение:

Объяснение см. в главе «Знак одного. Часть третья».

Евклидовы каракули

Вы могли бы сделать это вручную с использованием разложения на простые множители, если бы потратили на это день-другой. Вам пришлось бы выяснить, что

44 758 272 401 = 17 17 683 148 891;

13 164 197 765 = 5 17 683 148 891.

Затем вы могли бы сделать вывод, что НОД равен 17 683 148 891 = 2 632 839 553.

При использовании алгоритма Евклида весь расчет выглядит так:

(13 164 197 765; 44 758 272 401) (13 164 197 765; 31 594 074 636) (13 164 197 765; 18 429 876 871) (5 265 679 106; 13 164 197 765) (5 265 679 106; 7 898 518 659) (2 632 839 553; 5 265 679 106) (2 632 839 553; 2 632 839 553) (0; 2 632 839 553).

Следовательно, НОД равен 2 632 839 553.

123456789 раз по X

123456789 1 = 123456789;

123456789 2 = 246913578;

123456789 3 = 370370367;

123456789 4 = 493827156;

123456789 5 = 617283945;

123456789 6 = 740740734;

123456789 7 = 846197523;

123456789 8 = 987654321;

123456789 9 = 1111111101.

В этих числах присутствуют все девять ненулевых цифр в разном порядке, за исключением тех случаев, когда мы умножаем на число, кратное 3 (то есть на 3, 6 и 9).

Знак одного. Часть третья

Поскольку

62 = 7 9–1 = 7/0,(1) – 1,

мы можем воспользоваться представлением 7 через две единицы, чтобы получить 62 из четырех единиц.

Долгое время Сомс и Ватсап никак не могли выразить 138 через четыре единицы, но потом, воспользовавшись озарением Ватсапа про квадратные корни и факториалы и применив системный подход, они в конце концов выяснили, что 138 можно получить с использованием всего лишь трех единиц. Стартовой позицией, опять же, является семерка, выраженная через две единицы, и тогда

И наконец,

138 = 46/0,(1),

что, кстати говоря, представляет собой хитрый способ умножения на 3 с использованием всего одной дополнительной единицы.

Бросание монетки – несправедливый жребий

Persi Diaconis, Susan Holmes, and Richard Montgomery, Dynamical bias in the coin toss, SIAM Review 49 (2007) 211–223.

То же в популярном изложении: Persi Diaconis, Susan Holmes and Richard Montgomery, The fifty-one percent solution, What's Happening in the Mathematical Sciences 7 (2009) 33–45.

Аналогичные эффекты возникают при бросании костей – не только обычных кубиков, но и любых правильных многогранников. См.: J. Strzalko, J. Grabski, A. Stefanski, and T. Kapitaniak, Can the dice be fair by dynamics? International Journal of Bifurcation and Chaos 20 No. 4 (April 2010) 1175–1184.

Исключение невозможного

– Ваше упущение, – сказал Сомс, – состояло в том, что вы не заметили, что двигаться могут не только стаканы, но и налитое в них вино. Я просто возьму второй и четвертый стаканы и перелью их содержимое в седьмой и девятый.

Сила мидий

Monique de Jager, Franz J. Weissing, Peter M. J. Herman, Bart A. Nolet, and Johan van de Koppel. Levy walks evolve through interaction between movement and environmental complexity, Science 332 (4 June 2011) 1551–1553.

Доказательство шарообразности Земли

Мы видели, что при вычислении средних скоростей на фиксированном расстоянии нам следует использовать среднее гармоническое, а не среднее арифметическое значение. Гармоническое среднее возникает также при оценке расстояния между двумя аэропортами, если учитывать силу ветра, – по аналогичной, с небольшими отличиями, причине. Посмотрим на простую модель. Будем считать, что скорость самолета относительно воздуха равна c, летит он по прямой, а ветер дует строго вдоль этой прямой со скоростью w. Считаем, что c и w постоянны. Тогда a = c – w, b = c + w. Мы хотим оценить d на основании времен r и s. Чтобы избавиться от w, мы выразим a и b и получим a = d/r и b = d/s. Таким образом,

c – w = d/r, c+w = d/s.

Сложив, получим 2c = d (1/r + 1/s). Тогда c = d (1/r + + 1/s)/2. Если бы ветра не было, полет в одну сторону занял бы время t, где d = ct. Следовательно,

t = d/c = d/[d (1/r + 1/s)/2] = 1/[(1/r + 1/s)/2],

это и есть гармоническое среднее между r и s.

Короче говоря: если мы говорим о самолеточасах, то из этой простой модели воздействия ветра видно, что пользоваться следует гармоническим средним времени перелета в двух направлениях.

123456789 раз по X. Продолжение

123456789 10 = 1234567890;

123456789 11 = 1358024679;

123456789 12 = 1481481468;

123456789 13 = 1604938257;

123456789 14 = 1728395046;

123456789 15 = 1851851835;

123456789 16 = 1975308624;

123456789 17 = 2098765413;

123456789 18 = 2222222202;

123456789 19 = 2345678991.

В этих произведениях присутствуют все десять цифр 0–9 в некотором порядке, за исключением тех случаев, когда мы умножаем на число, кратное 3… Вплоть до 19, когда красивая закономерность останавливается (19 не кратно 3, но в ответе дважды встречается 9 и нет 0).

Но затем закономерность возобновляется:

Следующие исключения возникают на 28 и 29. На числах 30–36 все работает, на 37 вновь происходит сбой. На этом месте я прекратил вычисления. Что происходит дальше? Понятия не имею.

Загадка золотого ромба

Сомс затянул узел до конца, сплющил его и поднес к свету.

– Вот это да, пятиугольник! – изумленно воскликнул я.

– Точнее сказать, Ватсап, это похоже на правильный пятиугольник, у которого одна диагональ видима, а остальные три скрыты. Обратите внимание на отсутствие горизонтальной диагонали. Если ее добавить, к примеру, сложив полоску еще раз, то получится…

– Пятиконечная звезда! Пентаграмма! Ее используют в черной магии для вызова демонов!

Сомс кивнул.

– Но без этой последней складки и, соответственно, без одного ребра пентаграмма окажется неполной, и демон вырвется. Так что этот символ выражает угрозу выпустить в мир демонические силы, – он невесело улыбнулся. – Конечно, демонов в сверхъестественном смысле не существует, их невозможно ни вызвать, ни выпустить. Но вот люди демонического нрава, безусловно, существуют…

– Такие, к примеру, как в террористической организации Ал-Гебра! – воскликнул я. – Меня изгнали из Ал-Гебраистана оружием математического образования!

– Успокойтесь, Ватсап. Нет, я имел в виду скорее Матемагическую ассоциацию Нумерики. Это малоизвестная группа, и я сильно подозреваю, что она служит лишь официальным прикрытием для одной из дьявольских преступных схем Могиарти. Я сталкивался с ней и раньше, и теперь у меня в руках последнее, решающее звено, которое позволит нанести удар по зловещему профессору и навсегда разрушить эту часть его всемирной паутины преступлений. Если, конечно…

– Если что, Сомс?

– Если, конечно, мы сможем представить неопровержимые доказательства, когда дело дойдет до суда. Откуда мы знаем, что этот пятиугольник правильный?

– Но разве это не предельно просто?

– Напротив, вы скоро будете уверять меня, что это невероятно хитроумно и, может быть, вовсе не так, – хотя, говоря по существу, правильный ответ здесь совпадает с первой наивной догадкой. Осмелюсь предположить, что, как только мы установим этот факт, все остальное последует автоматически, но одного внешнего вида узла недостаточно. Однако я буду считать, что взаимное расположение линий на рисунке верно, так что у нас определенно есть пятиугольник с четырьмя диагоналями. Но действительно ли он правильный? В этом необходимо убедиться. Если это так, то этот факт должен следовать из постоянной ширины бумажной полоски. Обозначим углы так, как это делал великий Евклид из Александрии, и займемся геометрическими рассуждениями.

Я должен предупредить читателя, что остальная часть дискуссии будет интересна только тем, кто обладает некоторыми знаниями в евклидовой геометрии.

– Я начну, – объявил Сомс, – с нескольких простых наблюдений. Их можно доказать без большого труда с использованием базовой геометрии, так что подробности я опущу.

Во-первых, обратите внимание, что если две полоски, имеющие параллельные края, накладываются друг на друга, то в месте их перекрытия возникает ромб – параллелограмм, у которого все четыре стороны равны. Более того, если два таких ромба имеют одинаковую высоту и одинаковую сторону, то они конгруэнтны, то есть обладают одинаковыми размерами и формой. Следовательно, на диаграмме расплющенного узла присутствуют три конгруэнтных ромба.

– Почему только три? – спросил я в недоумении.

– Потому что CD и BE не совпадают с краями бумажной полоски, так что мы не можем пока сказать то же о ромбах CDRB или DESC. Вот почему я не провел линии CD.

Я, надо признаться, этого не заметил.

– В таком случае это невероятно тонкий момент, Сомс. Мало того, наше утверждение может оказаться попросту неверным!

Он почему-то вздохнул.

– Теперь мы переходим к центральному пункту моих рассуждений. Диагонали ромба рассекают его углы пополам, а противоположные углы равны, – Сомс отметил четыре угла греческой буквой (тета), см. рисунок слева.

По сходным причинам угол CAB также равен . Поскольку ромбы DEAT и PEAB конгруэнтны, я могу отметить буквой еще четыре угла. Получается рисунок справа.

– А теперь, Ватсап, скажите: что при взгляде на этот рисунок сразу же приходит в голову?

– На нем чертовски много букв , – без промедления отозвался я.

Он недовольно поморщился, и я услышал, как в горле у него что-то негромко зарокотало, не знаю уж почему.

– Это же очевидно, как шея высоченного жирафа, Ватсап! Посмотрите на треугольник EAB.

Я наше треугольник и внимательно рассмотрел его, поначалу ничего не понимая. Ну… В этом треугольнике тоже много отметок . Так, так… все его углы составлены из ! Теперь я понял.

– Сумма углов треугольника равна 180°, Сомс. В этом треугольнике углы равны , и 3. Их сумма 5 равна 180°, а значит, = 36°.

– Когда-нибудь из вас еще получится геометр, – сказал Сомс. – Остальное доказывается легко. Отрезки DE, EA, AB и BC равны по длине, поскольку являются сторонами конгруэнтных ромбов. Углы DEA, EAB и ABC равны между собой, поскольку располагаются в конгруэнтных ромбах, и один из них, EAB, равен 3 , то есть 108°. Так что все три угла равны 108°. Но этому же равен внутренний угол правильного пятиугольника.

– Так что точки D, E, A, B, C являются углами правильного пятиугольника, и я могу завершить рисунок, проведя отрезок CD! – воскликнул я. – Как неле… – я поймал краем глаза его взгляд. – Э-э, как элегантно, Сомс!

Он пожал плечами.

– Пустяк, Ватсап. Этого достаточно, чтобы покончить с Матемагической ассоциацией Нумерики и причинить Могиарти некоторые неудобства. Сам же он… Боюсь, он окажется куда более крепким орешком.

Почему пузырьки в пиве идут сверху вниз?

E. S. Benilov, C. P. Cummins, and W. T. Lee. Why do bubbles in Guinness sink? arXiv: 1205.5233 [physics. flu-dyn].

Собаки, дерущиеся в парке

– Собаки столкнулись через 10 секунд, – объявил Сомс.

– Поверю вам на слово, – сказал я. – Но удовлетворите мое любопытство: как вы получили эту цифру?

– Задача симметрична, Ватсап, а симметрия зачастую упрощает рассуждения. В описанных вами условиях три собаки всегда находятся в вершинах равностороннего треугольника. Он вращается и одновременно сжимается, но сохраняет форму. Таким образом, с точки зрения одной из собак – скажем, A, – она все время бежит по прямой к соседней собаке B.

– Но разве треугольник не вращается, Сомс?

– Вращается, но это несущественно, поскольку мы можем проводить вычисления во вращающейся системе координат. Важно, насколько быстро треугольник сжимается. Собака B всегда бежит под углом 60° к прямой AB, поскольку собаки всегда образуют равносторонний треугольник. Так что компонента ее скорости в направлении собаки A равна 1/2 4 = 2 ярда в секунду. Следовательно, A и B приближаются друг к другу с суммарной скоростью 4 + 2 = 6 ярдов в секунду и покрывают разделявшее их в начальный момент расстояние в 60 ярдов за 60/6 = 10 секунд.

Почему у моих друзей больше друзей, чем у меня?

Предположим, в социальной сети n человек, причем человек i имеет x_i друзей. Тогда среднее число друзей по все членам сети составляет

При рассмотрении столбца 3 в таблице – взвешенного среднего от числа друзей у каждого из друзей j человека i – мы используем стандартный математический прием и работаем вместо этого с человеком j. Этот человек фигурирует как друг у x_j человек – а именно у собственных друзей – и вносит x_j в подсчет полного количества у каждого из этих друзей. Так что случаи, когда человек j выступает в качестве друга, вносят вклад x_j в общую сумму. Число элементов в столбце 3 составляет x₁ + … + x_n. Так что взвешенное среднее числа друзей у каждого из друзей равно

Я утверждаю, что для любых x_j мы всегда имеем b>a, если только все x_j не равны, в каковом случае b = a. Это следует из стандартного неравенства, связывающего среднее с тем, что инженеры называют «среднеквадратичным значением» (это корень квадратный из среднего значения квадратов):

причем равенство достигается только при равенстве всех x_j. Возведя в квадрат и сгруппировав, получим a<b, за исключением случая равенства всех x_j, что и требовалось. Дополнительную информацию можно найти на сайте

http://www.artofproblemsolving.com/wiki/index.php?h2=Root-Mean_Square-Arithmetic_Mean-Geometric_Mean-Harmonic_mean_Inequality

Приключение шестерых гостей

Замечание Сомса – пример применения теории Рамсея – области комбинаторики, названной в честь Фрэнка Рамсея, доказавшего аналогичную, но более общую теорему в 1930 г. Его брат Майкл стал архиепископом Кентерберийским. Подойдем к нашему вопросу с осторожностью. Предположим, что некоторое число людей сидит за столом, причем каждый человек связан с другими либо ножом, либо вилкой. Выберем два произвольных числа f и k. Тогда существует некоторое число R, зависящее от f и k, такое, что если за столом присутствует по крайней мере R человек, то либо f из них соединены вилками, либо k – ножами.