5. Zadatak

Prvo rješenje

Dokazat ćemo da će ukupan zbroj uz optimalnu igru biti $29$.

Upisivanjem brojeva u ploču kao na slici Ana može osigurati da ne postoji put čiji je zbroj manji od $29$.

$9$	$7$	$1$
$6$	$3$	$5$
$2$	$4$	$8$

Nadalje, dokažimo da Borna uvijek može odabrati put čiji je zbroj najviše $29$ neovisno o Aninom rasporedu brojeva na ploči.

Neka su $A$ i $B$ brojevi u gornjem lijevom i donjem desnom kutu ploče te neka je $C$ najveći broj na dijagonali iz donjeg lijevog kuta do gornjeg lijevog kuta.

Promotrimo dva puta iz gornjeg lijevog kuta u donji desni kut ploče koja ne prolaze poljem s brojem $C$ te imaju jedino zajedničko početno i završno polje puta.

Na ta dva puta se nalaze svi brojevi od $1$ do $9$ bez broja $C$ te se brojevi $A$ i $B$ pojavljuju dva puta. Stoga imamo da je ukupan zbroj tih putova

$$\begin{aligned} &(1+2+\cdots+(C-1)+(C+1)+\cdots+9)+A+B\\ &=(1+2+\cdots+9)+A+B-C\\ &=45+A+B-C. \end{aligned}$$

Kako je $A+B\leq9+8=17$ i $C\geq3$ imamo da je ukupan zbroj brojeva na gornjim putevima najviše

$$45+A+B-C\leq45+17-3=59.$$

Iz gornjeg slijedi da barem jedan od ta dva puta ima zbroj brojeva najviše $29$ jer bi u suprotnome ukupan zbroj brojeva gornjih putova bio barem $60$.

Time smo pokazali da Borna zaista uvijek može pronaći put sa zbrojem najviše $29$.

Dakle, uz optimalnu igru, Ana i Borna će ukupno skupiti $29$ bodova.

Drugo rješenje

Uz optimalnu igru, Ana i Borna će skupiti $29$ bodova.

Isto kao u prvom rješenju, Ana može upisivanjem brojeva na ploču osigurati da ne postoji put čiji je zbroj manje od $29$.

Pokažimo da se Ani uvijek isplati brojeve $8$ i $9$ staviti u gornji lijevi i donji desni kut ploče.

Ako se broj $9$ ne nalazi niti u gornjem lijevom niti u donjem desnom kutu ploče, zamjenom broja $9$ s brojem u gornjem lijevom kutu ploče se suma brojeva na niti jednom putu nije smanjila.

Bez smanjenja općenitosti pretpostavimo da se $9$ nalazi u gornjem lijevom kutu ploče.

Ako se broj $8$ sada ne nalazi u donjem desnom kutu ploče, onda se zamjenom broja $8$ s brojem u donjem desnom kutu ploče suma brojeva na niti jednom putu nije smanjila.

Sada nastavimo s pretpostavkom da se brojevi $8$ i $9$ nalaze u gornjem lijevom i donjem desnom kutu ploče.

Neka je $C$ najveći broj na dijagonali koja spaja donji lijevi i gornji desni kut ploče.

Promotrimo dva puta iz gornjeg lijevog kuta u donji desni kut ploče koja ne prolaze poljem s brojem $C$ te imaju jedino zajedničko početno i završno polje puta.

Na ta dva puta se nalaze svi brojevi od $1$ do $9$ osim broja $C$ te se brojevi $8$ i $9$ pojavljuju dva puta. Stoga imamo da je ukupan zbroj brojeva na tim putovima jednak

$$(1+2+\cdots+9)+8+9-C=62-C.$$

Kako je $C\geq3$ imamo da je ukupan zbroj gornjih putova najviše

$$62-C\leq62-3=59,$$

iz čega slijedi da je barem jedan od ta dva puta ima zbroj najviše $29$ što smo i htjeli pokazati.