3. Zadatak

Dano je 2014 žetona koji su s jedne strane crne, a s druge bijele boje i ploča dimenzija $2014\times1$ . Na početku se na svakom polju ploče nalazi po jedan žeton, okrenut na crnu ili na bijelu stranu. U svakom potezu dozvoljeno je ukloniti jedan žeton okrenut na crnu stranu i istovremeno preokrenuti žetone na susjednim poljima (ako nisu već uklonjeni).

Odredi sve početne rasporede žetona za koje je nizom takvih poteza moguće ukloniti sve žetone.

Rješenje

Matematičkom indukcijom po broju žetona dokazat ćemo tvrdnju: Iz nekog početnoga rasporeda možemo ukloniti sve žetone ako i samo ako je u tom rasporedu neparan broj žetona okrenut na crnu stranu.

Ako je na ploči samo jedan žeton, možemo ga ukloniti ako i samo ako je okrenut na crnu stranu.

Za prirodni broj $N>1$ , pretpostavimo da je tvrdnja istinita za sve rasporede koji se sastoje od manje od $N$ žetona i promotrimo proizvoljan početni raspored od $N$ žetona. Neka je $K$ broj žetona u tom rasporedu koji su okrenuti na crnu stranu.

Primijetimo da se uklanjanjem nekog žetona ploča razdvaja u dva dijela te da potezi na jednom od ta dva dijela ne utječu na žetone drugog dijela.

Ako je $K$ neparan broj, dokazat ćemo da je moguće ukloniti sve žetone. Neka je $Y$ prvi žeton na ploči koji je okrenut na crnu stranu. Pretpostavimo da $Y$ nije ni na prvom ni na zadnjem mjestu ploče, te nazovimo $X$ žeton na polju ispred $Y$ , a $Z$ žeton na polju iza $Y$ . U prvom potezu uklonimo $Y$ i polje ploče na kojem se nalazi $Y$ (te preokrenemo $X$ i $Z$ ). Na taj način ćemo dobiti dvije manje ploče. Pokazat ćemo da sa svake od njih možemo ukloniti sve žetone.

Na prvoj ploči se nalaze svi žetoni koji su ispred $Y$ , a na drugoj ploči svi žetoni koji se nalaze iza $Y$ .

Na prvoj ploči su svi žetoni okrenuti na bijelu stranu, osim $X$ kojeg smo upravo okrenuli na crnu stranu. Dakle, na prvoj ploči je točno jedan žeton okrenut na crnu stranu, pa prema pretpostavci indukcije postoji niz poteza kojim možemo ukloniti sve žetone s te ploče.

Ako je $Z$ okrenut na bijelu stranu, onda će nakon poteza broj žetona na drugoj ploči koji su okrenuti na crnu stranu biti jednak $K$ . Ako je $Z$ okrenut na crnu stranu, onda će nakon poteza broj žetona na drugoj ploči koji su okrenuti na crnu stranu biti $K-2$ . U oba slučaja broj žetona na drugoj ploči je neparan. Prema pretpostavci indukcije zaključujemo da možemo ukloniti sve žetone i s druge ploče.

Ako je $Y$ prvo polje ploče, onda promatramo samo drugu ploču i žeton $Z$ , a ako je $Y$ zadnje polje ploče, onda promatramo samo prvu ploču i žeton $X$ .

Pretpostavimo da je $K$ paran broj i da za promatrani početni raspored postoji niz poteza kojim možemo ukloniti sve žetone. Neka je $Y$ žeton kojeg uklanjamo u prvom potezu. Uz žeton $Y$ , na ploči se prije tog poteza nalazio neparan broj žetona okrenutih na crnu stranu. Ukupan broj žetona okrenutih na crnu stranu na dva dijela ploče nakon poteza će i dalje biti neparan broj. Stoga se na jednom dijelu ploče nalazi paran broj žetona okrenutih na crnu stranu.

Prema pretpostavci indukcije, žetoni s tog dijela ploče se ne mogu ukloniti, pa dolazimo do kontradikcije. Time smo pokazali da ako je moguće ukloniti sve žetone, onda broj žetona okrenutih na crnu stranu ne može biti paran.