Feladat:	2016. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Szabó Barnabás
Füzet:	2016/október, 389 - 390. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Oszthatóság
Hivatkozás(ok):	Feladatok: 2016/szeptember: 2016. évi Nemzetközi Matematika Diákolimpia 13. feladata

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.   Szabó Barnabás megoldása. Lemma. Ha $x$ és $y$ egészek, akkor $x^2\mid y^2$ esetén $x\mid y$. Bizonyítás. $x\nmid y$ esetén létezik egy $q$ prím és $r$ nemnegatív egész, melyekre $q^r\mid x$ de $q^r\nmid y$, ekkor viszont $q^{2r}\mid x^2$ és $q^{2r}\nmid y^2$, tehát $x^2\mid y^2$ nem teljesülhetne. A feladat állítását $k$-ra vonatkozó teljes indukcióval fogjuk belátni. $k=3$ esetén feltehető, hogy az $A_1$, $A_2$ és $A_3$ csúcsok koordinátái rendre $\left(\mathrm{0,0}\right)$, $\left(a_1\mathrm{,}{b}_1\right)$ és $\left(a_2\mathrm{,}{b}_2\right)$ (ahol $a_i$, $b_i$ egészek). Tudjuk, hogy $n\mid a_1^2+b_1^2$ és $n\mid a_2^2+b_2^2$, továbbá $n\mid {\left(a_1-a_2\right)}^2+{\left(b_1-b_2\right)}^2=\left(a_1^2+b_1^2\right)+\left(a_2^2+b_2^2\right)-2\left(a_1{a}_2+b_1{b}_2\right)$, mivel $n$ páratlan, így $n\mid a_1{a}_2+b_1{b}_2$. Innen $n^2\mid \left(a_1^2+b_1^2\right)\left(a_2^2+b_2^2\right)-{\left(a_1{a}_2+b_1{b}_2\right)}^2={\left(a_1{b}_2-a_2{b}_1\right)}^2$. Ebből $n\mid a_1{b}_2-a_2{b}_1$ következik. A jól ismert területképlet alapján $\begin{array}{c}{\displaystyle 2S=|a_1{b}_2-a_2{b}_1|\mathrm{,}\text{azaz}n\mid 2S\mathrm{,}}\end{array}$ és ezt kellett belátni. Nyilvánvalóan elegendő az állítást prímhatvány $n$-re belátni (ha $x\mid 2S$ és $y\mid 2S$, ahol $\left(x\mathrm{,}y\right)=1$, akkor $xy\mid 2S$). Legyen $n=p^{\alpha }$, $p>2$. Esetünkben $k\ge 4$ és tegyük fel, hogy az állítást minden $k$-nál kisebb (de legalább 3) pozitív egészre beláttuk. Találni fogunk egy átlót, amely hosszának négyzete osztható $n$-nel, így ezen átló mentén félbevágva $P$-t két kisebb oldalszámú sokszöget kapunk, $P_1$-et (területe $S_1$) és $P_2$-t (területe $S_2$), amelyekre teljesül a feladat feltétele. Az indukciós feltevés miatt $n\mid 2S_1+2S_2=2S$, azaz készen lennénk a feladattal. Tehát már csak egy megfelelő átlót kell találnunk. $P$ rácssokszög, így a Pitagorasz-tétel alapján $P$ minden átlójának négyzete egész szám. Vegyük az átlók közül azt (vagy az egyiket néhány közül), amelyik hosszának négyzetében $p$ kitevője minimális. Legyen ez az $AC$ átló. Az $A$-val szomszédos csúcsok $B$ és $D$. Legyen az $AB$, $BC$, $CD$, $DA$, $AC$ és $BD$ szakaszok hossza rendre $a$, $b$, $c$, $d$, $e$, $f$. Az $ABCD$ húrnégyszögre a Ptolemaiosz-tételt felírva kapjuk, hogy $\begin{array}{c}{\displaystyle ac+bd=ef\mathrm{,}}\end{array}$ (1) ezt négyzetre emelve $\begin{array}{c}{\displaystyle a^2{c}^2+b^2{d}^2+2abcd=e^2{f}^2\mathrm{.}}\end{array}$ (2) Legyen $\beta$ az a legnagyobb nemnegatív egész, melyre $p^{\beta }\mid e^2$. Ha $\beta \ge \alpha$, akkor $AC$ megfelelő átló. A továbbiakban feltesszük, hogy $\beta <\alpha$. Ekkor $p^{\alpha }\mid a^2$ és $p^{\beta }\mid c^2$ (ha $CD$ átló, akkor ez $AC$ választása miatt igaz, ha $CD$ oldal, akkor $\beta <\alpha$ miatt), tehát $p^{\alpha +\beta }\mid a^2{c}^2$. Hasonlóan $p^{\alpha +\beta }\mid b^2{d}^2$. Mivel $e^2{f}^2$ is egész, így (2) alapján $2abcd$ is az. Viszont $p^{2\left(\alpha +\beta \right)}\mid 4a^2{b}^2{c}^2{d}^2$, így $p^{\alpha +\beta }\mid 2abcd$. Ezt felhasználva (2)-ből következik, hogy $p^{\alpha +\beta }\mid e^2{f}^2$, így $p^{\beta +1}\nmid e^2$ miatt $p^{\alpha }\mid f^2$, azaz ekkor a $BD$ átló megfelelő.