winnen door bureaucratische problemen te vermijden

Opgave - BxMO 2017 dag 1 vraag 2

Zij $n \geq 2$ een geheel getal. Alice en Bob spelen een spel dat gaat over een land bestaande uit $n$ eilanden. Precies twee van deze $n$ eilanden hebben een fabriek. In het begin is er nog geen enkele brug in het land. Alice en Bob moeten om beurten een brug bouwen tussen twee verschillende eilanden, en wel zodanig dat als er een brug wordt gebouwd tussen de eilanden $I_1$ en $I_2$, er geldt dat:

* $I_1$ en $I_2$ nog niet zijn verbonden door middel van een brug;
* minstens één van de twee eilanden $I_1$ en $I_2$ middels een aantal bruggen verbonden is met een eiland met een fabriek (of zelf een fabriek heeft). (Oftewel: je moet een fabriek kunnen bereiken om een brug te kunnen bouwen.)

Zodra een speler een brug bouwt die het mogelijk maakt om van de ene naar de andere fabriek te gaan, verliest deze speler het spel. (Oftewel: als je beide fabrieken kunt bereiken, krijg je bureaucratische problemen bij het bouwen van de brug.) Als Alice begint, bepaal dan (voor elke $n \geq 2$) wie een winnnende strategie heeft.
(Het is toegestaan om een brug te bouwen die over een andere brug heen gaat.)

Oplossing

Tijdens het spel worden de eilanden over twee verzamelingen verdeeld. De verzameling waarbij ze horen bepaald door welke fabriek de bruggen naar dat eiland zijn gebouwd. Laten we deze verzamelingen $V_1$ en $V_2$ noemen.

Een eiland kan slechts in 1 van de twee verzamelingen zitten en zal op het einde in één van de twee verzamelingen zitten (want de persoon kan zo nog minstens een zet doen). (1) Er kunnen geen bruggen gebouwd worden tussen twee eilanden van een verschillende verzameling. Als er maximaal een even aantal bruggen gebouwd worden wint Bob en bij een oneven aantal wint Alice.

Het maximaal aantal bruggen $B$ is $\frac{n(n-1)}2$ maar door (1) moeten we daar de bruggen tussen eilanden van een verschillende verzameling van aftrekken: $B=\frac{n(n-1)}2-|V_1||V_2|$

Als dit aantal even is heeft Bob een winnende strategie anders heeft Alice er een. We onderscheiden enkele gevallen.

Geval 1 $n \equiv 1 \mod 4$:
Hierdoor is $n = |V_1|+|V_2|$ oneven en dus is $|V_1||V_2|$ even. ook $\frac{n(n-1)}2$ is even want $n(n-1)\equiv1(1-1)\equiv0\mod4$. Dus is $B$ even en wint Bob altijd.

Geval 2 $n \equiv 0, 2 \mod 4$:

Bob kan nu winnen door telkens dezelfde zet als Alice te doen maar met de andere fabriek.
Na elke zet van Alice zorgt Bob ervoor dat de graaf van beide fabrieken hetzelfde is.
Dat dit mogelijk is, kan gezien worden op de volgende manier:
verdeel de $n$ eilanden in twee groepen van grootte $\frac n2$, waarbij de twee eilanden met een fabriek in een verschillende verzameling zit.
Construeer een bijectie $m$ tussen de twee groepen, of equivalent verdelen we de $n$ eilanden in $\frac n2$ paren, waarbij de twee eilanden met een fabriek in hetzelfde paar zitten, i.e. op elkaar worden afgebeeld door $m$.
Wanneer Alice eilanden $I_1$ en $I_2$ verbindt, verbindt Bob $m(I_1)$ en $m(I_2).$
Inductief kan men dan inzien dat $I_1$ niet gelijk kon zijn aan $m(I_2)$ en dat na een beurt van Bob geldt dat

    Eilanden $I_1$ en $I_2$ zijn verbonden asa $m(I_1)$ en $m(I_2)$ verbonden zijn
    Eiland $I_1$ is verbonden via enkele bruggen met een eiland $X$ met een fabriek asa $m(I_1)$ verbonden is via enkele bruggen met $m(X)$.

Geval 3 $n \equiv 3 \mod 4$:
Hierdoor is $n = |V_1|+|V_2|$ oneven en dus is $|v_1||v_2|$ even. ook $\frac{n(n-1)}2$ is oneven want $n(n-1)\equiv3(3-1)\equiv2\mod4$. Dus is $B$ oneven en wint Alice altijd.

Besluit: Alice heeft enkel een winnende strategie als $n \equiv 3 \mod 4$ anders heeft Bob er een.