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

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

Руководители Сергей Александрович Дориченко и Степан Львович Кузнецов
2007/2008 учебный год

Листок 6

1.
Какие из следующих фигур можно нарисовать, не отрывая карандаша от бумаги и не проводя ни одной линии дважды?
а) ; б) .
2.
Архипелаг состоит из 100 островов, некоторые из которых соединены мостами. Известно, что с каждого острова на другие ведёт чётное число мостов и что с любого острова можно добраться на любой (возможно, через другие острова). Докажите, что можно обойти архипелаг, побывав на каждом мосту ровно по одному разу.
3.
В доску вбиты гвоздики, рядом с которыми написаны цифры. Можно ли соединить гвоздики шнурками так, чтобы цифра, написанная около гвоздика, равнялась числу шнурков, за него завязанных?
а) ; б) .
4.
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей?
5.
Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий, чётно.
6.
Жук ползёт по ребрам куба. Сможет ли он последовательно обойти все ребра, проходя по каждому ребру ровно один раз?
7.
Докажите, что из куска проволоки длиной 120 см нельзя сделать каркас куба со стороной 10 см, если проволоку можно только изгибать (ломать нельзя).
8.
Верно ли, что среди а) пяти, б) шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых?
9.
В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы, выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?
10.
В стране Цифра есть девять городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если сумма цифр-названий этих городов делится на три. Можно ли добраться из города 1 в город 7 (возможно, с пересадками)? А из города 1 в город 9 (возможно, с пересадками)?