Назад

Олимпиадная задача: три дома и три колодца без пересечений тропинок

Задача 130801 • Сложность: 3 • 8-9 класс
Задача

Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?

Решение

Пусть это удалось. Полученный плоский граф двудолен, поэтому согласно задаче 131110  E ≥ 2F,  то есть  F ≤ 4.  Подставив в формулу Эйлера (задача 130759), получим  2 = 6 – 9 + F ≤ 1.  Противоречие.

Ответ

Нельзя.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Войти Зарегистрироваться
Комментариев нет