Разложим по полочкам! Решения задач части 4.

Описание и условия задач

Решения задач части 1

Решения задач части 2

Решения задач части 3

Решения задач части 4

4.1Доказать, что среди $n+1$ различных натуральных чисел, не превышающих $2n$, найдутся а) три числа, одно из которых равно сумме двух других; б) два числа, одно из которых делится на другое.

а) Среди $n+1$ чисел $a_0$, $a_1$ … $a_n$ есть наименьшее. Будем считать, что это $a_0$. Рассмотрим $n$ разностей: $a_1 - a_0$, $a_2-a_0$ … $a_n-a_0$. Из того, что числа $\{a_i\}$ натуральные, различны между собой и не превышают $2n$ следует, что разности также натуральные и различны между собой, причем каждая разность меньше $2n$. Таким образом, числа $\{a_i\}$ вместе с разностями образуют $2n+1$ натуральных чисел, не превышающих $2n$, поэтому среди них найдутся одинаковые. Так как числа $\{a_i\}$, а также разности $a_1 - a_0$ различны между собой, одно из совпадающих чисел это $a_i$, а другое $a_j - a_0$. Таким образом $a_i = a_j - a_0$,  или  $a_j = a_0 + a_i$.

б) Рассмотрим наибольшие нечетные делители заданных чисел (которые для нечетных чисел совпадают с самими числами). Так как имеется $n$ нечетных чисел, не превышающих $2n$ (числа вида $2k-1$, где $1 \leqslant k \leqslant n$), то среди $n+1$ различных чисел найдутся два числа $a$ и $b$ ($a \lt b$), имеющие одинаковый наибольший нечетный делитель $q$. Таким образом $a=2^iq$,  $b=2^jq$  $(0 \leqslant i \lt j)$, следовательно $\frac{b}{a}=2^{j-i}$ — целое число.

4.2Каждая клетка прямоугольной доски размера 4×7 окрашена в белый или черный цвет. Доказать, что найдется прямоугольник, образованный строками и столбцами доски, все угловые клетки которого окрашены в одинаковый цвет. Привести пример раскраски прямоугольной доски размером 4×6, где такого прямоугольника не существует.

В каждом из 7 столбцов из четырех клеток можно найти 2 пары клеток таким образом, что в каждой паре клетки окрашены в одинаковый цвет. Действительно, если есть по две клетки каждого цвета, то выбор очевиден; в противном случае в столбце найдутся как минимум 3 клетки одинакового цвета, так что берем пары (1,2) и (1,3).

Таким образом на всей доске найдется не менее 14 пар, в каждой из которых клетки окрашены в одинаковый цвет. Согласно принципу Дирихле найдется как минимум 7 пар, соответствующих одному и тому же цвету.

Заметим, что каждый столбец допускает возможность выбора $C_4^2 = 6$ пар, поэтому (снова работает принцип Дирихле) из 7 выбранных пар, найдутся две пары с совпадающими номерами строк. Клетки этих пар составляют требуемый прямоугольник.

В случае доски размером $4×6$ в каждом столбце возьмем по две клетки каждого цвета и используем все 6 возможных выборов пар. Раскраска такого вида получается, например, из раскраски на приведенном рисунке отбрасыванием крайнего столбца слева или справа. Понятно, что в этом случае найти требуемый прямоугольник не удается.

4.3Дана группа из 15 человек, в которой из любых трех найдутся двое, знакомые друг с другом. Доказать, что из нее можно одновременно выделить три подгруппы из трех, четырех и пяти человек, в каждой из которых все знакомы друг с другом. А верно ли это для группы из 14 человек?

Согласно лемме Рамсея, получаем: $$ R(4,3) \leqslant R(3,3) + R(4,2) = 6 + 4 = 10 \label{eq:431}\tag{4.3.1} $$ откуда $$ R(5,3) \leqslant R(4,3) + R(5,2) \leqslant 10+5 = 15 \label{eq:432}\tag{4.3.2} $$

Неравенство $\eqref{eq:432}$ означает, что в группе из 15 человек найдется либо 5 попарно знакомых, либо 3 попарно незнакомых. Однако, ввиду условия задачи, вариант 3 попарно незнакомых невозможен. Значит 5 попарно знакомых обязаны быть. Из оставшихся 10 человек, согласно $\eqref{eq:431}$ найдутся 4 попарно знакомых. Остается еще 6 человек, из которых можно выбрать трех попарно знакомых.

A если в в группе только 14 человек?

