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

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

Занятие 17 (11 марта 2017 года). Жмём руки и считаем

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

1.

Во дворе растут 10 берёз и стоят 6 фонарных столбов. Между ними натянуты бельевые верёвки так, что к каждому столбу привязано 7 верёвок, а к каждой берёзе — 5. Сколько во дворе бельевых верёвок?

2.

а)

Кот Васька поймал 6 марсианских мышек (у марсианских мышек по три хвоста) и связал их хвостами так, что свободных хвостов не осталось. Сколько узелков ему пришлось завязать?

б)

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

3.

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

4.

В некотором государстве 6 городов и 10 автодорог, каждая из которых связывает какие-то два города. Авиационное сообщение между двумя городами устанавливается тогда и только тогда, когда автомобильная дорога между этими городами отсутствует. Сколько авиалиний для этого нужно?

5.

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

6.

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

7.

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

8.

В стране 2017 городов и сёл. Из столицы выходит 25 дорог, из села Енотова выходит всего одна дорога, а из всех остальных населенных пунктов — по 20 дорог. Енот хочет добраться от Енотова до столицы по дорогам. Справится ли енот?

9.

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

10.

В стране 55 городов, и каждый соединён с каждым дорогой (напрямую). Можно ли все дороги на карте страны раскрасить в 54 цвета таким образом, чтобы все дороги, выходящие из одного города, были разного цвета?

11.

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