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

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

Листок 3. Всё путём!

1.

a)

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

b)

Сколько диагоналей в 1024-угольнике?

2.

В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей?

3.

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

4.

Двоечник Вася приехал из Диснейленда и рассказал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Отличница Настя сразу сказала: «Хотя бы один из этих мостов выходит на берег озера!» Как она догадалась?

5.

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

6.

a)

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

b)

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

7.

В каждой строчке и каждом столбце доски 8×8 стоит по две фишки. Докажите, что их можно раскрасить a) в два цвета, b) в 5 цветов так, чтобы в каждом столбце и в каждой строке все фишки были разных цветов.

8.

a)

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

b)

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

9.

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