Казалось бы для 14 человек следует искать контрпример, когда 5 попарно знакомых не существует. Однако, это не так. Присмотревшись к вычислениям в $\eqref{eq:431}$ можно заметить, что $R(3,3)$  и  $R(4,2)$ оба четны, поэтому неравенство леммы Рамсея можно усилить. Таким образом: $$ R(4,3) \leqslant R(3,3) + R(4,2) - 1 = 9 \\ R(5,3) \leqslant R(4,3) + R(5,2) \leqslant 14 $$

Таким образом, в группе из 14 человек также найдется 5 попарно знакомых, в оставшейся группе из 9 найдется 4 попарно знакомых. Остается 5 человек, и здесь приходится пасовать, так как мы знаем, что среди пяти человек может не оказаться трех попарно знакомых. Однако двое знакомых из пяти обязательно будут, а среди оставшихся трех найдутся еще двое знакомых. Таким образом, «в группе из 14 человек, таких что из любых трех найдутся двое знакомых друг с другом можно одновременно выделить четыре подгруппы из двух (две подгруппы), четырех и пяти человек, в каждой из которых все знакомы друг с другом».

Кстати, последние оценки для чисел Рамсея являются точными: $R(4,3)=9$ и $R(5,3)=14$. Отсюда можно получить оценку для $R(4,4)$: $$ R(4,4) \leqslant R(4,3) + R(3,4) = 18, $$ которая тоже точна!

Ниже приведены графы Рамсея, доказывающие точность $R(5,3)$ (13 вершин) и $R(4,4)$ (17 вершин). Как видно из вышеприведенных вычислений, точность $R(4,3)$ следует из точности $R(5,3)$ или $R(4,4)$, хотя граф Рамсея $R(4,3;8)$ тоже известен.

$R(5,3;13)$

$R(4,4;17)$

4.4На плоскости отмечено 35 точек, так что две точки из любых трех находятся на расстоянии менее 1 друг от друга. Доказать, что существует 18 точек, расстояние между любыми двумя из которых меньше 2.

Пусть $A$ – произвольная из отмеченных 35 точек. Если все остальные точки находятся от $A$ на расстоянии меньшем 1, то, согласно неравенству треугольника, расстояние между любой парой точек меньше 2 и утверждение доказано.

Предположим, что среди отмеченных существует точка $B$, находящаяся от $A$ на расстоянии не меньшем 1, и пусть $C$ – произвольная из заданных точек, отличная от $A$  и  $B$. По условию две из трех точек $A$, $B$  и  $C$ должны друг от друга находиться на расстоянии меньшем 1. Так как расстояние между $A$  и  $B$ не меньше 1, то точка $С$ находится на расстоянии меньшем единицы от $A$ или $B$.

Пусть $M_A$ и $M_B$ множества точек, отстоящих соответственно от $A$  и  $B$ на расстоянии меньшем 1. Если точка находится на расстоянии меньшем 1 от $A$  и  $B$ одновременно, выберем множество произвольно. Тогда каждая из остальных 33 точек войдет в одно из множеств, следовательно в каком-то из множеств будет не менее 17 точек.

Пусть для определенности множество $M_A$ содержит не менее 17 точек. Согласно неравенству треугольника расстояние между любыми двумя точками множества $M_A$ меньше 2. Вместе с точкой $A$ получаем не менее 18 точек, расстояние между любыми двумя из которых меньше 2.

4.5В стране 2018 городов, и из каждого выходит не менее 93 дорог. Известно, что из любого города можно проехать по дорогам в любой другой. Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)

Всероссийская математическая олимпиада, 1993 год. Окружной тур. По книге «Всероссийские олимпиады школьников по математике 1993-2006» под ред. Н.Х.Агаханова, М МНЦМО, 2007. Задача 24. В оригинале 1993 города.

Допустим, что утверждение неверно, и существуют города́ $A$ и $B$, такие что из одного в другой можно добраться, сделав не менее 63 пересадок, то есть как минимум по 64 дорогам. Разобьем все города на множества следующим образом: Множество $M_0$ — город $A$, множество $M_n$ — множество городов по которым от $A$ можно добраться не менее чем по $n$ дорогам, то есть сделав, как минимум, $n-1$ пересадок. Таким образом получим не менее 65 множеств, включая $M_0$.

Рассмотрим группу из трех последовательных множеств: $M_k$, $M_{k+1}$, $M_{k+2}$. Поскольку множеств не менее 65, получим как минимум 21 полную (трех-элементную) группу и одну группу, содержащую не менее двух элементов. Всего городов 2018, следовательно, согласно принципу Дирихле, существует группа, содержащая не более $\left\lfloor\dfrac{2018}{22}\right\rfloor = 91$ города.

