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

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

– Задача симметрична, Ватсап, а симметрия зачастую упрощает рассуждения. В описанных вами условиях три собаки всегда находятся в вершинах равностороннего треугольника. Он вращается и одновременно сжимается, но сохраняет форму. Таким образом, с точки зрения одной из собак – скажем, 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 за исключением случая равенства всех x_j, что и требовалось. Дополнительную информацию можно найти на сайте

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. Как можно предположить по названию, автор думал о логике, а не о комбинаторике.