5. Zadatak

Prvo rješenje.

Postoji sedam uzastopnih trojki žarulja. Zamislimo da sa sedam prekidača mijenjamo stanje po tri uzastopne žarulje. Prvo, uočimo da za dobivanje određenog rasporeda nije bitno kojim redoslijedom pritišćemo prekidače, već samo koliko puta smo promijenili stanje pojedine žarulje. Nadalje, uočimo da svaki prekidač treba pritisnuti jednom ili ne pritisnuti - pritisnemo li ga paran broj puta, isti je učinak kao da nismo pritisnuli niti jednom, a pritisnemo li ga neparan broj puta, isti je učinak kao da smo ga pritisnuli jednom.

a) Konačno stanje prve žarulje ovisi isključivo o tome hoćemo li prvi prekidač pritisnuti. Kako bi prva žarulja bila upaljena, moramo ga pritisnuti. Tada su upaljene prva, druga i treća žarulja. Konačno stanje druge žarulje, nakon što smo fiksirali stanje prve žarulje, ovisi isključivo o tome hoćemo li drugi prekidač pritisnuti. Pritisnut ćemo ga da žarulju ugasimo i time dobivamo da su upaljene prva i četvrta žarulja. Nastavljamo postupak na isti način; treći prekidač pritisnemo, četvrti ne, peti ne, šesti ne, sedmi da. Time smo dobili da je prvih sedam žarulja naizmjenično upaljeno i ugašeno i to je jedini način na koji smo do takvog rasporeda mogli doći. No, tada je osma žarulja upaljena pa ne možemo postići da sve žarulje budu naizmjenično upaljene i ugašene na traženi način.

b) Sve mogućnosti dobivamo odabirom nekog broja prekidača koje ćemo pritisnuti. Kako imamo dvije mogućnosti za svaki od $7$ prekidača (konačno stanje mogu biti i sve ugašene žarulje, što odgovara tome da niti jedan prekidač nismo pritisnuli), imamo $2^7=128$ mogućih odabira pritisnutih prekidača.

Uočimo da svaka dva različita odabira pritisnutih prekidača daju različit raspored stanja svih devet žarulja. Zaista, za dva različita odabira možemo promotriti prvi prekidač u nizu koji se pojavljuje u jednom od tih odabira, ali ne i u drugom. Tada će u pripadnim rasporedima prva žarulja kojoj taj prekidač mijenja stanje imati različita stanja.

Stoga postoji $128$ različitih mogućih rasporeda stanja devet žarulja.

Drugo rješenje.

Obojimo žarulje redom u tri boje:

crvena

bijela

plava

crvena

bijela

plava

crvena

bijela

plava

Na početku imamo nula crvenih, nula bijelih i nula plavih upaljenih žarulja. U svakom koraku mijenjamo stanje točno jednoj žarulji svake boje, pa se za $1$ mijenja broj upaljenih žarulja svake boje. Stoga u svakom trenutku brojevi crvenih, plavih i bijelih upaljenih žarulja moraju biti iste parnosti.

a) Ako bi druga, četvrta, šesta i osma žarulja bile ugašene, a preostalih pet žarulja upaljeno, onda bi bile upaljene dvije crvene, dvije plave i jedna plava bijela žarulja, što nije moguće jer brojevi $1$ i $2$ nisu iste parnosti.

b) Prve tri žarulje nazivamo prvi blok, srednje tri žarulje nazivamo drugi blok, a posljednje tri žarulje nazivamo treći blok.

Pokažimo da se može postići svaki raspored s istom parnosti broja upaljenih crvenih, bijelih i plavih žarulja.

Najprije pokažimo da se svaki takav raspored može svesti na raspored s jednakim brojem upaljenih crvenih, bijelih i plavih žarulja.

• Ako imamo raspored s po dvije upaljene žarulje dviju boja i niti jednu upaljenu žarulju treće boje, onda jedan od blokova sadrži točno dvije upaljene žarulje. Odaberemo li taj blok, imat ćemo točno jednu žarulje svake boje.
• Ako imamo raspored s dvije upaljene žarulje jedne boje i niti jednom upaljenom žaruljom preostalih dviju boja, onda jedan od blokova sadrži točno jednu upaljenu žarulju. Odaberemo li taj blok, imat ćemo točno jednu žarulje svake boje.
• Ako imamo raspored s po tri upaljene žarulje dviju boja i jednom upaljenom žaruljom treće boje, onda jedan od blokova sadrži dvije upaljene žarulje. Odaberemo li taj blok, imat ćemo točno dvije žarulje svake boje.
• Ako imamo raspored s tri upaljene žarulje jedne boje i jednom upaljenom žaruljom preostalih dviju boje, onda jedan od blokova sadrži jednu upaljenu žarulju. Odaberemo li taj blok, imat ćemo točno dvije žarulje svake boje.

U nastavku ćemo koristiti sljedeći postupak. Promotrimo bilo koje četiri uzastopne žarulje $ABCD$, odabirom žarulja $ABC$, te žarulja $BCD$ možemo postići da se promijene stanja žarulja $A$ i $D$, dok stanja žarulja $B$ i $C$ budu ista kao prije primjene tih koraka. Takav postupak nazivamo okretanje žarulja $A$ i $D$.

Pokažimo da se svaki raspored s jednakim brojem upaljenih žarulja iste boje može svesti na raspored u kojem za svaki blok vrijedi da su u tom bloku upaljene sve tri žarulje ili nijedna žarulja.

• Ako je upaljeno svih devet žarulja ili nijedna žarulja, onda odmah imamo takav raspored.
• Neka su upaljene po dvije žarulje svake boje. Postupkom okretanja žarulja možemo postići da su upaljene sve žarulje u prva dva bloka, te nijedna žarulja u trećem bloku.
• Neka je upaljena po jedna žarulja svake boje. Postupkom okretanja žarulja možemo postići da su upaljene sve žarulje u prvom bloku, te nijedna žarulja u druga dva bloka.

Svaku primjenu koraka možemo poništiti primjenom istog koraka. Stoga, ako iz rasporeda $X$ možemo postići raspored $Y$, onda možemo i iz rasporeda $Y$ postići raspored $X$.

Očito je da se može postići svaki raspored u kojem za svaki blok vrijedi da su u tom bloku upaljene sve tri žarulje ili nijedna žarulja. Stoga smo pokazali da su svi mogući rasporedi koji se mogu postići (iz početnog rasporeda s devet ugašenih žarulja) upravo rasporedi koji imaju istu parnost broja žarulja svake boje.

Preostaje prebrojiti takve rasporede.

Ako u svakoj boji imamo parno žarulja iste boje, onda za svaku boju imamo četiri mogućnosti: jedna mogućnost je da su sve tri žarulje te boje ugašene, a na tri načina možemo izabrati koje dvije žarulje su upaljene. S obzirom da imamo tri boje, to znači da ima ukupno $4^3=64$ takvih rasporeda.

Ako u svakoj boji imamo neparno žarulja iste boje, onda za svaku boju opet imamo četiri mogućnosti: jedna mogućnost je da su sve tri žarulje te boje upaljenje, a na tri načina možemo izabrati jednu upaljenu žarulju. S obzirom da imamo tri boje, to znači da ima ukupno $4^3=64$ takvih rasporeda.

Ukupno imamo $64+64=128$ traženih rasporeda.