Submitted by jonas on
De winnaar van de breinbreker van mei-juni is Sofian De Clercq! Sofian stuurde ons twee juiste oplossingen en ontvangt als prijs een jaarabonnement op het tijdschrift Pythagoras en op het tijdschrijft Wiskunde & Onderwijs. Proficiat en veel leesplezier!
We kregen ook nog juiste inzendingen van Yannick Neyt (3 oplossingen) en Stijn Cambie. Bedankt voor de inzending en tot volgende breinbreker.
Een oplossing van Sofian
Veronderstel dat op de convexe $n$-hoek $P$ een aantal diagonalen getekend staan, opnieuw op zo'n manier dat geen twee diagonalen elkaar snijden. We bewijzen de stelling dat aan elke kant van gelijk welke diagonaal uit deze collectie minstens $1$ hoekpunt van $P$ geen vertrekpunt zal zijn van een getekende diagonaal.
Selecteer nu $1$ van de getekende diagonalen. Kan je zo geen diagonaal vinden dan aangezien $P$ minstens een driehoek moet zijn is het probleem opgelost (we hebben minstens $2$ hoekpunten gevonden waaruit geen diagonaal vertrekt).
We snijden $P$ in twee convexe veelhoeken langs deze gekozen diagonaal ($AB$). Neem nu een van deze veelhoeken en noem ze $P_0$ (voor de andere veelhoek is de redeneerwijze analoog). We weten dat $P_0$ minder hoekpunten telt dan $P$ en er geen getekende diagonalen lopen van $P_0$ naar de andere gevormde veelhoek behalve diagonalen die vertrekken vanuit $A$ of $B$. In de eerste iteratiestap selecteren we een getekende diagonaal in $P_0$ (uiteraard verschillend van $AB$ want deze is geen diagonaal van $P_0$). Deze verdeelt $P_0$ in twee kleinere veelhoeken waarvan er een is met slechts $1$ zijde die samenvalt met een getekende diagonaal. Noem die veelhoek $P_1$. Het aantal hoekpunten in $P_1$ is kleiner dan die in $P_0$. Verder weten we dat zoals $P_0$, de omtrek van $P_1$ gevormd wordt door een aaneensluiting van zijden van $P$ en een getekende diagonaal. We herhalen dit proces tot er binnen, laat het ons $P_n$ noemen, geen diagonalen meer zijn. De omtrek van $P_n$ bestaat uit een reeks opeenvolgende zijden uit $P$ en $1$ getekende diagonaal. Sinds $P_n$ minstens een driehoek is, is het aantal opeenvolgende zijden uit $P$ in $P_n$ minstens $2$. Het aantal hoekpunten van $P$ die hierdoor omsloten worden is dus minstens $1$.