5. Zadatak

Prvo rješenje.

Nazovimo jedan raspored boja po ulicama bojenje, a jedan odabir trga i promjenu boja svih ulica koje vode do njega nazovimo transformacija.

Uočimo da ako od jednog bojenja možemo nizom transformacija doći do nekog drugog bojenja, tada istim nizom transformacija možemo doći i od drugog bojenja do prvog. Prema tome, početna tvrdnja ekvivalentna je tvrdnji da, krenemo li od bojenja u kojem su sve ulice iste boje, postoji bojenje do kojeg ne možemo doći niti jednim nizom transformacija.

U svakom nizu transformacija možemo smatrati da se svaki trg pojavljuje nijednom ili jednom. Naime, paran broj transformacija na jednom trgu ima isti rezultat kao da na tom trgu nije niti jednom izvršena transformacija, a svaki neparan broj transformacija na istom trgu ima isti rezultat kao da je transformacija izvršena točno jednom.

Uočimo nadalje da u nizu transformacija kojima iz jednog bojenja dolazimo do drugog redoslijed transformacija nije bitan, odnosno da je važno samo odrediti skup trgova koji su uključeni u te transformacije. Broj različitih skupova trgova iznosi $2^N$ jer za svaki od $N$ trgova možemo odabrati je li uključen u taj skup ili nije.

Primijetimo da skup u kojem smo uključili sve trgove vodi do bojenja koje je jednako početnom jer smo time svakoj ulici promijenili boju točno dvaput. Isti rezultat očito daje i skup trgova u kojem nismo uključili niti jedan trg. Budući da dva skupa daju isto bojenje, broj različitih bojenja do kojih možemo doći iz nekog početnog bojenja nije veći od $2^N-1$.

Imamo dva moguća početna bojenja (svi bridovi su crveni, odnosno svi bridovi su plavi), pa ukupan broj bojenja do kojih možemo doći iz jednog od ta dva bojenja nije veći od

$$2(2^N-1)=2^{N+1}-2.$$

Budući da ima $M$ ulica, a za svaku ulicu imamo dvije moguće boje, ukupan broj mogućih bojenja je $2^M$. Zbog $M>N$ slijedi

$$2^M\ge2^{N+1}>2^{N+1}-2,$$

pa zaključujemo da postoji bojenje do kojeg nije moguće doći iz početnih jednobojnih bojenja. Time je dokaz završen.

Napomena. U rješenju smo koristili da broj različitih bojenja do kojih možemo doći iz nekog početnog bojenja nije veći od $2^N-1$, no vrijedi jača ograda – taj broj nije veći od $2^{N-1}$. Naime, za bilo koji skup transformacija postoji komplementaran skup transformacija (u jednom skupu su točno one transformacije koje nisu u drugom i obratno). Dakle, svih $2^N$ skupova transformacija možemo podijeliti u komplementarne parove koji rezultiraju istim bojenjem, iz čega slijedi jača ograda za broj mogućih bojenja.

Drugo rješenje.

Rješenje zapisujemo koristeći jezik teorije grafova. Grad reprezentiramo grafom u kojem vrhovi predstavljaju trgove, te su dva vrha povezana bridom ako i samo ako postoji ulica koja spaja pripadna dva trga.

Uočimo da je dovoljno pokazati da postoji neki podskup skupa svih bridova u kojem je bridove moguće obojiti tako da se nikad u budućnosti ne može dogoditi da svi bridovi budu iste boje.

Ciklus duljine $n$ je niz različitih vrhova i bridova

$$T_0,u_1,T_1,\ldots,u_n,T_n=T_0$$

takvih da za svaki $j=0,\ldots,n-1$ vrhove $T_j$ i $T_{j+1}$ povezuje brid $u_j$.

Tvrdimo da se u ciklusu parnost broja crvenih (odnosno plavih) bridova ne mijenja. Zaista, ako primijenimo dozvoljenu transformaciju na vrh $T_j$, unutar ciklusa će boju promijeniti dvije ulice $u_j$ i $u_{j+1}$. Ako su obje ulice bile iste boje, onda se broj crvenih bridova promijenio za dva, a ako su te ulice različitih boja, onda se broj crvenih bridova ne mijenja.

Ako u grafu postoji ciklus parne duljine, onda jedan brid možemo obojiti plavo, a sve ostale crveno. Tako obojeni bridovi nikad neće imati istu boju jer ćemo uvijek imati neparan broj plavih bridova u tom ciklusu.

Pretpostavimo zato da u grafu nema ciklusa parne duljine. Poznato je (i može se jednostavno dokazati matematičkom indukcijom) da graf koji nema ciklus ima broj bridova manji od broja vrhova. Također, broj bridova u grafu koji ima točno jedan ciklus može najviše biti jednak broju vrhova (jer uklanjanjem jednog brida u ciklusu dobivamo graf bez ciklusa). Budući da je $M\ge N+1$, slijedi da graf mora imati barem dva ciklusa.

Odaberimo bilo koja dva ciklusa u promatranom grafu. Prema pretpostavci oba imaju neparnu duljinu, te nemaju zajedničkih bridova (u suprotnom bi njihova unija bez zajedničkog brida bila ciklus parne duljine). Obojimo točno jedan brid u jednom ciklusu plavo, a sve druge bridove u oba ciklusa crveno. Zbog parnosti broja crvenih bridova vidimo da ciklus koji ima jedan plavi brid nikad neće imati sve bridove crvene, dok ciklus koji ima sve bridove crvene nikad neće imati sve bridove plave. Dakle, uz opisano bojenje nikad u budućnosti se ne može dogoditi da svi bridovi (u ta dva ciklusa, pa tako i u čitavom grafu) budu iste boje.

Napomena. U zadatku nije važno dozvoljavamo li da dva trga budu spojena s više od jedne ulice. Naime, ako postoji takav par trgova, onda građani mogu jednu od ulica koje ih spajaju obojiti crveno, a drugu plavo. Dakle, u tom slučaju je tvrdnja trivijalna i preostaje pokazati tvrdnju zadatka pod pretpostavkom da je između svaka dva trga najviše jedna ulica.

Također nije važno da između svaka dva trga postoji niz ulica kojima možemo proći kako bismo došli od jednog trga do drugog. Naime, ako u gradu postoji više nepovezanih dijelova, onda za jedan od tih dijelova mora vrijediti da je broj ulica veći od broja trgova i dalje možemo argumentirati na isti način kao da je taj dio čitavi grad.