Feladat:	N.97	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor ,  Frenkel Péter ,  Gyarmati Katalin ,  Pap Gyula ,  Prause István
Füzet:	1996/november, 486 - 487. oldal		PDF  |  MathML
Témakör(ök):	Számsorozatok, Oszthatósági feladatok, Prímszámok, Polinomok, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1996/március: N.97

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Az $x^3-x-1$ polinomnak három különböző komplex gyöke van, $\alpha$, $\beta$ és $\gamma$ (ezek közül pontosan egy valós); ez például a szokásos függvényvizsgálattal könnyen igazolható. Ismeretes, hogy ekkor alkalmas $A$, $B$, $C$ (komplex) konstansokkal $a_n=A{\alpha }^n+B{\beta }^n+C{\gamma }^n$ ($n=0$, 1, 2, $\text{...}$). Az $A$, $B$, $C$ értékét a sorozat első három tagja egyértelműen meghatározza. Esetünkben $A=B=C=1$, hiszen a gyökök és együtthatók összefüggéseiből $\alpha +\beta +\gamma =0=a_1$, ${\alpha }^2+{\beta }^2+{\gamma }^2={\left(\alpha +\beta +\gamma \right)}^2-2\left(\alpha \beta +\beta \gamma +\gamma \alpha \right)=0^2-2\left(-1\right)=2=a_2$, és persze ${\alpha }^0+{\beta }^0+{\gamma }^0=3=a_0$. Tehát $\begin{array}{c}{\displaystyle a_n={\alpha }^n+{\beta }^n++{\gamma }^n\left(n=\mathrm{0,}\mathrm{1,}\mathrm{2,}\text{...}\right)\mathrm{.}}\end{array}$ (1) Felhasználva, hogy $\alpha$, $\beta$, $\gamma$ kielégíti az $x^3=x+1$ egyenletet (1)-ből kapjuk, hogy $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{ccc}\hfill {\displaystyle a_{3n}}& {\displaystyle ={\left(\alpha +1\right)}^n+{\left(\beta +1\right)}^n+{\left(\gamma +1\right)}^n=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left({\alpha }^k+{\beta }^k+{\gamma }^k\right)=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)a_k}\hfill & \hfill {\displaystyle \left(1\right)}\\ \multicolumn{3}{c}{\text{<br>és}}\\ \hfill {\displaystyle a_n}& {\displaystyle ={\left({\alpha }^3-1\right)}^n+{\left({\beta }^3-1\right)}^n+{\left({\gamma }^3-1\right)}^n=\sum _{t=0}^n{\left(-1\right)}^t\left(\genfrac{}{}{0ex}{}{n}{t}\right)\left({\alpha }^{3t}+{\beta }^{3t}+{\gamma }^{3t}\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\sum _{t=0}^n{\left(-1\right)}^t\left(\genfrac{}{}{0ex}{}{n}{t}\right)a_{3t}\mathrm{.}}\hfill & \hfill {\displaystyle \left(2\right)}\end{array}}}\end{array}$ Tetszőleges $p$ prímre és $1\le r\le p-1$ egészre $\left(\genfrac{}{}{0ex}{}{p}{r}\right)=\frac{p\left(p-1\right)\text{...}\left(p-r+1\right)}{r!}$ osztható $p$-vel; ezért (2) szerint $\begin{array}{c}{\displaystyle a_p\equiv a_0+{\left(-1\right)}^p{a}_{3p}\equiv a_0+{\left(-1\right)}^p\left(a_0+a_p\right)\left(\text{mod}p\right)\mathrm{.}}\end{array}$ Így $p>2$-re $a_p\equiv -a_p\left(\text{mod}p\right)$, azaz $p\mid 2a_p$. adódik, amiből következik a feladat állítása.   II. megoldás. Legyen $n$ pozitív egész; írjunk bele egy körbe egy szabályos (konvex) $A_1{A}_2\text{...}{A}_n$ $n$-szöget (itt és a továbbiakban is megengedve az elfajuló ,,1- és 2-szög'' esetét is). Jelölje $b_n$ azoknak a konvex sokszögeknek a számát, amelyek csúcsai $A_1$, $A_2$, $\text{...}$, $A_n$ közül valók, és bármely két szomszédos csúcsuk az eredeti $A_1{A}_2\text{...}{A}_n$ sokszögben másod- vagy harmadszomszédos (egy vagy két eredeti csúcspont esik közéjük). Megmutatjuk, hogy $b_n=a_n$ ($n=1$, 2, $\text{...}$). Nyilván $b_1=0=a_1$, $b_2=2=a_2$, $b_3=3=a_3$; elegendő tehát igazolni a $b_n=b_{n-2}+b_{n-3}$ rekurziót ($n\ge 4$). Tekintsünk egy tetszőleges, a kívánalmaknak eleget tevő sokszöget; $A_n$, $A_{n-1}$ és $A_{n-2}$ valamelyike biztosan előfordul ennek csúcsaként, ezért e sokszög két legnagyobb sorszámú csúcsa a következő lehet: (1) $A_n$ és $A_{n-2}$;  (4) $A_n$ és $A_{n-3}$;  (2) $A_{n-1}$ és $A_{n-3}$;  (5) $A_{n-1}$ és $A_{n-4}$;  (3) $A_{n-2}$ és $A_{n-4}$;  (4) $A_{n-2}$ és $A_{n-5}$.  Ha e két csúcsot egymással és a köztük fekvő eredeti csúcspontokkal egybeejtjük (,,összehúzzuk''), majd a csúcsok számozását folyamatosan változtatjuk, akkor az (1), (2) és (3) esetben az $n-2$, míg a (4), (5), ill. (6) esetben az $n-3$ oldalú szabályos sokszögbe írt megfelelő sokszöghöz jutunk. Utóbbi sokszögek valamennyien elő is fordulnak ‐ mégpedig pontosan egyszer ‐ ezen a módon, így valóban $b_n=b_{n-2}+b_{n-3}$, tehát $b_n=a_n$. Legyen ezután $n=p$ prím. Ha $S$ egy megfelelően beírt sokszög, akkor ennek a kör középpontja körüli $\frac{{360}^{\circ }}{p}i$-vel való elforgatottjai ($i=1$, 2, $\text{...}$, $p$) is megfelelőek. Ezek páronként különbözők, hiszen ha lenne közöttük két megegyező, akkor $S$-et valamilyen $\frac{{360}^{\circ }}{p}\cdot t$ fokos forgatás önmagába vinné ($1\le t\le p-1$). Ekkor azonban a $\frac{{360}^{\circ }}{p}tj$ fokos forgatások is önmagába viszik $S$-et ($j=1$, 2, $\text{...}$, $p-1$), és e forgatások között ott van a $\frac{360}{p}$ fokos is; ez a forgatás viszont láthatóan nem viheti $S$-et önmagába. Tehát a feltételeknek megfelelően beírt $a_p$ darab sokszög $p$-s csoportokba osztható, azaz $p\mid a_p$.  Frenkel Péter (Fazekas M. Főv. Gyak. Gimn., III. o.t.)