6. úloha vzorové riešenie

Úloha mala len jedno riešenie, a to \(N=3\), ktoré našli všetci riešitelia. Na to aby sme dokázali, že iné riešenia neexistujú, bol kľúčový poznatok horný odhad pre \(S(N)=(d_1,d_2)+\dots+(d_{k-1},d_{k})\leq N-1\). To sa dá sa vidieť, lebo ak pre rôzne \(a,\, b\) platí, že \((a,b)=D\), tak \(D \mid a\) a \(D \mid b\), a potom aj \(D \mid (a-b)\). Pre rôzne \(a,\, b\) môžeme preto napísať: \((a,b)\leq|a-b|\) a \(S(n)\) môžeme odhadnúť ako \[(d_1,d_2)+(d_2,d_3)+\dots+(d_{k-1},d_{k})\leq(d_2-d_1)+(d_3-d_2)+\dots+(d_{k}-d_{k-1})=d_{k}-d_1=N-1.\] Keďže my potrebujeme \(N-2\), to znamená, že všetky dvojice najväčších spoločných deliteľov sa musia rovnať ich rozdielu (\((d_{a},d_{a+1})=d_{a+1}-d_{a}\)) okrem jednej, ktorá musí byť o jedna menej, teda existuje jediné také \(i\), že \(D=(d_{i},d_{i+1})=d_{i+1}-d_{i}-1\). Potom \(D \mid d_{i+1}\), \(D \mid d_{i}\) a \(D \mid d_{i+1}-d_{i}-1\) takže \(D \mid -1\) čiže \(D=1\). Takže z \(D=d_{i+1}-d_{i}-1\) vieme, že \(d_{i+1}-d_i=2\). Teraz vidíme, že oba delitele sú nepárne (ak by boli oba párne tak by \(2 \mid D\) a následne \(2 \mid 1\)). Číslo \(N\) si môžeme zapísať ako \(N=d_{i}\cdot d_{i+1}\cdot R\), pre vhodné prirodzené \(R\).

Teraz sa pozrieme na dva prípady. Ak by \(R=1\), tak buď \(d_i=1\) a v tom prípade ľahko zistíme, že \(d_{i+1}=3\), a teda \(N=3\), alebo \(d_{i}>1\). Teraz bude mať \(N\) deliteľov: \(1,\, d_2,\, \dots,\, d_i,\, d_{i+1},\, \dots,\, N\). Tu problém nastane v dvojici \((1,d_2)\). Vieme, že \(d_2\) je nepárne, lebo \(N=d_{i} d_{i+1}\) je nepárne. Tu máme problém, lebo \((1,d_2)=1\), ale \(d_2-1\geq2\) (kvôli parite \(d_2\)) a to je spor z predpokladom, že \((d_i,d_{i+1})\) je jediná dvojica, čo sa nerovná vlastnému rozdielu (\(d_{i+1}-d_i\)). Druhý prípad je, ak \(R>1\). Pozrieme sa na čísla \(Rd_i\) a \(R d_{i+1}\). Tieto dva delitele \(N\) pôjdu určite za sebou. Ľahko si overíme, že ak by pre nejaké prirodzené \(P\) platilo \(P \mid N\) a \(Rd_i<P<Rd_{i+1}\), tak \(N/P\) by padlo medzi \(d_i\) a \(d_{i+1}\), čo sa nemôže stať. Zjavne je \((Rd_i,Rd_{i+1})=R\). Využitím \(d_{i+1}-d_i=2\) odvodíme \(Rd_{i+1}-Rd_i=2R\). Tieto dve čísla by sa mali rovnať, ale \(R\neq2R\), takže máme spor. Teda jediné číslo, čo postúpi do ďalšieho kola je \(N=3\).