Rode en blauwe fiches
Opgave - BxMO 2014 vraag 2
Zij $k \geq 1$ een geheel getal. We beschouwen $4k$ fiches, waarvan er $2k$ rood zijn en $2k$ blauw. We kunnen een rijtje van deze $4k$ fiches veranderen in een ander rijtje door een zogenaamde zet, die bestaat uit het omwisselen van een aantal (mogelijk één) opeenvolgende rode fiches met een gelijk aantal opeenvolgende blauwe fiches. We kunnen bijvoorbeeld in één zet het rijtje $rbbbrrrb$ veranderen in $rrrbrbbb$, waarbij $r$ staat voor een rood fiche en $b$ voor een blauw fiche.
Bepaal het kleinste getal $n$ (als functie van $k$) zodanig dat, ongeacht met welk rijtje van deze $4k$ fiches we beginnen, we ten hoogste $n$ zetten nodig hebben om het rijtje te bereiken waarvan de eerste $2k$ fiches allemaal rood zijn.
- login om te reageren
Oplossing
Noem het minimale aantal zetten $n$ in functie van $k$ $f(k)$.
We zullen bewijzen dat $f(k)=k \forall k \in \mathbb{N}_0$. Dat doen we door eerst aan te tonen dat het altijd in $k$ zetten mogelijk is, en door vervolgens een rij te tonen waarbij minstens $k$ zetten moeten worden gebruikt.
Ten eerste: we zullen ons aan volgende strategie houden: we verdelen allereerst de $4k$ fiches in 2 groepen, één die bestaat uit de eerste $2k$ fiches van de rij, dit is groep 1. De andere, groep 2, bestaat uit de volgende $2k$ fiches van de rij. We noemen $r_1$ het aantal rode fiches in groep 1 en $b_1$ het aantal blauwe fiches in groep 1. Als nu $r_1 \geq b_1$ vervangen we één voor één alle blauwe fiches uit groep 1 door rode van groep 2. Dit zal precies $b_1$ zetten vragen. Als $r_1 = b_1$ zal dit precies $k$ zetten vragen, aangezien dan $b_1=k$. Als $r_1$<$b_1$, vervangen we alle rode elementen uit groep 1 door blauwe en vervolgens vervangen we groepen 1 en 2. Dit zal $r_1+1$ zetten nemen, maar omdat $r_1 $<$b_1$ en $r_1+b_1=2k$ en $r_1$ en $b_1$ geheel zijn, zal $r_1 +1 \leq k$. Dus het is mogelijk met maximaal $k$ zetten.
Ten tweede: beschouw de rij $brbrbrbr...br$.
Bekijk het aantal overgangen van kleur (paren opeenvolgende fiches met een verschillend kleur).
Wanneer we twee groepen van opeenvolgende fiches selecteren (een rode - en een blauwe groep), zijn er maximaal $4$ overgangen verbroken (op het begin- en eindpunt van elke groep).
Na de wissel van beide groepen fiches, zijn er dus maximaal $4$ overgangen minder dan in de toestand voor de wissel.
Omdat de rij $brbrbrbr...br$ $4k-1$ overgangen heeft en de rij $rr\ldots rbb \ldots b$ slechts $1$ overgang, moet het aantal overgangen met $4k-2$ worden verminderd.
Daarvoor hebben we minstens $\lceil \frac{4k-2}{k} \rceil=k$ zetten voor nodig.