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

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

Занятие 21 (апрель 1994). Графы

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

Задача 2. Можно ли, сделав несколько ходов конями из исходного положения, изображенного на рисунке 1, расположить их так, как показано на рисунке 2

Задача 3. Блокнот с оберткой стоят 11 к. Сам блоконт на 10 к. дороже обертки. Сколько стоят блокнот и обертка в отдельности?

Задача 4.
а) В государстве 100 городов, а из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
б) Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 городов? А ровно 100 дорог?

Задача 5.
а) Докажите, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых человека.
б) Верно ли то же утверждение для любой компании из 5 человек?

Задача 6. На катетах АВ и ВС прямоугольного треугольника АВС построили квадраты АВPQ и ВСSR. Докажите, что длина диагонали АС равна сумме растояния от точки Q до прямой АС и расстояния от точки S до прямой АС.

Задача 7. В футбольном турнире участвуют К команд. Докажите, что в любой момент времени найдутся две команды, сыгравшие одинаковое число матчей.