Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/sbcombi.ps Дата изменения: Thu Apr 15 17:57:17 2004 Дата индексирования: Sat Dec 22 16:30:10 2007 Кодировка: koi8-r

Графы.
Составитель Мазин М. В.
Задача 1. В группе из нескольких человек некоторые люди знакомы друг с дру-
гом, а некоторые - нет. Каждый вечер один из них устраивает ужин для всех своих
знакомых и знакомит их друг с другом. После того как каждый человек устроил хотя
бы один ужин, оказалось, что какие-то два человека все еще не знакомы. Докажите,
что на следующем ужине им познакомиться тоже не удастся.
Задача 2. В государстве 2000 городов. Некоторые пары городов соединены до-
рогами так, что из любого города можно проехать в любой другой. Докажите, что
это государство можно разбить на несколько республик (возможно, всего на одну)
так, чтобы в каждой республике из любого города можно было единственным обра-
зом проехать в любой другой город этой республики, не выезжая за ее пределы. (В
каждой республике должно быть не менее двух городов.)
Задача 3. Докажите, что в любой компании, состоящей из четного числа людей,
найдутся два человека, у которых в этой компании четное число общих знакомых.
Задача 4. В Северной Балбесии 100 городов, некоторые из них соединены доро-
гами так, что из каждого города можно доехать до любого другого. При этом всего
в Северной Балбесии 1000 дорог. Правительство хочет закрыть некоторые дороги
(возможно, все) так, чтобы из каждого города выходило четное число оставшихся
дорог (возможно, ни одной). Сколькими способами оно может это сделать?
Комбинаторика (дополнительные задачи).
Задача 1. Прямоугольник разбит на доминошки (то есть прямоугольники 12).
Докажите, что его клетки можно раскрасить в два цвета так, чтобы любая доминош-
ка в этом разбиении содержала клетки разных цветов, но в любом другом разбиении
этого прямоугольника на доминошки нашлась бы доминошка, содержащая две клет-
ки одного цвета.
Задача 2. Вдоль улицы с односторонним движением расположенно n мест для
парковки автомобиля. На улицу въезжает последовательно n автомобилей (с номе-
рами от 1 до n в порядке возрастания). Каждый водитель едет к своему любимому
месту парковки и, если оно свободно, припарковывается; в противном случае он едет
дальше до первой свободного места и припарковывается там. Если же места дальше
заняты, он уезжает (насовсем). Последовательностью предпочтений назовем список
a 1 ; a 2 ; : : : ; a n любимых мест парковки соответственно первого, второго,: : : ; n го во-
дителя. Сколько существует последовательностей предпочтений, для которых все
водители сумеют припарковаться?