kijk niet zo zuur, maar denk basisch

Opgave - BxMO 2011 dag 1 vraag 4

Abby en Brian spelen een spel. Eerst kiezen ze een geheel getal $N > 1$.
Daarna schrijven ze om beurten een getal op een bord.
Abby begint met het opschrijven van $1.$
Vanaf dat moment, wanneer $1$ van hen $n$ opschrijft, moet de ander $n + 1$ of $2n$ opschrijven, onder de voorwaarde dat dat getal niet groter is dan $N.$
Degene die $N$ opschrijft wint het spel.
$(a)$ Bepaal welke speler een winnende strategie heeft als $N = 2011.$
$(b)$ Vind het aantal gehele getallen $1\le N \le 2011$ waarvoor Brian een winnende strategie heeft.

Oplossing

$(a)$ Indien Abby steeds als getal $n+1$ opschrijft, zal ze steeds een oneven getal opschrijven. Dit heeft als gevolg dat Brian enkel even getallen kan opschrijven, waardoor bij $N=2011$ Abby dus enkel $n+1$ moet opschrijven om de winst te garanderen.

$(b)$ Uit $(a)$ volgt dat Brian geen winst kan garanderen indien $N$ oneven is. We bekijken nu dus enkel nog de even getallen.

Deze even getallen kunnen we opsplitsen in 2 categorieën: de viervouden $(1)$ en de viervouden $+ 2$ $(2)$.

$(1)$ We stellen $N=4m$. Als iemand $2m$ noteert, kan de tegenpartij winst garanderen door te verdubbelen. Indien iemand een element van ${2m-1,2m-2...,m+1}$ noteert, kan de tegenpartij winnen door te verdubbelen, waarna het verdere verloop vastligt, omdat er nog maar één zet kan gebeuren (herhaaldelijk). In dat geval wint deze zelfde tegenpartij.

Als Brian Abby dus een getal uit ${2m,2m-1,...,m+1}$ kan laten noteren, kan hij zijn overwinning garanderen. Dit is steeds het geval wanneer hijzelf $m$ opschrijft (gezien beide mogelijke zetten die erop volgen dan steeds binnen de verzameling liggen). Indien $m$ niet door Brian genoteerd wordt, kan hij zijn winst niet garanderen, gezien Abby dan de overwinning kan grijpen met de juiste strategie. Brian kan dus winnen bij $N=4m$ a.s.a. hij kan winnen bij $N=m$.

$(2)$ We stellen $N=4m + 2$. Als iemand $2m+1$ noteert, kan de tegenpartij winst garanderen door te verdubbelen. Indien iemand een element van ${2m,2m-1,...,m+1}$ noteert, kan de tegenpartij verdubbelen, waarna het verloop van het spel opnieuw vastligt, gezien er nog maar één zet kan gedaan worden (herhaaldelijk). Opnieuw merken we dus op dat Brian kan verzekeren dat Abby een getal uit de verkregen verzameling noteert als en slechts als hij zelf $m$ opschrijft.

Indien we de getallen van $1$ tot $4$ beschouwen, zien we dat $2$ het enige van deze getallen is dat zeker genoteerd wordt door Brian.

We gebruiken dus onze eerdere bevindingen, nl. dat als bij $N=m$ Brian winst kan garanderen, hij dat ook kan bij $N=4m$ en $N=4m + 2$ om de andere mogelijkheden te tellen en houden daarbij rekening met de bovengrens.

$2$
$8,10$
$N_1,N_2,N_3,42$
$N_1,...,N_7,170$
$N_1,...,N_{15},682$

Als we nog meer oplossingen zouden hebben, zouden deze allemaal groter zijn dan $2*4^5=2048$, waardoor we ze niet mee moeten tellen.

Zo zien we dus dat er $1+2+4+8+16 = 31$ waarden van $N$ zijn waarvoor Brian een winnende strategie kan hebben.