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

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

Графы и обходы графов (10.11 и 12.11)

1.

а) Расположите на плоскости 6 точек и соедините их непересекающимися линиями так, чтобы из каждой точки выходили 4 линии.

б) проведите 6 прямых и отметьте на них 7 точек так, чтобы на каждой прямой было ровно три из отмеченных точек.

2.

а) Художник-авангардист нарисовал картину “Контур квадрата и его диагональ”. Мог ли он нарисовать свою картину, не отрывая карандаша от бумаги и не проводя никакую линию дважды?

б) А если его картина называлась “Контур квадрата и его диагонали”?

3.

а) Зачеркните 9 точек, изображенных на левом рисунке, четырьмя отрезками, не отрывая карандаша от бумаги и не проводя никакую линию дважды.

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

4.

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

5.

а) 20 команд сыграли турнир по олимпийской системе (встречаются две команды, победитель играет дальше, проигравший выбывает). Сколько всего было сыграно матчей?

б) а если турнир проходил по круговой системе в один круг? (каждая команда играет с каждой один раз).

6.

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

Дополнительные задачи

7.

В углах шахматной доски 3*3 стоят 4 коня: 2 белых и 2 черных. Можно ли за несколько ходов поставить коней так, чтобы во всех соседних углах стояли кони разного цвета.

8.

Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы - квадраты со стороной b, всего 9 кварталов). Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке A? (Стороны квадрата - тоже улицы).

9.

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