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

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

Бонусные задачи 1.

1.

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

2.

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

3.

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

4.

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

5.

В стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

6.

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

7.

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

8.

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

9.

Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и черных пятиугольников. Каждый черный лоскут граничит только с белыми, а каждый белый — с тремя белыми и тремя черными. Сколько лоскутов белого цвета?

10.

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

а)

198 перелетов;

б)

196 перелетов.

11.

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

12.

Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды A, B и C такие, что A выиграла у B, B выиграла у C, а C выиграла у A.