ГРУППА ВЕСНЫ ТЕОРИЯ РАМСЕЯ Среди любых шести человек найдется либо трое попарно знакомых, либо трое попарно незнакомых.

ГРУППА ВЕСНЫ ТЕОРИЯ РАМСЕЯ
Среди любых шести человек найдется либо трое попарно знакомых, либо трое попарно незнакомых.
Среди любых десяти человек найдется либо четверо попарно знакомых, либо трое попарно незнакомых.
Среди любых девяти человек найдется либо четверо попарно знакомых, либо трое попарно незнакомых.
Среди любых 20 человек найдется либо 4 попарно знакомых, либо 4 попарно незнакомых.

Обозначим через r(m,n) минимальное число, что среди любых r(m,n) человек найдется либо m попарно знакомых, либо n попарно незнакомых.

Докажите, что r(m,n)
· r(m-1,n)+ r(m,n-1).
Докажите, что r(m,n)
· C
На плоскости отметили 17 точек и соединили каждые 2 из них цветным отрезком: красным, желтым или зеленым. Докажите, что найдутся 3 точки в вершинах одноцветного треугольника.

Обозначим через r(m1, ...,mk) минимальное число, что если полный граф с r(m1, ...,mk) раскрашен в k цветов, то для некоторого i найдется mi вершин, попарно соединенных ребрами цвета i.

Докажите, что r(m1, m2,...,mk)
· r(m1-1, m2,...,mk)+ r(m1, m2-1,...,mk)+...+ r(m1, m2,...,mk-1).
Найдите оценку на r(m1, m2,...,mk), аналогично задаче 6.





ГРУППА ВЕСНЫ ТЕОРИЯ РАМСЕЯ
Среди любых шести человек найдется либо трое попарно знакомых, либо трое попарно незнакомых.
Среди любых десяти человек найдется либо четверо попарно знакомых, либо трое попарно незнакомых.
Среди любых девяти человек найдется либо четверо попарно знакомых, либо трое попарно незнакомых.
Среди любых 20 человек найдется либо 4 попарно знакомых, либо 4 попарно незнакомых.

Обозначим через r(m,n) минимальное число, что среди любых r(m,n) человек найдется либо m попарно знакомых, либо n попарно незнакомых.

Докажите, что r(m,n)
· r(m-1,n)+ r(m,n-1).
Докажите, что r(m,n)
· C
На плоскости отметили 17 точек и соединили каждые 2 из них цветным отрезком: красным, желтым или зеленым. Докажите, что найдутся 3 точки в вершинах одноцветного треугольника.

Обозначим через r(m1, ...,mk) минимальное число, что если полный граф с r(m1, ...,mk) раскрашен в k цветов, то для некоторого i найдется mi вершин, попарно соединенных ребрами цвета i.

Докажите, что r(m1, m2,...,mk)
· r(m1-1, m2,...,mk)+ r(m1, m2-1,...,mk)+...+ r(m1, m2,...,mk-1).
Найдите оценку на r(m1, m2,...,mk), аналогично задаче 6.

15

Приложенные файлы

  • doc 3210527
    Размер файла: 28 kB Загрузок: 0

Добавить комментарий