5. Zadatak

Andrija i Boris imaju 2014 karata označenih brojevima od 1 do 2014. Andrija ima sve karte s parnim, a Boris sve karte s neparnim brojevima. Andrija je poredao svoje karte ukrug redom, od 2 do 2014, u smjeru kazaljke na satu tako da se brojevi na kartama ne vide. Boris zna da su karte poredane tim redom i u tom smjeru, ali ne zna gdje se nalazi karta s brojem 2. Nakon toga, Boris na svaku Andrijinu stavi po jednu od svojih karata i tako nastane 1007 parova karata. Za svaki se par usporedi brojeve na kartama i dodijeli jedan bod onom igraču na čijoj je karti veći broj.

Odredi najveći mogući $N$ tako da Boris može biti siguran da će ostvariti barem $N$ bodova.

Rješenje

Najveći broj bodova za koji Boris može biti siguran da će ostvariti je 503.

Tvrdimo da ako Boris svoje karte složi obrnutim redom, od 2013 do 1, u smjeru kazaljke na satu, onda će bez obzira na Andrijin raspored Boris ostvariti 503 boda.

Službeni dijagram rasporeda karata

Za takav Borisov raspored, promotrimo neki Andrijin raspored. Ispod Borisove karte 2013 se nalazi Andrijina karta $2k$ , za neki $k\in\mathbb N$ . Pretpostavimo da je $2k\ne2014$ , slučaj u kojem je $2k=2014$ izravno slijedi. Na slici je prikazan raspored karata napisan u niz, počevši od mjesta na koje je Boris stavio kartu 2013. Parove karata podijelimo u dva dijela: dio u kojem se nalaze Andrijine karte $2k,2k+2,\ldots,2012,2014$ , te drugi dio u kojem se nalaze $2,4,\ldots,2k-4,2k-2$ . U prvom dijelu Andrijine karte (slijeva nadesno) rastu od $2k$ do 2014, a Borisove padaju od 2013. Drugim riječima, na početku tog dijela su Borisove karte veće, a na kraju su Andrijine veće. Označimo s $2a+1$ ( $a\in\mathbb N$ ) zadnju Borisovu kartu u prvom dijelu koja je veća od odgovarajuće Andrijine karte, koju označimo s $2b$ za neki $b\in\mathbb N$ . Dakle, vrijedi

2a+1>2b,\qquad 2a-1<2b+2.

Iz prethodnih nejednakosti slijedi $2a-3<2b<2a+1$ , pa je $2b=2a-2$ ili $2b=2a$ .

Primijetimo da je zbroj karata u svakom paru prvog dijela jednak i iznosi $2013+2k$ . Naime, u svakom sljedećem paru je Borisov broj za 2 manji od prethodnog, a Andrijin za 2 veći od prethodnog, pa se zbroj ne mijenja. Stoga vrijedi $(2a+1)+2b=2013+2k$ .

Ako je $2b=2a-2$ , onda je $k$ neparan broj i $a=\frac{1007+k}{2}$ . Slično, ako je $2b=2a$ , onda je $k$ paran broj i $a=\frac{1006+k}{2}$ . Ako je $X$ broj parova u prvome dijelu u kojima je Borisova karta veća od Andrijine, onda je $X=b-k+1$ . Stoga zaključujemo da vrijedi

X=\begin{cases} \frac{1007-k}{2},&\text{ako je }k\text{ neparan},\\ \frac{1008-k}{2},&\text{ako je }k\text{ paran}. \end{cases}

Nadalje, označimo sa $Y$ broj parova u drugome dijelu u kojima je Borisova karta veća od Andrijine. Analognim zaključivanjem kao u prvome dijelu, dobivamo

Y=\begin{cases} \frac{k-1}{2},&\text{ako je }k\text{ neparan},\\ \frac{k-2}{2},&\text{ako je }k\text{ paran}. \end{cases}

Stoga je $X+Y=503$ bez obzira na vrijednost broja $k$ , te zaključujemo da će slaganjem karata na ovaj način Boris ostvariti 503 boda.

Preostaje nam dokazati da Boris ne može rasporediti svoje karte tako da njegov broj bodova bude veći od 503 bez obzira na Andrijin raspored.

Pretpostavimo da postoji Borisov raspored za koji Andrija ostvaruje manje od 504 boda bez obzira kako postavi svoje karte. Za takav Borisov raspored, označimo s $A$ ukupni broj bodova koje Andrija ostvari u svim svojim mogućim rasporedima. Mogućih Andrijinih rasporeda ima 1007, pa po pretpostavci vrijedi $A<1007\cdot504$ . S druge strane, promotrimo koliko broju $A$ pridonosi svaka od Borisovih karata. Karta s brojem 2 doprinosi ukupno 1 bod jer daje bodove samo u rasporedu u kojem se karta s brojem 1 nalazi iznad nje. Karta s brojem 4 donosi 2 boda (slučajevi u kojima su iznad nje karte 1 i 3). Općenito, za $k\in\{1,2,\ldots,1007\}$ karta s brojem $2k$ donosi $k$ bodova. Stoga vrijedi

A=1+2+\cdots+1007=\frac{1007\cdot1008}{2}=1007\cdot504.

Došli smo do kontradikcije, pa zaključujemo da naša pretpostavka nije bila točna, tj. da Boris ne može biti siguran da će ostvariti više od 503 boda.