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

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

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

1.

Сколькими способами можно добраться из А в Б по дорогам, изображённым на рисунках (на всех дорогах введено одностороннее движение)?

а)

б)

в)

2.

а)

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

б)

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

3.

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

4.

Между планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля — Меркурий, Сатурн — Венера, Земля — Сатурн, Сатурн — Меркурий, Меркурий — Венера, Уран — Нептун, Юпитер — Марс, Марс — Уран и Нептун — Юпитер. Можно ли добраться с Земли до Марса?

5.

Группа островов соединена мостами так, что от каждого острова можно добраться до любого другого. Турист обошёл все острова, пройдя по каждому мосту ровно один раз. На острове Светлом он побывал трижды. Сколько мостов ведёт со Светлого, если турист а) не с него начал и не на нём закончил? б) с него начал, но не на нём закончил? в) с него начал и на нём закончил?

6.

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

7.

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

8.

а)

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

б)

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

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

9.

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

10.

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

11.

В стране 1000 городов. Докажите, что можно соединить некоторые из них авиалиниями так, что из двух городов будет вести ровно по одной авиалинии, из других двух — ровно по две, ещё из двух — ровно по три, ..., наконец, из оставшихся двух — ровно по 500 авиалиний. (Если А соединён авиалинией с Б, то Б соединён с А.)