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

Занятие 15.  ГРАФЫ

1.  

В деревне 9 домов. Известно, что у Петра соседи — Иван и Антон, Максим — сосед Ивану и Сергею, Виктор — Диме и Никите. По соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Димой, Сергей с Антоном, причём больше соседей в этой деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Пётр огородами пробраться к Никите за яблоками?
 

2.  

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

3.  

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

4.  

Пётр, пробираясь огородами до Никиты, сделал себе москитную сетку, в которой ровно 100 узелков, и любые два узелка соединены ниточкой. Сколько ниточек потратил Петр на это бесполезное занятие?
 

5.  

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

6.  

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

7.  

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

8.  

Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий, чётно.
 

9.  

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

Домашние задачи

10.  

Нарисуйте 4 вертикальных и 4 горизонтальных отрезка, каждый из которых пересекает три отрезка другого направления.
 

11.  

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

12.  

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

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

13.  

В графе каждая вершина покрашена в синий или зелёный цвет. При этом каждая синяя вершина связана с пятью синими и десятью зелёными, а каждая зелёная — с девятью синими и шестью зелёными. Каких вершин больше, синих или зелёных?
 

14.  

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



Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS