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

Задача 4.2.1

(1)(2)(3)

?

(1)

На плоскости отметили 17 точек и соединили каждые 2 из них цветным отрезком: красным, жёлтым или зелёным. Тогда есть одноцветный треугольник.

(2)

Придумайте 9 точек на плоскости и раскраску в 3 цвета всех соединяющих их отрезков, для которой нет одноцветного треугольника.

(3)

То же, что в п. (2), для 16 точек.

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

Например, очевидно, что $R(1, m, n) = 1$ и $R(2, m, n) = R(m, n)$ для любых $m, n$ . В задаче 4.2.1 доказано, что $R(3,3,3) \leqslant 17$ , $\geqslant 10$ и $\geqslant 17$ . Но не очевидно, что такое число существует для любых $m_1, \ldots , m_k$ .

Задача 4.2.2

(1)(2)(3)

?

(1)

$R(m, n, p) \leqslant R(R(m, n), p)$ .

(2)

$R(m_1, m_2, \ldots , m_k) \leqslant R(m_1 - 1, m_2, \ldots , m_k) + R(m_1, m_2 - 1, \ldots , m_k) + \ldots + R(m_1, m_2, \ldots , m_k - 1)$ .

(3)

Найдите оценку на $R(m_1, m_2, \ldots , m_k)$ через полиномиальные коэффициенты.

Подробнее см. [w2] и [Ga].

Задача 4.2.3

Если рёбра графа $K_{31}$ раскрашены в синий, белый и красный цвета так, что нет ни синей 4-клики, ни белой 3-клики, ни красной 3-клики, то из каждой вершины выходит 14, 15 или 16 синих рёбер.

?

Задача 4.2.4

Теорема. Для любого целого $m > 0$ существует такое $M > 0$ , что для любого простого числа $p > M$ сравнение $x^m + y^m \equiv z^m \pmod{p}$ имеет решение в ненулевых вычетах по модулю $p$ . (Доказать эту теорему вы сможете после решения двух следующих задач.)

?

Задача 4.2.5

Сравнение $x^m + y^m \equiv z^m \pmod{p}$ имеет решение в ненулевых вычетах по модулю $p$ для

?

(1)

$m = 2$ , $p = 89$ ;

(2)

$m = 3$ , $p = 89$ ;

(3)

$m = 4$ , $p = 83$ ;

(4)

$m = 3$ , $p = 97$ ;

(5)

$m = 9$ , $p = 97$ .

Задача 4.2.6

Теорема Шура. Для любой раскраски натурального ряда в конечное число цветов найдётся одноцветное решение уравнения $x + y = z$ .

Более точно, для любого целого $k > 0$ существует такое целое $r > 0$ , что для любой раскраски первых $r$ натуральных чисел в $k$ цветов найдётся одноцветное решение уравнения $x + y = z$ .

?

Задача 4.2.7

(1)(2)

Найдите нижние оценки на $R(\underbrace{n, \ldots , n}_{k})$ , аналогичные утверждениям

?

(1)

4.1.5(1);

(2)

4.1.5(2).

Многоцветные числа Рамсея