5. Zadatak

Dana je dvadeset i jedna točka kao na slici. Na početku je svakoj točki pridružen broj nula.

Dvadeset i jedna točka povezana vodoravnim, okomitim i dijagonalnim dužinama.

U svakom potezu odabire se pravac koji sadrži neku od nacrtanih dužina i u svim točkama kroz koje taj pravac prolazi, pridruženi brojevi se povećavaju za 1. Kažemo da je prirodni broj $n$ dohvatljiv ako se na opisani način može postići da je nakon određenog broja poteza svim točkama pridružen isti broj $n$ .

a) Dokaži da je broj 2010 dohvatljiv.

b) Dokaži da broj 2011 nije dohvatljiv.

Rješenje

a) Pokazat ćemo da su svi parni brojevi, pa tako i broj 2010, dohvatljivi.

Najprije uvećajmo za 1 brojeve u sva tri retka i u sva tri stupca kao na lijevoj slici.

Brojevi nakon uvećanja duž tri retka i tri stupca.

Broj 2 pridružen svim točkama.

Zatim uvećajmo brojeve u svim točkama koje leže na pravcima koji su paralelni jednoj od dijagonala velikog kvadrata za 1. Rezultat je prikazan na desnoj slici. Time smo dobili broj 2 u svim točkama, pa je ponavljanjem tog postupka moguće u svim točkama dobiti broj 2010, odnosno bilo koji parni broj.

b) Pokažimo sada da nijedan neparni broj, pa tako niti broj 2011, nije dohvatljiv.

Označimo s $h_1,h_2,h_3$ broj uvećanja po odgovarajućim retcima (horizontalni potezi), s $v_1,v_2,v_3$ broj uvećanja po odgovarajućim stupcima (vertikalni potezi), te s $A,B,C,D,a,b,c,d$ broj uvećanja po odgovarajućim dijagonalama (dijagonalni potezi), kao na sljedećim slikama.

Oznake h1, h2 i h3 za horizontalne poteze.

Oznake v1, v2 i v3 za vertikalne poteze.

Oznake A, B, C i D za dijagonalne poteze.

Oznake a, b, c i d za dijagonalne poteze.

Promotrimo sada točke označene zvjezdicama na lijevoj donjoj slici. Kako dijagonalni potezi ne prolaze tim točkama, vrijedi $h_1+v_1=h_1+v_2=h_1+v_3=h_2+v_1=\ldots=h_3+v_3=n,$ odakle dobivamo da je $h_1=h_2=h_3$ i $v_1=v_2=v_3$ . Dakle, svih triju horizontalnih poteza ima jednako. Isto vrijedi i za sva tri vertikalna poteza. Označimo li $h=h_1=h_2=h_3$ i $v=v_1=v_2=v_3$ , mora vrijediti $h+v=n$ .

Devet točaka označenih zvjezdicama.

Četiri točke označene kvadratićima.

Promatrajmo sada ukupan broj uvećanja u točkama označenim kvadratićima na desnoj slici. Mora vrijediti $v+B+c=h+B+b=v+C+b\quad h+C+c=n.$ Odavde je $B+c=C+b$ i $B+b=C+c$ , odakle dobivamo $b=c$ i $B=C$ . Zbog toga je $v+B+b=h+B+b$ , odakle je $v=h$ . Stoga dobivamo da je $n=v+h=2h$ paran broj, a to je kontradikcija jer je $n$ neparan broj. Zaključujemo da nijedan neparni broj nije dohvatljiv.

Drugi način.

Kontradikciju u b) dijelu zadatka možemo dobiti na još jedan način. Promotrimo još jednom točke označene zvjezdicama.

Devet točaka označenih zvjezdicama za drugi način dokazivanja.

Označimo sa $S$ zbroj svih brojeva pridruženim tim točkama. Na početku je $S=0$ , a u svakom se koraku $S$ mijenja. Svakoj točki bi na kraju trebao biti pridružen isti neparni broj, a kako je ukupni broj promatranih polja neparan, $S$ također mora biti neparan. Broj pridružen uočenim poljima broj može se povećati isključivo povećanjem brojeva za 1 u cijelom retku ili cijelom stupcu tj. horizontalnim ili vertikalnim potezom. Nadalje, svakim horizontalnim i vertikalnim potezom mijenja se parnost broja $S$ . S obzirom da $S$ na kraju mora biti neparan, broj horizontalnih i vertikalnih poteza mora biti neparan. No, kao u prvom rješenju zaključujemo da horizontalnih i vertikalnih poteza mora biti jednako pa je njihov zbroj paran, a to je kontradikcija.