Školjka

%V0 Tvrdimo da je $g(n)=2$ za sve potencije broja 2 a da je $g(n)=3$ za sve ostale brojeve Jasno da je $g(n)\geq 2$ jer za $0$ i $n$ ne postoje brojevi koji čine tu artimetičku sredinu, pa je tako dovoljna konstrukcija za potencije broja 2 da bi na kraju $g(n)=2$ To činimo indukcijom po $k\geq 1$ gdje je $n=2^k$ $BAZA$ $-$ je $k=1$ trivijalna $PRETP.$ $-$da za neko $k-1$ vrijedi da $g(2^{k-1})=2$ $KORAK$ $-$od danih $0,1,...,2^k$ odaberemo interval $0,1,...,2^{k-1}$ te pretpostavkom svedemo na brojeve $0, 2^{k-1}$ slično tako $ 2^{k-1}, 2^{k-1}+1,..., 2^k$ reduciramo u $ 2^{k-1},2^k$. $-$Sada imamo $3$ broja $0, 2^{k-1},2^k$ gdje je $ 2^{k-1}$ artimetička sredina $0$ i $n$ pa nam ga je dopušteno izbaciti. Tvrdnja je time dokazana. For the sake of contradiction, pretpostavimo da je $g(n)=2$ i za brojeve koje nisu potencije broja $2$. U tom slučaju sa sigurnošću možemo tvrditi da su $0,n$ zadnji brojevi na ploči. Uzmimo neki prosti $p>2$ takav da $p$ dijeli $n$ ( takav postoji jer smo pretpostavili da $n$ nije potencija broja $2$) uočimo da je artimetička sredina $0$ i $n$ i dalje djeljiva sa $p$ odnosno kako u artimetičkoj sredini samo dijelimo sa dvojkom zajednički djelitelj dva broja će ostati $p$, tako bi backtrackingom dobili niz u kojem su svi članovi djeljivi sa $p$ što dovodi do kontradikcije jer to ne zadovoljava početne uslove zadanog niza. Dakle $g(n)\ge 3 $ za ostale $n$. Kao konstrukciju posmatramo broj $n$ u obliku $2^m+r$ gdje je $2^m$ najveći pribrojnik koji je ujedno i potencija broja 2, uočimo da je $r<2^m$ pa je u intervalu $2^m,2^m+1,...,2^m+r $ moguće obrisati članove tako da ostanu samo $2^m,n$. Međutim znamo da $0,1,...,2^m$ možemo reducirati u $0,2^m$ Tako zadani niz od $n$ brojeva možemo reducirati u $3$ elementa $0,2^m,n$. Time je početna tvrdnja dokazana.