Submitted by Jens Bossaert on
De winnaar van deze breinbreker is Jef Laga, die hierbij een jaarabonnement wint op de wiskundetijdschriften Pythagoras en Wiskunde & Onderwijs. Proficiat en veel leesplezier!
We ontvingen ook correcte inzendingen van Stijn Cambie, Frederic Broucke, Marc Peeters, en Toon Baeyens & Simon Van den Eynde. Bedankt voor jullie inzendingen!
Oplossing
De enige waarde van $n$ waarvoor Lander steeds alle schelpjes kan wegnemen, is $n=2$.
Voor $n=1$ kan hij duidelijk het rooster $\left[\begin{array}{cc}1&2\end{array} \right]$ nooit leegmaken.
Voor $n>2$ zullen we aantonen dat hij het rooster $\left[\begin{array}{cc} 1 & n-1 \end{array} \right]$ nooit kan leegmaken. Stel dat na een aantal stappen het rooster de vorm $\displaystyle \left[\begin{array}{cc} a & b \end{array} \right]$ heeft. Beschouw dan het verschil $a-b$. Als we uit beide vakjes $n$ schelpjes wegnemen blijft dit verschil hetzelfde. Als we het eerste vakje maal $n$ doen, dan wordt dit verschil $na-b$, dus het verschil vermeerdert met $(n-1)\,a$. Analoog, als we het tweede vakje maal $n$ doen, vermindert het verschil met $(n-1)\,b$.
We zien dus dat het verschil tussen de twee vakjes steeds hetzelfde blijft modulo $n-1$. Echter, in onze beginsituatie is dit verschil $1\bmod{n-1}$, en in een leeg rooster is het $0\bmod{n-1}$. Dus we kunnen nooit een leeg rooster bekomen.
Voor $n=2$ geven we een algoritme waarmee we elk rooster kunnen leegmaken. Met volgende procedure kunnen we een willekeurige rij omzetten in een rij van nullen. Trek eerst herhaaldelijk 2 af van alle elementen van de rij tot er ergens op de rij een 1 of een 2 staat. Daarna herhalen we volgende drie stappen:
- Voor elke 1 in de rij, verdubbel de overeenkomstige kolom.
- Voor elke 2 in de rij (zo is er minstens één), verdubbel de overeenkomstige kolom.
- Verminder de rij met 2.
Telkens we deze 3 stappen uitvoeren, verdwijnen er schelpjes uit de vakjes van de rij met meer dan 2 schelpjes. Dus na een aantal keer zal de rij enkel nog vakjes met 1 of 2 schelpjes bevatten. Als we daar dan nog eens stappen 1 en 3 op toepassen, krijgen we een nulrij.
Voor een willekeurig rooster kunnen we bovenstaande procedure achtereenvolgens op alle rijen toepassen (merk op dat dit steeds kan, zonder dat er in andere rijen nullen bijkomen of verdwijnen), en als we dat doen krijgen we een leeg rooster.