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

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

Тема 7.1. Графы

1.

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

2.

Можно ли расположить в пространстве 5 шаров, чтобы каждый касался ровно трёх других?

3.

Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий, чётно.

4.

Рис. 3

Можно ли нарисовать квадрат с диагоналями (рис. 3), не отрывая карандаша от бумаги и не проводя линий дважды?

5.

На рис. 4 изображена схема мостов Кёнигсберга (ныне Калининград) времён Л. Эйлера. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?

Рис. 4

6.

В центре куба 3×3×3 сидит жук. Сможет ли он, переползая через ребра, обойти все кубики 1×1×1 по одному разу?

7.

Дан кусок проволоки длиной 120 см. На какое наименьшее число частей его нужно разломить, чтобы изготовить каркас куба с ребром 10 см?

8.

Верно ли, что среди любых а) пяти, б) шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых?

9.

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

10.

У царя Гороха было 3 сына. У 50 его потомков было по 4 сына (и ни одной дочери), а прочие умерли бездетными. Сколько всего потомков было у царя Гороха?

11.

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

12.

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