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

Кружок 9-11 классов

Графы

1.

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

2.

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

3.

Можно ли 77 телефонов соединить между собой проводами так, чтобы каждый был соединён ровно с пятнадцатью другими?

4.

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

5.

У короля 15 баронов-вассалов. Могло ли так оказаться, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

6.

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

7.

Пешеход обошёл все улицы одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь один раз. Могло ли такое быть?

8.

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

9.

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

10.

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

11.

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