Банк задач по математике

Задача 4.3.1

Среди любых четырёх из 8000 студентов можно выбрать слаженную тройку (т.е. тройку, составляющую слаженную команду на олимпиаду по программированию). Докажите, что можно выбрать 5 студентов, любая тройка из которых является слаженной.

?

Задача 4.3.2

(1)(2)(3)(4)

?

(1)

Среди любых 5 точек общего положения на плоскости найдётся выпуклый 4-угольник.

(2)

Найдётся 8 точек общего положения на плоскости, среди которых нет выпуклого 5-угольника.

(3)

Среди любых 9 точек общего положения на плоскости найдётся выпуклый 5-угольник.

(4)

Теорема Эрдёша–Секереша. Для некоторого $n$ среди любых $n$ точек общего положения на плоскости найдётся выпуклый 10-угольник. (Ср. с задачей 4.4.4.)

Числом Рамсея для гиперграфов $R_l(m_1, \ldots , m_k)$ , $m_1, \ldots , m_k \geqslant l$ , называется минимальное из таких целых положительных чисел $x$ , что для любой раскраски всех $l$ -элементных подмножеств $x$ -элементного множества в $k$ цветов найдутся $i$ и подмножество размера $m_i$ , у которого все $l$ -элементные подмножества покрашены в $i$ -й цвет. («Число Рамсея для гиперграфов» --- единый термин, определённый выше; знание термина «гиперграф» не нужно для его понимания.)

Например, очевидно, что $R_2(m_1, \ldots , m_k) = R(m_1, \ldots , m_k)$ и $R_3(3, n) = n$ . В задаче 4.3.1 требуется доказать, что $R_3(5,4) \leqslant 8\, 000$ . А при решении задачи 4.3.2(4) требуется доказать, что $R_3(10,10)$ или $R_4(5,10)$ существует.

Задача 4.3.3

(1)(2)(3)

?

(1)

Число $R_l(m_1, \ldots , m_k)$ существует для любых $m_1, \ldots , m_k$ . (Это не очевидно!)

(2)

$R_l(m_1, \ldots , m_k) \leqslant R_l(R_l(m_1, m_2), m_3, \ldots , m_k)$ .

(3)

$R_l(m, n) \leqslant R_{l-1}(R_l(m-1, n), R_l(m, n-1)) + 1$ .

Задача 4.3.4

(1)(2)(3)

?

(1)

Если $\binom {r}{n} < 2^{\binom {n}{3}-1}$ , то $R_3(n, n) > r$ .

(2)

Найдётся такое число $c > 0$ , что $R_3(n, n) \geqslant 2^{cn^2}$ .

(3)

Найдите нижние оценки на $R_l(\underbrace{n, \ldots , n}_{k})$ , аналогичные утверждениям 4.1.5(1, 2) (ср. с задачей 4.2.7).

Известно, что $R_l(\underbrace{n, \ldots , n}_{r^{2r}+1}) \geqslant (l-1)r^{r^{\cdots^{r}}}$ (степенная башня высотой $n$ ).

Числа Рамсея для гиперграфов