На клетчатой бумаге нарисовали квадрат стороной 20 клеток. На клетчатой бумаге нарисовали квадрат со стороной 20 клеток. Затем некоторые стороны клеток покрасили в красный цвет, причем никакие две красные стороны квадратов не имеют общих концов, а на правой и верхней сторонах квадрата красных отрезков нет. Докажите, что можно проложить путь из левой нижней точки в правую верхнюю, не проходя при этом по красным сторонам.
На клетчатой бумаге нарисовали квадрат стороной 20 клеток. На клетчатой бумаге нарисовали квадрат со стороной 20 клеток. Затем некоторые стороны клеток покрасили в красный цвет, причем никакие две красные стороны квадратов не имеют общих концов, а на правой и верхней сторонах квадрата красных отрезков нет. Докажите, что можно проложить путь из левой нижней точки в правую верхнюю, не проходя при этом по красным сторонам.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Предположим, что такой путь невозможен. Рассмотрим все возможные пути из левой нижней точки в правую верхнюю. Каждый такой путь пересекает красные стороны квадратов максимум один раз (иначе мы можем просто обойти их). Из-за того, что никакие две красные стороны не имеют общих концов, каждый из этих путей пересекает красные стороны не более одного раза.
Таким образом, из каждой клетки, составляющей путь из левой нижней точки в правую верхнюю, ровно один краец клетки пересекает красную сторону. Но так как на правой и верхней сторонах квадрата красных отрезков нет, то любой путь из левой нижней точки в правую верхнюю должен пересечь красную сторону хотя бы один раз, что противоречит условию. Следовательно, путь без прохождения по красным сторонам существует.