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

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

Листок 8. Графы — 2.

1.

a)

На светсткий раут прибыла 1000 барсуков. Некоторые при встрече пожали друг другу руки. Могли ли ровно 123 из них совершить нечётное число рукопожатий?

b)

Могли ли все 1000 барсуков совершить по нечётному числу рукопожатий?

c)

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

2.

a)

В каждой клетке шахматной доски 8×8 сидел таракан. По команде каждый таракан перебежал на соседнюю по горизонтали или вертикали клетку (при этом несколько тараканов могли забежать на одну клетку). Могли ли после этого все клетки остаться занятыми?

b)

А если бы это происходило на доске 9×9?

3.

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены железной дорогой в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться на поезде из города 1 в город 9?

4.

a)

В стране Цифра каждый город соединён с каждым автодорогой. Сколько всего дорог в стране?

Ответ

Ответ.

9 × 8	= 36
2

b)

Сколько диагоналей имеет правильный 23-угольник?

Ответ

Ответ.

23 × 20	= 230
2

5.

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

Ответ Указание

Ответ. Нельзя.

Указание. Посчитайте количество точек пересечения.

6.

a)

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

Ответ

Ответ. Не может.

b)

А может ли в государстве, в котором из каждого города выходят 5 дорог, быть ровно 100 дорог?

Ответ

Ответ. Может.

c)

А может ли в государстве, в котором 100 городов из каждого города выходить 5 дорог?

Ответ

Ответ. Может.

7.

a)

Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

b)

Среди 17 человек любые два либо дружат, либо враждуют, либо незнакомы. Докажите, что среди них найдутся либо трое друзей, либо трое врагов, либо трое незнакомых.