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

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

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

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

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

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

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

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

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

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

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

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

Наименьшее такое R обозначается как R (f, k) и называется числом Рамсея. Из доказательства Сомса видно, что R (3,3) = 6. Числа Рамсея вычисляются с необычайным трудом, за исключением нескольких простых случаев. Известно, к примеру, что R (5,5) лежит в промежутке от 43 до 49, но его точное значение остается загадкой.

Рамсей доказал более общую теорему, в которой количество типов соединения (ножи, вилка, что угодно – чаще всего используются цвета, но Сомс использует то, что оказывается под рукой) может определяться любым конечным числом. Единственное известное нетривиальное число Рамсея для больше чем двух типов соединения – это R (3,3,3), равное 17.

Существуют бесчисленные обобщения этой идеи. Конкретное число, о котором идет речь, известно лишь в нескольких, очень немногочисленных, случаях. Вот статья, с которой все началось: F. P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society 30 (1930) 264–286. Как можно предположить по названию, автор думал о логике, а не о комбинаторике.

R. L. Graham and B. L. Rothschild, Ramsey theory, Studies in Combinatorics (ed. G.-C. Rota) Mathematical Association of America 17 (1978) 80–99.

В 1981 г. О. Свенсон опросил 161 шведского и американского студента, попросив каждого из них оценить свое мастерство и безопасность вождения по отношению к остальным участникам опроса. В отношении мастерства 69 % шведов оценили себя как выше среднего уровня; в отношении безопасности то же сделали 77 %. Для американских студентов цифры составили 93 % по мастерству и 88 % по безопасности. Мне довелось сдать два американских экзамена по вождению, один из которых проводился вообще без автомобиля, и я понимаю, почему американцы до такой степени преувеличивают свои способности. См.: O. Svenson, Are we all less risky and more skillful than our fellow drivers? Acta Psychologica 47 (1981) 143–148.

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

Не знаю, как вы, а я великолепно себя чувствую.

– Нужные нам числа – это 4 и 13, – сказал Сомс.

– Поразительно, просто поразительно. Я…

– Вы знакомы с моими методами, Ватсап.

– Тем не менее мне кажется замечательным, что вы можете вывести ответ из таких неопределенных разговоров.

– Хм. Посмотрим. Суть дела, Ватсап, состоит в том, что каждое утверждение, которое мы делаем, добавляет дополнительную информацию к тому, что знаем мы оба. И знаем, что оба знаем, и т. д. Предположим, что произведение двух нужных нам чисел равно p, а сумма равна s. Первоначально вы знаете p, а я знаю s. Мы оба знаем, что второй из нас знает то, что знает, но не знаем конкретного значения.

– Поскольку вы не знаете самих чисел, p не может быть произведением двух простых, таким как 35. Ведь 35 – это 5 × 7, и никак иначе выразить это число как произведение двух чисел, больших 1, невозможно, так что вы сразу поняли бы, какие два числа имеются в виду. По аналогичной причине p не может равняться кубу простого числа, такому как 5³ = 125, поскольку такое число раскладывается только как 5 × 25.

– Да, это понятно, – вставил я.

– Кроме того, p не может быть равно qm, где q – простое число, а m – составное, поскольку для любого d больше 1, которое является делителем m, qd будет больше 100.

– Ну, даааа…

– К примеру, p не может быть равным 67 × 3 × 5, что раскладывается на множители тремя способами: 67 × 15, 201 × 5 и 335 × 3. Поскольку в двух последних случаях используются числа больше 100, на эти способы разложения можно не обращать внимания, и остается только один способ, с числами 67 и 15.

– Верно.

– Итак, ваше замечание помогает мне понять все это, но к тому моменту я и сам сделал те же выводы на основании известной мне суммы чисел. Я видел, что s не является суммой двух таких чисел. Но затем вы тоже об этом узнали, потому что я вам сказал, то есть вы узнали кое-что новое о числе s. Конечно, оба мы должны помнить, что если s = 200, то оба числа должны равняться 100, а если s = 199, то они равняются 100 и 99.

– Разумеется.

– Если исключить невозможное… – сказал Сомс, – получится, что сумма s может равняться одному из следующих чисел: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51 и 53.

– Но раньше вы с большим пренебрежением отзывались о…

– О, в математике это правило достаточно хорошо работает, – небрежно ответил он. – Потому что здесь мы можем быть уверены, что невозможное на самом деле невозможно.