Заочная олимпиада по комбинаторике ФПМИ МФТИ. 03.2018 1. В каждую клетку таблицы с несколькими строками и 100 столбцами поставили 0 или 1. Оказалось, что в любом столбце нулей больше, чем единиц. Обязательно ли найдутся три столбца таких, что число строк, в пересечениях которых с этими столбцами стоят только нули, больше числа строк, в пересечениях которых с этими столбцами стоят только единицы? 2. а) Докажите, что если степень каждой вершины графа равна d и диаметр графа равен 2, то число вершин в графе не превосходит d2 + 1. б) Докажите, что если указанная оценка достигается, то d + 1 не кратно пяти. 3. Пусть p > 2 � простое число. Докажите, что Zp \ {0} можно разбить на два равномощных множества A и B так, что для любого x 2 Zp \ {0} существует одинаковое количество решений уравнения x = a + b, a 2 A, b 2 B. 4. Даны целые числа n k r 1. Для разбиения множества [n] := {1, . . . , n} на r частей A1 , . . . , Ar обозначим через mk (A1 , A2 , . . . , Ar ) число k-элементных подмножеств [n], имеющих непустое пересечение с каждой из частей. Для какого разбиения [n] на r частей A1 , . . . , Ar достигается максимальное значение mk (A1 , A2 , . . . , Ar )? 5. Дано счетное множество событий, каждое имеет вероятность 0.1. Докажите, что существует пять событий таких, что они происходят одновременно с вероятностью больше 0.99 · 10 5 . 6. На плоскости отмечено n точек так, что никакие три не лежат на одной прямой, и некоторые из них соединили отрезками. Оказалось, что любой отрезок пересекает все остальные отрезки за исключением, возможно, одного. Какое наибольшее число отрезков могло быть проведено? 7. Найдите наибольшее cn такое, что для любых векторов v1 , v2 , . . . , vn+1 в Rn с суммой, равной нулевому вектору, существуют "1 = ±1, "2 = ±1, . . . , "n+1 = ±1 такие, что |"1 v1 + "2 v2 + · · · + "n+1 vn+1 |2 cn (|v1 |2 + · · · + |vn+1 |2 ). 8. Пусть множество K ✓ R2 таково, что K \ (a + K) = ? для некоторого вектора a. Докажите, что тогда два замкнутых круга диаметра |a| не могут поменяться местами при непрерывном движении их центров по K, при котором круги не будут иметь общую точку. 9. Для графа G назовем кликовым хроматическим числом графа (G) минимальное число цветов для такой покраски вершин G, что каждая максимальная по включению неодновершинная клика (полный подграф) содержит хотя бы два разных цвета. Рассмотрим граф G(n, r, s): его вершинами являются r-элементные подмножества n-элементного множества, ребра проведены между парами подмножеств с пересечением мощности ровно s. а) Докажите, что (G(n, r, 0)) = 2 при n > N (r) для некоторого N (r). б) Докажите, что lim (G(n, r, s)) = 1 для любого r > s > 0. n!1 10. Дан связный недвудольный k-регулярный граф на n вершинах. Матрица A(r) = (r) n (r) (aij )i,j=1 состоит из чисел, определяемых комбинаторно: aij � число путей длины r из вершины i в вершину j без возвратов, т.е. число путей i = x0 , x1 , . . . , xr = j, где xi 1 и xi для trA(r) 1  i  r � соседние вершины, при этом xi 1 6= xi+1 для 1  i  r 1. Найдите lim (k . 1)r r!1