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

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

Занятие 9. Графы

1.

Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6×6 из чисел: +1, −1 и 0 так, чтобы все суммы по строкам, столбцам и большим диагоналям были различны. Узнает ли Буратино великую тайну?

2.

Может ли у многоугольника быть ровно 10 диагоналей?

3.

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

4.

Как известно, у марсиан по 3 руки. Могут ли 2009 марсиан взяться за руки, чтобы не осталось свободных рук? (В каждом рукопожатии участвуют ровно две руки.)

5.

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

6.

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

7.

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

8.

Жук ползёт по рёбрам а) тетраэдра (на рисунке слева), б) куба, в) октаэдра (на рисунке справа). Сможет ли он последовательно обойти все рёбра, проходя по каждому ребру ровно один раз?

9.

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

10.

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

11.

В противоположных концах клетчатой полоски 1×100 стоит по фишке. Двое играют в следующую игру. За один ход можно сдвинуть одну из фишек на 1, 2, 3 или 4 клетки в сторону второй фишки. Проигрывает тот, кто не может сделать хода. Кто выиграет при правильной игре?

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

12.

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

13.

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

14.

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

15.

В Тридевятом царстве из столицы выходит 100 дорог, а из остальных городов — по 10, и от любого города можно добраться до любого другого. Докажите, что можно закрыть 50 выходящих из столицы дорог так, чтобы из любого города можно было по-прежнему добраться до любого другого.