Submitted by jonas on
Oef, de breinbreker van januari-februari was een harde noot om te kraken en ook onze jury had wel wat werk om de ingezonden oplossingen (waarbij de grenzen van de deadline werden afgetast) te verwerken. Maar uiteindelijk is er een winnaar gekozen, en deze eer gaat naar Igor Voulis!
Zoals altijd ontvangt de winnaar een jaarabonnement op het tijdschrift Pythagoras en op het tijdschrijft Wiskunde & Onderwijs.
We kregen ook nog correcte inzendingen van Mathias Jolie, Dries Maertens, Yannick Neyt en Jeroen Demeyer (lees oplossing). Bedankt voor jullie inzending en veel succes met de breinbeker van maart-april.
Oplossing Igor
Igor stuurde zijn oplossing in een mooi pdf formaat door, je kan deze lezen door op -->dit<-- te klikken.
Oplossing van de jury
We bewijzen de bewering via inductie op het aantal lichtjes $n$. Het geval $n=1,2$ is triviaal, zij dus $n>2$.
We weten dan wegens inductiehypothese dat als we één lichtje weglaten (niet bekijken), we de overige lichtjes kunnen switchen (i.e. aan- of uitdoen alle lichtjes). We zullen in het vervolg noteren: als $x$ lichtje, dan kan $x'=V-x$ switchen, waarbij $V$ de verzameling van alle lichtjes is.
We mogen veronderstellen dat voor elk lichtje $y$ geldt dat als je $y'$ switcht, dan $y$ onveranderd blijft. Als dit niet zo is, neem dan zo'n lichtje $y$, steek $y'$ aan en vermits dan ook $y$ licht geeft is het bewijs afgelopen.
Neem vervolgens twee lichtjes, noem $x$ en $y$. Door eerst $x'$ en daarna $y'$ te switchen, vinden we dat $x$ en $y$ branden, maar al de andere lichtjes uit zijn. We kunnen dus in de de kerstboom twee willekeurige lichtjes switchen zonder de rest van stand te veranderen.
We onderscheiden nu twee gevallen. Als de kerstboom een even aantal lichtjes heeft, dan kan je paarsgewijs alle lichtjes van de graaf aansteken.
Als de graaf een oneven aantal lichtjes heeft, dan heb je zeker één lichtje (noem $x$) die een even aantal buren heeft*. Steek dan paarsgewijs alle buren van $x$ aan en steek dan $x$ aan. Al zijn buren gaan terug uit, dus enkel $x$ geeft licht. Om te eindigen steek je $x'$ aan.
* Als de kerstboom $m$ kabels (verbinding tussen twee lichtjes) en $n$ lichtjes heeft, dan geeft een dubbele telling van de koppels $(l,k)$, met lichtje $l$ op kabel $k$, dat $\sum_i d_i = 2m$, waarbij $d_i$ de graad (het aantal kabels dat in het lichtje vertrekken) van lichtje $i$. Dus als je een oneven aantal lichtjes hebt, moet je er een even $d_i$ tussen zitten.