Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/sbory05/ocensnur.ps Дата изменения: Tue Apr 12 16:04:03 2005 Дата индексирования: Sun Dec 23 00:23:13 2007 Кодировка: Windows-1251 Поисковые слова: звездная пыль

Подсчеты в графах . Группа Y . 06 апреля 2005г.
1) Комиссия собиралась 40 раз. На каждом заседании было ровно 10 человек, любые два не
были вместе больше 1 раза. Докажите, что в комиссии хотя бы 60 человек.
2) 100 государств объединены в блоки, в каждом не больше 50 государств, любые два государства
состоят вместе хотя бы в одном блоке. Каково минимальное возможное число блоков?
3) В стране каждый город соедин?н дорогами не более, чем с 3 другими и из любого города
можно добраться по дорогам до любого, сделав не более одной пересадки. Для какого максимального
числа городов это возможно?
4) В компании у любых 2 знакомых друг с другом человек ровно 5 общих знакомых. Докажите,
что количество знакомств в этой компании делится на 3.
5) n > k  фиксированные натуральные числа. S  множество из n точек на плоскости, такое,
что любое три точки из S не на одной прямой и для любой точки P 2 S существует хотя бы k
различных точек из S равноудаленных от P . Докажите, что k < 1
2 +
p
2n.
6) Пусть Pn (k) - число перестановок множества из n элементов, имеющих ровно k неподвижных
точек (т.е. ровно k элементов остались на своих местах). Докажите, что
n
P
k=0
k
Pn (k) = n!
7)Дан правильный 2005 - угольник.Ровно m его вершин покрашено в белый цвет, а остальные
вершины покрашены в черный. Рассматриваются одноцветные равнобедренные треугольники с
вершинами в вершинах 2005 - угольника.( либо все 3 вершины белые, либо все 3 черные). Доказать,
что число таких равнобедренных одноцветных треугольников не зависит от способа раскраски.
8) В системе p уравнений с q = 2p неизвестными
8
> > > <
> > > :
a 11 x 1 + a 12 x 2 + : : : + a 1q x q = 0
a 21 x 1 + a 22 x 2 + : : : + a 2q x q = 0
. . .
. . .
. . .
a p1 x 1 + a p2 x 2 + : : : + a pq x q = 0
коэффициенты a ij 2 f1; 0; 1g Докажите, что существует решение (x 1 ; x 2 ; : : : ; x q ) этой системы
такое, что: все x j целые; для некоторого j(1 6 j 6 q) x j <> 0; для всех j(1 6 j 6 q) выполнено
неравенство jx j j 6 q.
1

Оценки в графах. Группа Z. 06.04.05
1) Дано поле 2n + 1  2n + 1 клеток. Двое по очереди ставят фишки: первый может поставить
фишку в клетку (x; y), если в столбце с номером x и строке с номером y до его хода поставлено в
сумме ч?тное число фишек, второй  если неч?тное. В каждую клетку можно поставить не более 1
фишки. Проигрывает тот, кто не может сделать ход. Докажите, что один из игроков выигрывает,
как бы он сам не играл.
2) Дан правильный треугольник со стороной 10. Каждую сторону разбили на 10 равных частей,
провели через точки разбиения прямые параллельные сторонам основного треугольника и тем
самым разбили основной треугольник на 100 единичных правильных треугольников . Цепочкой
назов?м последовательность единичных треугольников такую, что ни один треугольник не повторяется
дважды и каждый последующий имеет общую сторону с предыдущим. Какое наибольшее число
треугольников может быть в цепочке?
3) В связном графе n вершин, степень каждой не превосходит 3, количество р?бер не меньше
5
4 n. Докажите, что существует не висячая вершина такая, что после е? удаления граф оста?тся
связным.
4) В обществе из представителей 6 стран 2005 человек, пронумерованных числами от 1 до 2005.
Докажите, что в одной стране существуют люди с номерами a, b и c такие что a = b + c или с
номерами a и b такие, что a = 2b.
5) Даны рациональные числа x 1 ; x 2 ; : : : ; xn , такие, что x 2
1 + x 2
2 + : : : + x 2
n = 1. Докажите, что
для любого целого k > 2 существуют целые числа a 1 ; a 2 ; : : : ; an , не все равные 0 такие, что ja i j 6
k 1; i = 1; 2; : : : ; n и ja 1 x 1 + a 2 x 2 + : : : + anxn j 6 k
p
n
k n 1 .
6) В стране 25 городов. Из каждого города выходят не более 23 дорог, и между двумя городами
существует путь, проходящий не более чем по 2 дорогам.
а) Докажите, что дорог хотя бы 38.
б) Найдите минимально возможное число дорог.
7) В связном графе 1000 вершин, из каждой выходит не более 9 дорог. Докажите, что можно
выбрать 220 вершин так, чтобы между ними не было цикла неч?тной длины.
8) Дано семейство из 2m-элементных множеств и для любого мегамножества из (m+1) 2 элементов
множеств все множества, полностью содержащиеся в этом мегамножестве, имеют общий элемент.
Доказать: у всех множеств есть общий элемент.
9)
а) Докажите, что для любого n существует натуральное число g(n) такое, что полный турнир
с g(n) участниками содержит транзитивный (т.е. такой, что если A выиграл у B и B выиграл у C,
то A выиграл у C) подтурнир с n участниками.
б) Докажите, что существует такое >1, что  n < g(n) < 2 n .
2