Home › Archief › Internationale Olympiades › IMO › 2016 › je moet creatief denken als prinses van oranje

je moet creatief denken als prinses van oranje

Tags:

Opgave - IMO 2016 dag 2 vraag 3

In het vlak zijn $n \ge 2$ lijnstukken gegeven zodanig dat elk tweetal lijnstukken elkaar inwendig snijdt en elk drietal lijnstukken geen gemeenschappelijk punt heeft.
Amalia moet van ieder lijnstuk een eindpunt kiezen en daar een kikker plaatsen die in de richting van het andere eindpunt kijkt.
Daarna zal Amalia precies $n-1$ keer in haar handen klappen.
Bij elke klap springt iedere kikker onmiddelijk vooruit naar het volgende snijpunt op het lijnstuk.
Kikkers veranderen hierbij niet van richting.
Het is de wens van Amalia om de kikkers zodanig te plaatsen dat er nooit twee kikkers gelijktijdig op hetzelfde snijpunt zitten.

    Bewijs dat Amalia altijd haar wens kan laten uitkomen als $n$ oneven is.
    Bewijs dat Amalia nooit haar wens kan laten uitkomen als $n$ even is.

Oplossing

Ingediend door Tijs B.

a) We geven een strategie:

Teken een cirkel die alle snijpunten van de lijnstukken omvat. Trek de lijnstukken door als ze de cirkel nog niet snijden en verkort ze tot aan de cirkel indien ze wel snijden. De richting van de lijnstukken is niet veranderd, evenals de ligging van de snijpunten, en alle snijpunten bestaan nog, dus mogen we W.L.O.G. aannemen dat de eindpunten van de lijnstukken op de cirkel liggen. Begin nu door op een willekeurig eindpunt een kikker te zetten. Slaag op de cirkel een eindpunt over en plaats een nieuwe kikker op het volgende eindpunt, enzovoort.

We bewijzen dat de strategie werkt: aangezien $n$ oneven is, zal er geen lijnstuk zijn met een kikker op allebei de eindpunten. Omdat er een even aantal eindpunten is, zullen er tevens nergens kikkers naast elkaar zitten. Beschouw twee willekeurige kikkers $A$ en $B$ op lijnstukken $a$ en $b$ met snijpunt $S$. We zullen bewijzen dat deze nooit op hetzelfde snijpunt terecht zullen komen.

Merk op dat elk lijnstuk waarvan een eindpunt tussen $A$ en $B$ ligt, $a$ of $b$ zal snijden voor $S$, maar niet allebei. Aangezien dit aantal oneven is, zal er op $a$ of op $b$ voor $S$ meer snijpunten liggen, want elk lijnstuk waarvan het eindpunt niet tussen $A$ en $B$ ligt, zal ofwel zowel $a$ als $b$ snijden voor $S$ ofwel geen van beide. Omdat het aantal snijpunten voor $S$ niet gelijk is, zullen de kikkers ook niet gelijktijdig op dit snijpunt zitten, waarmee bewezen is dat de strategie werkt.

b) Construeer opnieuw een cirkel analoog zoals bij a).
Wanneer Amalia de kikkers op $n$ snijpunten van de cirkel en een verschillend lijnstuk heeft geplaatst, zullen er op de cirkel sowieso twee kikkers aan elkaar grenzen, aangezien het onmogelijk is dat ze geplaatst worden zodat er telkens één vrij eindpunt tussen hen is.
Dit omdat voor een vast lijnstuk, elk van de $n-1$ lijnstukken een eindpunt langs beide kanten heeft en het ene snijpunt van het vaste lijnstuk $n$ (even) aantal plaatsen verwijderd is van het andere.

Deze aangrenzende kikkers zullen sowieso op hetzelfde moment op het snijpunt van hun twee rechten zijn, aangezien er voor het snijpunt $S$ van de twee lijnstukken evenveel snijpunten moeten komen: indien een lijnstuk voor $S$ snijdt, moet het beide lijnstukken snijden. Q.E.D.