Олимпиадные задачи по математике по теме "Понятие графа".

Задача 1:

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

Решение: 
Нарисуем схему: планетами будут соответствовать точки, а соединяющим их маршрутам – непересекающиеся между собой линии. Теперь видно, что долететь от Зем-ли до Марса нельзя.



Задача 3:

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

Решение: 
Да, такой обход возможен.



Задача 4:

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

Решение: 
Нет, нельзя. Рассмотрите остатки получающихся двузначных чисел при делении на 9

 

Написать комментарий

*  

Защитный код
Обновить
→