Параде – 1
Параде желе да посете сваку улицу на својој рути тачно једном. У ова два примера, први је успешна рута параде, а други није (једна улица је изостављена).
ИЗАЗОВ
За сваки распоред улица, пронађите руту параде која посећује сваку улицу тачно једном или одлучите да је то немогуће. За распореде улица које имају параду, који дозвољавају да параде почињу и завршавају се на истом месту? Можете ли пронаћи образац у својим резултатима?
белешке
ИЗАЗОВ
Кључна идеја је пратити где параде почињу и завршавају се, ако уопште постоје, за мапу улица. Неке параде могу почети и завршити се било где, а неке морају почети или завршити на веома одређеним локацијама.
Након разматрања многих примера, намеће се следеће запажање. Није важно да мала деца доказују ове ствари.
Резултат 1: Ако угао има непаран број улица које долазе до њега, парада мора тамо почети или се завршити.
Разлог за то је једноставан. Сваки пут када парада уђе и изађе из угла, то представља паран број улица које долазе до тог угла. Стога, углови са непарним бројем улица морају бити почетак или крај параде.
Резултат 2: Ако постоји више од два угла са непарним бројем улица које улазе у њих, онда ова мапа не може имати параду.
Резултат 3: Ако постоје тачно два угла са непарним бројем улица, онда свака парада мора почети на једном од њих, а завршити се на другом. Конкретно, немогуће је имати параду која почиње и завршава се на истом месту.
Резултат 4: Ако нема углова са непарним бројем улица, онда парада може почети било где, и мора почети и завршити се на истом месту.