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

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

Знакомство с графами (30 ноября 2013 года)

1.

В деревне Игуменка 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор - Диме и Никите, а также по соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Димой, Сергей с Антоном и больше соседей в означенной деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Петр огородами пробраться к Никите за яблоками?

2.

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

3.

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

4.

На окружности расположены 8 точек. Можно ли так соединить эти точки отрезками, чтобы каждая была соединена ровно с четырьмя другими?

5.

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

6.

Капитан Врунгель побывал в стране Оз. По его рассказам, в этой стране много городов. При этом из Изумрудного города выходит только дорога из желтого кирпича, а из каждого другого города выходит ровно по три дороги. Может ли оказаться, что прославленный капитан говорит правду?

7.

В верхних углах доски 3 на 3 стоят черные кони, а в нижних - белые. Можно ли за несколько ходов поменять их местами? Если да, то сколько ходов для этого необходимо?

8.

В верхних углах доски 3 на 3 стоят черные кони, а в нижних - белые. Можно ли за несколько ходов разместить коней одного цвета в противоположных углах доски. Есла да, то сколько ходов для этого необходимо?