Число Эрдёша

Проблема прошлой недели была весьма остроумно решена читательницей, которая, к сожалению, позже удалила свой комментарий. Давайте посмотрим, как в своё время к ней подошли венгерские математики Пауль Эрдёш и Жорж Секереш, постоянные коллеги и соавторы теоремы Эрдёша-Секереша . Они исходили из принципа «ящика» и придумали разделить множество первых 2n чисел {1, 2, …, 2n} на n подмножеств таким образом, чтобы, взяв n + 1 число из исходного множества, по крайней мере два из них попали в одно и то же подмножество. Таким образом, если бы эти подмножества были таковы, что для любых двух чисел из одного и того же подмножества одно было бы кратно другому, исходное утверждение было бы доказано.

Для этой цели n подмножеств определяются как пересечения множества {1, 2, …, 2n} со следующими множествами: {1, 2, 2², 2³…}, {3, 3 x 2, 3 x 2², 3 x 2³…}, {5, 5 x 2, 5 x 2², 5 x 2³,…}, …, {n-1, (n-1) x 2, (n-1) x 2², n-1) x 2³…}, в которых каждый элемент делит следующий в своем подмножестве, и, кроме того, каждое число в исходном множестве {1, 2, …, 2n} может быть записано однозначно как (2m-1) x 2ᴷ, то есть оно принадлежит одному из этих множеств. Это довольно сложное объяснение, которое Бретос Бурсо резюмирует следующим образом:

Каждое натуральное число является произведением чётной и нечётной частей (произведением своих простых множителей, равных 2, и своих нечётных простых множителей). Если два различных числа имеют одинаковую нечётную часть, то одно из них делит другое (одно число, делящееся на 2 больше раз, чем другое, кратно другому). У взятых нами n + 1 чисел есть n возможных нечётных частей (1, 3, 5..., 2n-1), поэтому найдется по крайней мере два числа с одинаковой нечётной частью.

Говоря об Эрдёше и сотрудничестве между математиками, нельзя не упомянуть число Эрдёша . У плодовитого венгерского математика было не менее 509 непосредственных соавторов, число Эрдёша (nE) которых равно 1; те, кто сотрудничал с любым из этих 509, но не напрямую с Эрдёшем, имеют nE, равное 2 (то есть более шести тысяч), и так далее.

Как вы думаете, каким может быть ваше число Эрдёша, если использовать фермианскую оценку? Меня устроит разумное приближение. (Подсказка: если вы будете читать этот раздел регулярно, будет гораздо проще.)

Гипотеза Эрдеша-Секереша

Вышеупомянутую теорему Эрдёша-Секереша не следует путать с одноименной гипотезой.

Теорема утверждает, что для любой пары натуральных чисел (целых и положительных) r и s любая последовательность длины, равной или большей, чем (r-1)(s-1) + 1, содержит монотонно возрастающую подпоследовательность длины s или монотонно убывающую подпоследовательность длины r.

Звучит сложно, но простой пример прояснит концепцию: при r = 3 и s = 2, то есть (r-1)(s-1) + 1 = 3, любая перестановка трёх чисел имеет либо возрастающую подпоследовательность длины три, либо убывающую подпоследовательность длины два. Возьмём шесть возможных перестановок чисел 1, 2 и 3 (и запишем последовательности в упрощённом виде):

• 123 имеет в себе возрастающую подпоследовательность длины три: 123
• 132 имеет убывающую подпоследовательность длины два: 32
• 213 имеет убывающую подпоследовательность длины два: 21
• 231 имеет две убывающие подпоследовательности длины два: 21 и 31
• 312 имеет две убывающие подпоследовательности длины два: 31 и 32
• 321 имеет три убывающие подпоследовательности длины два: 32, 31 и 21

Как бы вы подошли к доказательству этой теоремы с точки зрения принципа «ящика»? (Я не прошу строгого доказательства, а лишь плана действий.)

Что касается гипотезы Эрдёша-Секереша, то она представляет собой обобщение «проблемы счастливого конца», названной так Эрдёшем, поскольку она привела к браку его друга и коллеги Жоржа Секереша с австралийским математиком Эстер Кляйн. Но это тема другой статьи.