Školjka

%V0 Neka je $(a_1, a_2, ..., a_{2014})$ konfiguracija raspoloženja građana prije bilo koje interakcije spomenute u zadatku. Pritom je $a_i$ raspoloženje osobe $A_i$ s tim da je $a_i = -1$ ako je $A_i$ sretan, a $a_i=1$ ako je $A_i$ nesretan. Neka je $f(a_1, a_2, ..., a_{2014})$ konfiguracija raspoloženja nakon što se svaki $A_i$ nasmije $A_{i+1}$, a da je $(a_1, a_2, ..., a_{2014})$ prijašnja konfiguracija. Iteraciju funkcije $f \ k$ puta na konfiguraciju $(a_1, a_2, ..., a_{2014})$ označavamo s $f_k(a_1, a_2, ..., a_{2014})$. Po prirodi promjene raspoloženja kakva je opisana u zadatku vrijedi $f_k(a_1)=a_1, \forall k\in \mathbb{N}$. Nadalje imamo $f(a_{i+1})=f(a_i)a_{i+1}$ te šire $f_{k+1}(a_{i+1})=f_{k+1}(a_i)f_k(a_{i+1})$. Poznato nam je i $| \{ i:f_4(a_i)=-1\} | = 2000$. Promotrimo prvih nekoliko vrijednosti $f(a_i)$. Slijedimo li tvrdnje gore lako dobijemo $f(a_2)=a_1a_2, f(a_3)=a_1a_2a_3,...$. Dade se naslutiti i induktivno dokazati da je $$f(a_i)=\prod \limits_{j=1} ^i a_j$$ Daljnjim ružnim raspisivanjem se opet dade naslutiti i induktivno dokazati sljedeće $$ f_2(a_i)=\prod \limits_{ \substack { j \leq i \\ j \equiv i \ (\text {mod} \ 2 )} } a_j$$ $$f_3(a_i) = \prod \limits_{ \substack {j \leq i \\ (j - i) \ \text{mod} \ 4 \in \{ 0,-1\}} } a_j$$ $$f_4(a_i) =\prod \limits_{ \substack { j \leq i \\ j \equiv i \ (\text {mod} \ 4 )} } a_j$$ Sada po ostatku pri dijeljenju s $4$ konfiguraciju $f_4(a_1, a_2, ..., a_{2014})$ možemo podijeliti na 4 po faktorima disjunktne potkonfiguracije, $(a_1, a_1a_5, ..., a_1a_5...a_{2013}), (a_2, a_2a_6, ..., a_2a_6...a_{2014}),(a_3,a_3a_7,...,a_3a_7...a_{2011}), (a_4,a_4a_8,...,a_4a_8...a_{2012}) $. Uočimo da na svake dvije $-1$ dolazi barem jedna $1$ te da ako je neki početni član $1$, na tu barem jednu $1$ dolazi maksimalno jedna $-1$. Stoga je optimalno ako na svaku od 14 $1$ dolaze dvije $-1$ te ako su svi početni članovi $-1$. Zaključujemo da je $N \leq 4+2 \cdot 14=32$. Za $N=32$ nudimo sada jasan primjer. Neka je $S= \{ 1,2,3,4,5,9,13,17,...,1+4 \cdot 27, 1+4\cdot 28 \}$. Ako je $i \in S$ tada neka je $a_i = -1$, a u suprotnom $a_i = 1$. Stoga je $N=32$ doista najveći mogući broj sretnih građana.