legale bewegingen
Opgave - APMC 1981 dag 2 vraag 1
$n$ symbolen worden in een cirkel geschikt en ieder symbool is ofwel 1 ofwel 0. Een legale beweging wordt gedefinieerd als het veranderen van een 1 in een 0, en de beide buren ook te veranderen (eventueel van 0 naar 1). Bijvoorbeeld kan je $...01101...$ veranderen naar $...10001...$. Als de beginsituatie precies één 1 heeft, voor welke waarden van $n$ kan je dan alle symbolen in een 0 omzetten met een eindig aantal legale bewegingen.
- login om te reageren
Oplossing
Noem de symbolen in volgorde $a_1$ tot $a_n$, waarbij $a_1=1$ en alle andere symbolen 0.
- We bekijken nu eerst alle $n=3k$ met $k$ een natuurlijk getal.
We bepalen de verzamelingen $A$ en $B$ als volgt:
$A = \{a_{3i}|i \in \mathbb{N}\}$
$B = \{a_{3j+1}|j \in \mathbb{N}\}$
De som van alle elementen uit $A$ en $B$ blijft dan altijd oneven, (ze is invariant modulo 2)
want elke keer je een beweging uitvoert verander je juist $1$ element van zowel $A$ als $B$, als je alle gevallen nakijkt zie je inderdaad dat de pariteit blijft behouden.
Je kunt er dus niet voor zorgen dat dat alle symbolen $0$ worden.
- Nu kijken we naar $n=3k+1$
We veranderen de eerste $1$ in de reeks $...000101...$ en daarna
$...001011...$, $...010111...$, $...101111...$,
tot we nog maar één $0$ over hebben. Dan zijn er $3k$ enen en kan het dus opgelost worden (door alle groepjes enen samen te nemen en $k$ bewegingen uit te voeren).
- En als laatste naar $n=3k+2$
We beginnen op dezelfde manier als hierboven, tot we nog maar één $0$ over hebben. Dan
$...1110111...$, $...1111001...$
Nu hebben we nog $3k$ enen en kan het dus weer opgelost worden.