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

Рамсей доказал более общую теорему, в которой количество типов соединения (ножи, вилка, что угодно – чаще всего используются цвета, но Сомс использует то, что оказывается под рукой) может определяться любым конечным числом. Единственное известное нетривиальное число Рамсея для больше чем двух типов соединения – это 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.

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

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

– Итак, на главной стадии рассуждений мы оба знаем то, что я только что вам рассказал. И в этот момент вы быстро объявляете, что можете определить нужные нам числа! Так что я быстро перебираю все возможные пары чисел с этими суммами и обнаруживаю, что 10 из 11 вариантов s имеет одно из возможных произведений, совпадающее с произведением для другого значения s . Поскольку вы сказали мне, что уже знаете нужные нам числа, все 10 таких s можно смело исключить из расследования. Остается единственный возможный вариант суммы, 17, и единственное произведение, не допускающее двух разных значений s . А именно 52, которое получится, если представить 17 как 4 + 13, и только в этом случае. Следовательно, два наших числа – это 4 и 13.

Я поздравил Сомса с такой проницательностью.

– Пошлите кого-нибудь из Нерушимых сил Бейкер-стрит к Роулейду с этим сообщением, – скомандовал он, быстро записывая числа на клочке бумаги. – Не пройдет и часа, как двое злоумышленников будут арестованы.

В 1930 г. Хайман Лоб и Херберт Ричмонд доказали, что в некоторых случаях жадный алгоритм дает лучшее решение, чем построение Малфатти. Ховард Ивз в 1946 г. заметил, что для равнобедренного треугольника с очень острой вершиной пирамидальное построение почти вдвое больше по площади, чем построение Малфатти. В 1967 г. М. Голдберг доказал, что жадный алгоритм всегда лучше варианта Малфатти, а в 1994 г. Виктор Залгаллер и Г. А. Лось доказали, что он всегда дает наибольшую возможную площадь.

M. R. Schroeder, Diffuse sound reflection by maximum-length sequence. Journal of the Acoustical Society of America 57 (1975) 149–150.