triviale vraag en niet-triviale vraag
Opgave - IMO 2016 dag 1 vraag 3
Zij $P=A_1A_2 \ldots A_k$ een convexe veelhoek in het vlak.
De hoekpunten $A_1, A_2, \ldots, A_k$ hebben gehele coördinaten en liggen op een cirkel.
Zij $S$ de oppervlakte van $P$. Een oneven natuurlijk getal $n$ is gegeven.
Het kwadraat van de lengte van iedere zijde van $P$ is geheel (overbodig gegeven) en deelbaar door $n$.
Bewijs dat $2S$ geheel is en deelbaar door $n$.
- login om te reageren
Oplossing
Eerst en vooral: vanwege de formule van Pick geldt dat $2 S=o+2 i-2$, zodat $2 S$ altijd geheel is.
We geven nu de rest van het bewijs per volledige inductie op $k$.
Inductiebegin Zij $k=3$.
Zij $a,b,c$ de zijden van de driehoek. Volgens de formule van Heroon geldt dan dat
$4 S^2=4 s(s-a)(s-b)(s-c)$
$= \frac{1}{4} (a+b+c)(a+b-c)(a+c-b)(b+c-a)$
$=\frac{(a^2+2ab+b^2-c^2)(c^2-a^2-b^2+2ab)}{4}$
$=\frac{2a^2 b^2-a^4-b^4-c^4+2 b^2 c^2+2 a^2 c^2}{4}$
Omdat $ggd(n,2)=1$, geldt dat $n^2 \mid RL$, en dus $n^2 \mid 4 S^2$, dus $n \mid 2 S$.
Inductiehypothese Veronderstel dat de stelling waar is voor $k-1$, waarbij $k \ge 4$.
Inductiestap Zij nu $n=p_1^{q_1}p_2^{q_2}...p_r^{q_r}$, waarbij het LL de priemfactorisatie van $n$ is. Beschouw $p_1^{q_1}$. We bewijzen dat $2 S$ hierdoor deelbaar is. Door daarna dezelfde methode op alle andere factoren toe te passen, is de stelling bewezen.
Lemma Er bestaat een diagonaal $A_r A_s$ zodat $p_1^{q_1} \mid \left |A_r A_s \right |^2$.
Bewijs: omdat de hoekpunten roosterpunten zijn, zijn de kwadraten van de diagonalen geheel.
Alle kwadraten van de zijden zijn deelbaar door $n$ en dus ook door $p_1^{q_1}$. Beschouw de grootste $t$ zodat voor een willekeurige diagonaal geldt dat het kwadraat deelbaar is door $p_1^t$. Veronderstel $t < q_1$ (anders zijn we klaar). Dan bestaat er per definitie een diagonaal $A_x A_y$ waarvan het kwadraat niet deelbaar is door $p_1^{t+1}$.
Beschouw de koordenvierhoek $A_{x-1}A_x A_{x+1} A_y$. Dan geldt volgens de stelling van Ptolemaeus dat
$\left | A_x A_{x+1} \right | ^2 \left | A_{x-1} A_y \right | ^2+2 \left | A_x A_{x+1} \right |\left | A_{x-1} A_y \right |\left | A_{x+1} A_y\right | \left | A_x A_{x-1} \right | +\left | A_x A_{x-1} \right |^2 \left | A_{x+1} A_y\right |^2$
$=\left | A_x A_y \right |^2 \left | A_{x-1} A_{x+1} \right | ^2$
Merk op dat elke afzonderlijke term van het LL deelbaar is door $p_1^{t+q_1}$. In het rechterlid staat echter de diagonaal $A_x A_y$ waarvan het kwadraat ten hoogste deelbaar is door $p_1^{t}$. Hieruit volgt dat het kwadraat van $A_{x-1} A_{x+1}$ deelbaar is door $p_1^{q_1}$, waarmee het lemma bewezen is.
Uit het lemma volgt dat we $P$ kunnen opdelen in twee veelhoeken met minder hoekpunten van $P$. Hiervan zijn we echter al zeker dat de dubbele oppervlakte van elk van hen deelbaar is door $p_1^{q_1}$ wegens de inductiehypothese (want ze zijn deelbaar door $n$), dus is $2 S$ dat ook. Q.E.D.