МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 6 (22 октября 2011 года). Графы

1.

Можно ли, сделав несколько ходов конями из положения на рисунке слева, расположить их так, как показано на рисунке справа? (Выходить за пределы поля 3×3 не разрешается.)

2.

В стране 2011 городов, из каждого выходит по 4 дороги. Сколько всего дорог в стране?

3.

В классе 20 человек. Из них все, кроме Пети дружат ровно с 5 одноклассниками. Может ли Петя ни с кем не дружить?

4.

Может ли в стране, где из каждого города выходит по три дороги и нет развилок и тупиков, быть ровно 100 дорог?

5.

Иван утверждает, что среди любых а) четырёх; б) пяти; в) шести человек обязательно найдётся либо трое знакомых друг с другом, либо трое незнакомых. Не завирается ли он?

* * *

6.

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

7.

В шахматном турнире, в котором каждый участник должен был встретиться с каждым, один шахматист заболел и не доиграл свои партии. Всего в турнире было проведено 24 встречи. Сколько шахматистов участвовало в турнире, и сколько партий сыграл выбывший участник?

8.

В некотором государстве система авиалиний устроена так, что любой город соединён авиалиниями не более чем с тремя другими, и из любого города в любой другой можно перелететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в этом государстве?

9.

В стране любые два города соединены либо железной дорогой, либо авиалинией. Докажите, что можно закрыть какой-то один вид транспорта так, чтобы из любого города можно было проехать в любой другой (возможно, с пересадками).