Parady – 1
Parady chcą odwiedzić każdą ulicę na swojej trasie dokładnie raz. W tych dwóch przykładach pierwsza jest udaną trasą parady, a druga nie (jedna ulica jest pominięta).
WYZWANIE
Dla każdego układu ulic znajdź trasę parady, która przechodzi przez każdą ulicę dokładnie raz, albo uznaj, że jest to niemożliwe. W przypadku układów ulic z paradą, które z nich pozwalają na jej rozpoczęcie i zakończenie w tym samym miejscu? Czy dostrzegasz jakiś schemat w wynikach?
Komentarz
WYZWANIE
Kluczową ideą jest śledzenie, gdzie parady się zaczynają i kończą, o ile w ogóle istnieją na mapie ulicznej. Niektóre parady mogą zaczynać się i kończyć w dowolnym miejscu, a inne muszą zaczynać się lub kończyć w ściśle określonych lokalizacjach.
Po przeanalizowaniu wielu przykładów nasuwa się następująca obserwacja: małe dzieci nie muszą tego udowadniać.
Wynik 1: Jeżeli do rogu ulicy dochodzi nieparzysta liczba ulic, parada musi się tam rozpocząć lub zakończyć.
Powód jest prosty. Za każdym razem, gdy parada wjeżdża i wyjeżdża z narożnika, oznacza to, że do narożnika prowadzi parzysta liczba ulic. Dlatego narożniki z nieparzystą liczbą ulic muszą być początkiem lub końcem parady.
Wynik 2: Jeśli na więcej niż dwóch narożnikach znajduje się nieparzysta liczba ulic, to na tej mapie nie ma parady.
Wynik 3: Jeśli istnieją dokładnie dwa narożniki z nieparzystą liczbą ulic, to każda parada musi zaczynać się na jednym z nich i kończyć na drugim. W szczególności nie jest możliwe, aby parada zaczynała się i kończyła w tym samym miejscu.
Wynik 4: Jeżeli nie ma narożników z nieparzystą liczbą ulic, parada może rozpocząć się w dowolnym miejscu, a jej początek i koniec muszą znajdować się w tym samym miejscu.