Задача 103781

Тема:    [ Обход графов ]

Сложность: 2 Классы: 6,7

Условие

Автор: Ботин Д.А.

Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть?

Решение

Рассмотрим шесть улиц, выходящих из центра города в разных направлениях (то есть шесть отрезков с общим началом и без других общих точек). Пешеход может, выйдя из центра, пройти каждую улицу туда-обратно. Но, очевидно, пройти по каждой улице ровно один раз невозможно.

Ответ

Могло.

Источники и прецеденты использования

олимпиада
Название	Математический праздник
год
Год	1994
класс
	1
Класс	6
задача
Номер	8