een vraag over voetballers; een col van 1e categorie naar goud
Opgave - IMO 2017 dag 2 vraag 2
Zij gegeven een geheel getal $N$ > $2$. Een groep van $N(N +1)$ voetballers, allemaal van
verschillende lengte, staat op een rij. De bondscoach wil $N(N-1)$ voetballers uit deze rij verwijderen zodat een rij van $2N$ voetballers overblijft die aan de volgende $N$ voorwaarden voldoet:
(1) er staat niemand tussen de twee langste voetballers,
(2) er staat niemand tussen de op twee na langste en de op drie na langste voetballer,
$\ldots$
(N) er staat niemand tussen de twee kortste voetballers.
Bewijs dat dit altijd mogelijk is.
- login om te reageren
Oplossing
Verdeel de $N(N+1)$ spelers in $N$ opeenvolgende groepen van $N+1$ spelers. We zullen bewijzen dat het altijd mogelijk is om uit elk van deze groepen dan $2$ spelers te kiezen zodat aan alle voorwaarden voldaan is.
Beschouw de groep waarin de op één na grootste speler het grootst is. Zij $A$ deze speler. Verwijder uit deze groep alle spelers behalve de grootste speler en $A$, zij vormen de eerste groep in onze nieuwe telling.
Verwijder uit alle andere groepen de spelers die groter zijn dan $A$. We verwijderen telkens maximaal één speler, aangezien de op één na grootste uit elke groep kleiner is dan $A$.
Herhaal dit algoritme nog $N-1$ keer met de overige groepen.
Na stap $k$, zijn er nog $N-k$ overige groepen, met elk minimum $N+1-k$ personen.
Dit betekent dat het algoritme wel degelijk herhaald kan worden.
De spelers die overblijven voldoen dan aan alle voorwaarden, aangezien de spelers die over zijn van de eerste groep (met de nieuwe telling) de grootste zullen zijn, die van de tweede groep de op twee na en op drie na grootste, enzovoort.
De personen die overblijven van de $k^{de}$ groep zijn net de $2$ personen vermeld in voorwaarde $(k)$ van de opgave en tussen hen staat niemand anders omdat ze de enige $2$ personen van de oorspronkelijke groep zijn.