С другой стороны, известно, что из каждого города множества $M_{k+1}$ исходит не менее 93 дорог, причем каждая дорога ведет либо в город из $M_{k}$, либо в город из $M_{k+2}$. (В случае неполной группы множеств все дороги ведут в $M_{k}$, но это не влияет на рассуждения.) Так как во множестве $M_{k+1}$ есть как минимум 1 город, получаем как минимум 93 го́рода во множествах $M_{k}$ и $M_{k+2}$ в совокупности, что вместе с городом из $M_{k+1}$ составляет не менее 94 городов в каждой группе. Получаем противоречие с предыдущим утверждением о существовании группы, содержащей не более 91 города.

4.6Множество чисел от 1 до 100 включительно чисел разбито на 7 подмножеств. Доказать, что хотя бы в одном из этих подмножеств найдутся либо четыре числа $a$,$b$,$c$,$d$, таких что $a+b=c+d$, или три числа $e$,$f$,$g$,  для которых $e+f = 2g$.

Олимпиада Югославии, 1981 год.

Угадайте с чего начнем. Все правильно: 100 чисел, 7 подмножеств, даже ящики искать не надо! Таким образом, одно подмножество содержит не менее … беру калькулятор … 15 чисел. Хотите продолжить самостоятельно? Нет — vamos adelante!

Для каждой пары из 15 выбранных чисел будем выписывать их разности (вычитаем из большего меньшее). Таких разностей будет $\frac{15 \cdot 14}{2}$, причем они могут принимать лишь 99 значений: $1,2...99$. Тут и калькулятор не нужен дабы убедиться, что найдутся две разности, имеющие одинаковые значения. Таким образом получаем, $$ a-b = c-d, \label{eq:461}\tag{4.6.1} $$ откуда $a+d = b+c$, что и ... Стоп! Говоря языком программистов, здесь есть небольшой «глюк». Понятно, в чем дело?

Дело в том, что один элемент принимает участие в нескольких парах, так что нет гарантии, что среди $a$, $b$, $c$   и   $d$ нет одинаковых. Если одинаковых нет, тогда действительно доказательство завершено. А если одинаковые есть?

Заметим, что числа одной пары различны, таким образом $a \ne b$  и   $c \ne d$. Кроме того, если $a = c$, то из $\eqref{eq:461}$ следует $b = d$, тогда как о том, чтобы оба элемента пары совпадали, мы никак не договаривались. Аналогичное фиаско получаем, полагая $b = d$.

Таким образом, возможно либо $a=d$, тогда из $\eqref{eq:461}$ получаем $b+c=2a$, либо $b=c$, откуда $a+d=2b$. Вот теперь всё!

4.7На прямой расположены $n^2+1$ отрезков. Доказать, что из них можно выбрать либо $n+1$ непересекающихся отрезков, либо $n+1$ отрезков, имеющих общую точку.

Олимпиада Чехословакии, 1979 год.

Выберем на прямой положительное направление и будем сравнивать отрезки по левому (начальному) концу: отрезок предшествует другому если его левый конец лежит не правее (т.е левее или совпадает) левого конца другого отрезка. Начнем по-порядку присваивать каждому отрезку число от 1 до $n$ включительно, так, чтобы это число не совпадало с числом никакого уже пронумерованного (т.е. предшествующего) отрезка, пересекающего данный.

При этом возможно два случая:

1. Какому-то отрезку присвоить номер не удалось. Это означает, что имеется $n$ предшествующих отрезков, пресекающих данный. В этом случае левый конец данного отрезка принадлежит $n+1$ отрезкам одновременно. Как видим принцип Дирихле здесь не понадобился. Однако следует рассмотреть еще один случай:

2. Каждому отрезку удалось присвоить номер. Другими словами, нам удалось поместить $n^2+1$ отрезков в $n$ «ящиков». Это значит, что найдется номер, присвоенный $\left\lceil\frac{n^2+1}{n}\right\rceil = n+1$ отрезкам. Согласно правилу присваивания номеров эти $n+1$ отрезков не пересекаются.

4.8Доказать, что в любой последовательности из $mn+1$ различных вещественных чисел можно выбрать либо возрастающую подпоследовательность из $m+1$ чисел, либо убывающую подпоследовательность из $n+1$ чисел.

Источник: "Problem Set 7. Pigeonhole Principle", автор Harm Derksen. Ну и задачи! Приводимая здесь — далеко не самая сложная из них. Неужели в Мичиганском университете их запросто решают? Скорее всего просто для саморекламы.

Каждому числу $a_i$ из последовательности $a_1, a_2 ... a_{mn+1}$ поставим в соответствие парy чисел $(p_i, q_i)$, гдe

