Олимпиадные задачи по математике

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

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

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

3 . Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается .)

Ответ:нельзя

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

• Ответ.  Нет.

Решение.

Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компоненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.

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

• Ответ.  200.
• Решение.  Обойдем по очереди все города, считая дороги, входящие из них. Всего таким способом мы насчитаем 400 дорог. Но каждая дорога выходит из двух городов, значит, каждую дорогу мы посчитали два раза. Поэтому на самом деле дорог в государстве в два раза меньше, чем мы насчитали, то есть 200.

• Теорема 1. Количество ребер в любом графе равно половине суммы степеней его вершин .

6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? Подсказка:  попытайтесь посчитать количество телефонных проводов

Ответ.  Нет.

Решение.  В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. Применим к этому графу теорему 1. Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75. Это нечетное число, поэтому его половина — число нецелое. То есть в нашем графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может.

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

Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.

Ответ.  Нет.

Решение.  Сделаем учеников вершинами графа, а ребрами будем соединять тех из них, которые дружат между собой. По условию в таком графе четных вершин будет 11, а нечетных 9+10=19, то есть нечетное число, что противоречит теореме 2.