Submitted by Jens Bossaert on
Stijn Cambie is de winnaar van deze breinbreker en wint hierbij een jaarabonnement op de wiskundetijdschriften Pythagoras en Wiskunde & Onderwijs. Proficiat en veel leesplezier!
We ontvingen ook een gedeeltelijke inzending van Marc Peeters. Bedankt hiervoor!
Oplossing
Er zijn $\left\lceil\frac{m+n}{2}\right\rceil$ kabouters nodig.
Beschouw de omtrek van het reeds verkende gebied. Als we $k$ parachutisten laten landen, is deze omtrek vlak na de landing hoogstens $4k$. Als ze het bos nu gaan verkennen, kan deze omtrek enkel maar afnemen (of gelijk blijven). Inderdaad: als een nieuwe sector verkend wordt, verdwijnen er minstens twee zijden uit de rand van het gebied, en komen er hoogstens twee bij. Als op een zeker moment heel het bos verkend is, is de omtrek van het verkende gebied $2(m+n)$. Maar wegens de bovenstaande observatie is dat pas mogelijk als de omtrek op het begin ook al minstens $2(m+n)$ was. Dus moet er gelden dat $4k \ge 2(m+n)$.
Om het bos volledig te verkennen, hebben we dus minstens $\left\lceil\frac{m+n}{2}\right\rceil$ kabouters nodig.
Dit minimale aantal parachutisten is ook steeds voldoende. We kunnen ze bijvoorbeeld op de volgende plaatsen laten landen: stel zonder verlies van algemeenheid dat $m \ge n$; dan bestaat het bos uit een $n \times n$ vierkant met daaronder nog $m-n$ extra rijen. We laten dan op elk vakje van de (hoofd-) diagonaal van dat vierkant een kabouter landen, en verder nog één op rijen nummer $n+2$,$n+4$ etc., en dan nog één op de laatste rij (als er daar nog geen stond).