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

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

Занятие 13 (10 декабря 2011 года). Графы-2

1.

Хоровод водят а) шесть; б) восемь; в) десять ребят. Те, кто держатся за руки — друзья, кроме того, друзья те, кто стоят напротив. Одного из ребят мама позвала обедать, и он ушёл. Смогут ли остальные встать в хоровод так, чтобы каждые двое, стоящие рядом, были друзьями?

2.

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

3.

В Тридевятом царстве лишь один вид транспорта — ковёр-самолет. Из столицы выходит 21 ковролиния, из города Дальний одна, а из всех остальных городов по 20. Докажите, что из столицы можно долететь до Дальнего (возможно, с пересадками).

4.

Доска — квадрат 4×4 без угловых клеток. Сможет ли шахматный конь обойти все клетки этой доски, побывав на каждой по одному разу?

* * *

5.

Известно, что в компании из семи человек любые шестеро могут встать в круг так, что стоящие рядом — друзья. Верно ли, что и все семеро смогут так встать в круг?

6.

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

7.

В городе есть дороги трёх типов: однополосные, двухполосные и трехполосные. На каждом перекрёстке в городе сходятся три дороги, причём разных типов. Иными словами, каждый перекрёсток есть разделение трёхполосной дороги на двухполосную и однополосную. Тупиков в городе нет. Три городских дороги выходят за пределы города и превращаются в шоссе. Докажите, что из города выходит ровно по одному шоссе каждого типа.

8.

Имеются две страны: Обычная и Зазеркалье. У каждого города в Обычной стране есть «двойник» в Зазеркалье, и наоборот. Однако если в Обычной стране какие-то два города соединены железной дорогой, то в Зазеркалье эти города не соединены, а любые два несоединённых в Обычной стране города обязательно соединены железной дорогой в Зазеркалье. В Обычной стране девочка Алиса не может проехать из города А в город Б, сделав менее двух пересадок. Докажите, что в Зазеркалье Алиса сможет проехать из любого города в любой другой, сделав не более двух пересадок.

* * *

9.

Каждая клетка квадратной таблицы покрашена в некоторых цвет, причём любые две строчки раскрашены по-разному. Докажите, что можно убрать один столбец так, что в оставшейся таблице все строки по-прежнему будут различны.

10.

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