Problem 1992

Solution:

Als $m$ (het aantal rijen) even is, dan koppelen we de vakjes van het bord in tweetallen aan elkaar: in elke kolom vormen de bovenste twee vakjes een tweetal, en het derde en vierde vakje, enzovoorts. Omdat er een even aantal rijen is, lukt dit. Prik kan nu de volgende strategie hanteren: als Stekel een vakje van zo'n tweetal bezet, zet hij een pion in het andere vakje van dit tweetal. Na elke zet van Prik zijn op deze manier alle tweetallen met nul of met twee pionnen bezet, dus hij kan deze strategie steeds blijven uitvoeren. Hij voldoet automatisch aan de voorwaarde dat zijn pion grenst aan de pion die Stekel net heeft neergezet. Prik kan dus zorgen dat het hele bord vol met pionnen komt en wint. Als $n$ even is, heeft Prik analoog ook een winnende strategie.

Als $m=n=1$ hoeft Prik geen enkele pion te zetten om te winnen. Als $m=1$ en $n=3$ of andersom, zet Prik zijn eerste pion op een vakje dat grenst aan het vakje waar Stekel net een pion heeft neergezet; dat lukt altijd. Het bord is dan na de volgende zet van Stekel vol, dus Prik wint.

Bekijk nu het geval dat $m=n=3$. Stekel kan de volgende strategie volgen. Hij zet zijn eerste pion in het middelste vakje. Prik moet in dezelfde rij of in dezelfde kolom een pion zetten; zonder verlies van algemeenheid nemen we aan dat de pion van Prik in dezelfde kolom komt. Stekel zet nu in het derde vakje van deze kolom een pion. Op dat moment zijn de linker- en rechterkolom nog helemaal leeg. Prik moet in één van beide een pion zetten. Stekel kiest vervolgens de andere kolom: daar zijn nog drie vakjes leeg. Hij plaatst daar een pion en dwingt Prik daarmee om ook in die kolom een pion te zetten; de vakjes in de middelste kolom zijn immers allemaal al vol. Stekel plaatst vervolgens een pion in het laatste vakje van die kolom, waarna Prik niet meer kan. Dus Stekel wint.

Blijft over het geval dat $m$ en $n$ allebei oneven zijn en dat $m \geq 5$ of $n \geq 5$ (of allebei). We bekijken het geval dat $n$ (het aantal kolommen) minstens 5 is. Het andere geval gaat analoog. Stekel kan nu de volgende strategie volgen. Hij zet zijn pionnen steeds in de middelste kolom, totdat die kolom vol is. Als Stekel vervolgens weer aan de beurt is, staat er een even aantal pionnen op het bord, allemaal in de middelste drie kolommen, waarbij de middelste kolom in elk geval helemaal vol is. De linker- en rechterkolom zijn nog helemaal leeg. Er is nog een oneven aantal vakjes open, dus ofwel het gebied links van de middelste kolom ofwel het gebied rechts van de middelste kolom bevat een oneven aantal lege vakjes.

Stekel kiest dat gebied en plaatst vervolgens al zijn pionnen daar, op willekeurige plekken. Omdat de middelste kolom helemaal vol is, moet Prik nu ook al zijn pionnen in dat gebied zetten. Er was een oneven aantal vakjes leeg in dit gebied, dus Stekel bezet in principe het laatste vakje. Prik kan daarna niet meer zetten, dus Stekel wint. Mocht Prik al in een eerdere beurt niet meer kunnen zetten, dan wint Stekel ook.

We concluderen dat Stekel wint als $m$ en $n$ oneven zijn en $m \geq 5$, als $m$ en $n$ oneven zijn en $n \geq 5$, en als $m=n=3$. Prik wint in alle overige gevallen: als $m$ even is, als $n$ even is, als $m=n=1$, als $m=1$ en $n=3$ en als $m=3$ en $n=1$.