Školjka

Koji su tocno moguci skupovi pogodaka? Skup $S$ je skup pogodaka za neka gadjanja akko za svaki cvor bar jedan od njegovih susjeda je unutar $S$. \\ Smjer $\Rightarrow$ je dosta ocit iz uvjeta zadatka, dok za $\Leftarrow$ za svaki cvor biramo pucanje na sljedeci nacin: \\ Ako je tocno jedan susjed u $S$, u njega puca. \\ Ako su oba susjeda u $S$, puca u susjeda koji je u CCW smjeru u odnosu na njega. \\ Jasno je skup pogodaka podskup od $S$, a da svakog elementa $x$ od $S$ pogadjamo je jasno ako pogledamo CW susjeda od $x$, on ce nuzno pucat u $x$ jer se nalazi na CCW strani. \\ Zamislimo graf na cvorevima poligona, izmedju neka dva cvora postoji brid akko su udaljeni za tocno 2 u CW ili CCW smjeru. Dakle $P(n)$ je broj skupova $S$ takvih da, ako je $\{x,y\}$ brid, onda je bar jedan od $x, y$ u $S$. \\ Ako je $n=2k+1$, taj graf je ciklus duljine $2k+1$, ako je $n=2k$, onda je dva disjunktna ciklusa duljine $k$. \\ Neka je $Q(n)$ broj podskupova cvoreva od ciklusa duljine $n$ takvih da za svaki brid bar jedan od vrhova je u skupu. \\ Dakle vrijedi $P(2k+1) = Q(2k+1)$ i $P(2k) = Q(k)^2$ \\ Neka je $\alpha(n)$ broj podskupova cvoreva lanca duljine $n$ sa opet istim svojstvom kao za definiciju $Q$. \\ Fiksirajmo neki cvor $x$ ciklusa duljine $n$. On moze ili biti u skupu, ili ne. Ako je, onda je broj takvih skupova $\alpha(n-1)$. Ako nije, onda mu susjedi nuzno moraju biti u skupu, pa je broj takvih skupova $\alpha(n-3)$. To jest, $Q(n) = \alpha(n-1) + \alpha(n-3)$ \\ Fiksirajmo neki cvor $x$ koji je rub lanca duljine $n$. Ako je u skupu, onda je broj takvih skupova $\alpha(n-1)$, inace $\alpha(n-2)$. Dakle $\alpha(n) = \alpha(n-1) + \alpha(n-2)$ \\ Iz $\alpha(0) = 1$, $\alpha(1) = 2$ slijedi $\alpha(n) = F_{n+2}$, gdje je $F_n$ $n$-ti Fibonaccijev broj. \\ Dakle $Q(n) = F_{n+1} + F_{n-1}$ \\ Nazad na problem, zelimo dokazati $M(P(n), P(n+1)) = 1$ \\ Prvi slucaj, $n=2k$ \\ $M(P(2k), P(2k+1)) = 1$ \\ $ \iff M(Q(k)^2, Q(2k+1)) = 1$ \\ $ \iff M(Q(k), Q(2k+1)) = 1$ \\ $ \iff M(F_{k+1} + F_{k-1}, F_{2k+2} + F_{2k}) = 1$ \\ $ \Leftarrow M(F_k(F_{k+1} + F_{k-1}), F_{2k+2} + F_{2k}) = 1$ \\ $ \iff M(F_{2k}, F_{2k+2} + F_{2k}) = 1$ \\ $ \iff M(F_{2k}, F_{2k+2}) = F_{M(2k, 2k+2)} = F_2 = 1$ \\ Drugi slucaj se dokazuje na isti nacin, samo cemo imati $F_{k+2} + F_{k}$ umjesto $F_{k+1} + F_{k-1}$ \\ Napomena, koristeno je $F_{2k} = F_k(F_{k+1} + F_{k-1})$ i $M(F_a, F_b) = F_{M(a, b)}$