spel met rij
Opgave - NWO 2008 vraag 5
We spelen een spel met een rij van $2008$ gehele getallen. Alle getallen in de rij zijn groter dan of gelijk aan $0$. Een zet bestaat uit het kiezen van een getal b uit de rij, waarvan de twee buurgetallen $a$ en $c$ positief (dus groter dan $0$) zijn. We vervangen dan $a$, $b$ en $c$ door respectievelijk $a-1$, $b+7$ en $c-1$. Het eerste en het laatste getal van de rij mogen niet gekozen worden omdat ze maar één buur hebben. Als we geen getal $b$ meer kunnen vinden waarvan beide buurgetallen positief zijn, kunnen we geen zet meer doen en stopt het spel. Bewijs dat het spel altijd op een gegeven moment stopt, met welke rij getallen we ook beginnen en welke zetten we ook doen.
- login om te reageren
Oplossing
Noem de getallen achtereenvolgens $a_0 ,a_1 ,a_2 ,...,a_{2008}$
We definiëren nu de "overlevingswaarde" van de rij:
$a_0 +7a_1 +...+7^ka_k+...+7^{2008} a_{2008}$
Nu neemt de "overlevingswaarde" van de rij bij elke stap af, met een waarde minimum gelijk aan $7^{k-1}$ als we $(a_{k-1},a_k,a_{k+1})$ kiezen (waarbij $2008 > k > 0$, zodat het met minstens 1 per keer afneemt), dus moet de overlevingswaarde wel ooit kleiner worden dan 0 als dit proces oneindig lang door zou gaan (de startwaarde is een bepaalde natuurlijke waarde).
Maar dat kan niet omdat alle $a_i \ge 0$ na iedere stap. Want elke $a_i$ kan slechts met juist 1 per stap afnemen en als deze 0 wordt (wat dus noodzakelijk gebeurt als we $a_i$ negatief willen maken) kunnen we zijn buur niet meer kiezen zodat $a_i$ niet meer kan afnemen.
Dus moet het spel wel stoppen opdat de overlevingswaarde positief zou blijven.