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

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

Занятие 4 (17 октября 2015 года). Его сиятельство Граф

1.

Задача Эйлера о кёнигсбергских мостах. Город Кёнигсберг (ныне Калининград) был расположен на берегах реки Прегель (Преголя) и двух островах, которые соединены семью мостами (на рисунке). Можно ли было прогуляться по городу, пройдя по каждому мосту ровно один раз?

2.

а)

Нарисуйте картинки одним росчерком карандаша, не проводя одной линии дважды:

б)

А можно ли так нарисовать вот эту картинку:

3.

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

4.

а)

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

б)

Верно ли это утверждение для пяти человек?

5.

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

6.

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

7.

На рисунке изображён схематический план города: кружочки обозначают площади, а прямые линии — улицы. Отрезки улиц между соседними площадями имеют равную длину. Турист выходит из гостиницы, расположенной на одной из площадей, и хочет обойти город, пройдя хотя бы один раз по каждой из улиц, и вернуться в гостиницу. Как туристу совершить такой обход, чтобы его маршрут имел наименьшую длину?

а)

б)

8.

У каждого из королевских советников ровно один другой советник — друг, и ровно один — враг. Король хочет сформировать из своих советников Сенат, составленный из двух палат одинаковой численности (каждый советник должен попасть ровно в одну из палат). При этом король знает, что, попав в одну палату, два советника-друга непременно организуют заговор против короля, а два советника-врага поссорятся окончательно и начнут гражданскую войну в стране. Сможет ли король сформировать Сенат без угрозы своей собственной и государственной безопасности?

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

9.

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

10.

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

11.

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

а)

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

б)

Покажите, что число людей на собрании может быть больше 4.