• $p_i$ – длина наибольшей (по количеству членов) возрастающей подпоследовательности, оканчивающейся членом $a_i$;
• $q_i$ – длина наибольшей убывающей подпоследовательности, оканчивающейся членом $a_i$;

Если утверждение задачи неверно, то найдется последовательность из $mn+1$ различных вещественных чисел, для которой $p_i \leqslant m$  и  $q_i \leqslant n$ для всех $i$. В этом случае возможно не более $mn$ различных пар, поэтому среди $mn+1$ пар $(p_i, q_i)$ найдутся две одинаковые, соответствующие элементам последовательности $a_j$ и $a_k$ $(j \lt k)$. Таким образом $p_j = p_k$  и  $q_j = q_k$  $(j \lt k)$. Покажем, что это невозможно.

а) Пусть $a_j \lt a_k$. Рассмотрим наибольшую возрастающую подпоследовательность оканчивающуюся в $a_j$. Эта последовательность состоит из $p_j$ элементов. Добавив к ней $a_k$ получаем возрастающую подпоследовательность из $p_j+1$ элементов, оканчивающуюся в $a_k$. Следовательно $p_k \gt p_j$ и пары не могут быть одинаковыми.

б) Пусть $a_j \gt a_k$. Рассмотрим наибольшую убывающую подпоследовательность оканчивающуюся в $a_j$. Эта последовательность состоит из $q_j$ элементов. Добавив к ней $a_k$ получаем убывающую подпоследовательность из $q_j+1$ элементов, оканчивающуюся в $a_k$. Следовательно $q_k \gt q_j$ и пары снова не могут быть одинаковыми.

Утверждение доказано.

Заметили, где используется различие элементов последовательности?.. Разумеется, в строгости неравенств. Если отказаться от этого условия, то хотя бы одно из неравенств следует сделать нестрогим. Например, замена в б) неравенства $a_j \gt a_k$  на  $a_j \geqslant a_k$, соответствует следующему утверждению:

В любой последовательности из $mn+1$ вещественных чисел можно выбрать либо возрастающую подпоследовательность из $m+1$ чисел, либо невозрастающую подпоследовательность из $n+1$ чисел.

4.9Дано 2018 множеств по 45 элементов в каждом, при этом каждая пара множеств имеет в точности один общий элемент. Доказать, что существует элемент, принадлежащий всем 2018 множествам.

Олимпиада «Австрия—Польша», 1978 год. В оригинале 1978 множеств и 40 элементов.

Пусть $X$ заданная совокупность из 2018 множеств. Возьмем произвольное множество $A_0 \in X$ имеющее 45 элементов $a_1$,$a_2$ … $a_{45}$. При этом $A_0$ имеет в точности один общий элемент с каждым из остальных 2017 множеств.

Каждому из $a_i$ поставим в соответствие совокупность множеств $Z_i$ из $X$, для которым $a_i$ служит общим элементом с $A_0$. Другими словами $$ Z_i = \{ M \in X\;|\;M \cap A_0 = \{a_i\}\}\; \text{или просто}\; Z_i = \{ M \in X\;|\; a_i \in M\}. $$

Легко видеть, что соответствие является взаимно однозначным и распределяет 2017 множеств по 45 совокупностям $\{Z_i\}_{i=1}^{45}$. Таким образом, найдется совокупность $Z_k$, соответствующая элементу $a_k = a$, содержащая не менее $\left\lceil\frac{2017}{45}\right\rceil = 45$ множеств $\{А_i\}_{i=1}^{45}$, которые вместе с $A_0$ образуют 46 множеств $А_0, А_1, ... А_{45}$, содержащих элемент $a$.

Покажем, что элемент $a$ содержится также во всех остальных множествах из $X$. Допустим, что существует множество $B \in X$, не содержащее $a$. Пусть $b_i$ – общий элемент множества $B$  с  $A_i$  $(i=0,1...45)$. Тогда каждое из $b_i$ отлично от $a$. Покажем, что среди $b_i$ нет одинаковых.

Действительно, если $b_j=b_k=b$ $(0 \leqslant j \lt k \leqslant 45)$, то $b$ является общим элементом множеств $A_j$  и  $A_k$. Но $a$ также является общим элементом множеств $A_j$  и  $A_k$, а двух общих элементов множества иметь не могут.

Из вышесказанного следует, что множество $B$ содержит как минимум 46 различных элементов, что противоречит условию. Красивейшая задача!

Описание и условия задач

Решения задач части 1

Решения задач части 2

Решения задач части 3

Решения задач части 4