Парады – 1
Организаторы парадов стремятся посетить каждую улицу на своем маршруте ровно один раз. В этих двух примерах первый маршрут парада оказался успешным, а второй — нет (одна улица пропущена).
CHALLENGE
Для каждой схемы улиц либо найдите маршрут парада, который проходит по каждой улице ровно один раз, либо решите, что это невозможно. Для схем улиц, где предусмотрен парад, какие из них позволяют парадам начинаться и заканчиваться в одном и том же месте? Можете ли вы обнаружить закономерность в своих результатах?
Заметки
CHALLENGE
Главная идея заключается в том, чтобы отслеживать места начала и окончания парадов, если таковые вообще существуют, для карты улиц. Некоторые парады могут начинаться и заканчиваться где угодно, а некоторые должны начинаться или заканчиваться в строго определенных местах.
После рассмотрения множества примеров можно сделать следующий вывод: маленьким детям не нужно доказывать подобные вещи.
Результат 1: Если к углу подходит нечетное количество улиц, парад должен начинаться или заканчиваться там.
Причина проста. Каждый раз, когда парад проходит через угол улицы и возвращается обратно, это означает, что к этому углу подходит четное количество улиц. Следовательно, углы с нечетным числом улиц должны быть началом или концом парада.
Результат 2: Если на карте имеется более двух угловых участков, к которым подходит нечетное количество улиц, то на этой карте парад невозможен.
Результат 3: Если есть ровно два угла с нечетным числом улиц, то любой парад должен начинаться на одном из них и заканчиваться на другом. В частности, невозможно, чтобы парад начинался и заканчивался в одном и том же месте.
Результат 4: Если нет перекрестков с нечетным числом улиц, то парад может начаться где угодно и должен начинаться и заканчиваться в одном и том же месте.