Winnaar breinbreker november-december

Breinbreker

De winnaar van de breinbreker van november-december is Steven Van Overberghe. We belonen dit met een abonnement op het wiskundetijdschrift Pythagoras. We ontvingen ook een correcte inzending van Bart Van Gasse. Bedankt!
Oplossing:
In een rechthoekig rooster met een oneven aantal munten is het steeds mogelijk om ze allemaal te nemen (dus als één van de zijden oneven lengte heeft, zeg z.v.v.a. de lengte). Dat kan op de volgende manier (zie de bijgevoegde figuren):

  1. Begin in de linkeronderhoek en neem de hele onderste rij.
  2. Neem van de tweede rij de munten op de oneven posities (tellend van links bijvoorbeeld)
  3. Neem alle tussenliggende munten, zodat dus nu de eerste twee rijen volledig zijn genomen.
  4. Herhaal tot alle rijen zijn genomen

Dit werkt omdat in stap 2 zowel de eerste als de laatste munt van de rij worden genomen, en elke munt in stap 3 dus 3 buren heeft die al genomen zijn.

Voor een rooster met een even aantal munten (dus lengte L en hoogte H even) kan je als volgt tewerk gaan:

  1. Neem het volledige L-1 op H rooster, dat bestaat uit het volledige rooster zonder de meest rechtse kolom, op de manier zoals hierboven beschreven.
  2. Neem H/2 munten van de rechtse kolom, startend in de rechterbovenhoek door telkens één munt tussen te laten (cfr. punt 2 hierboven)
  3. Neem nu alle tussenliggende munten.
  4. Alleen de munt rechtsonder blijft over.

Nu kan je aantonen dat dat ook het beste is wat je kan doen op een even bij even rooster. Beschouw daarvoor het rooster van munten als een soort graaf met n toppen en bogen tussen elk paar aangrenzende munten. Stel dat v_1, v_2, ..., v_n een nummering van de toppen is die een geldige oplossing vormt (dat wil zeggen: neem de munten precies in die volgorde zoals de toppen opgelijst staan). Teken nu vanuit elke top v een pijl naar alle aangrenzende toppen die eerder waren gekozen dan v (en die dus een lager nummer hebben). Dan komen er in elke top, behalve v_1, een oneven aantal pijlen toe (per definitie). Aangezien er naast v_1 een oneven aantal toppen zijn, is het aantal pijlen dus een som van oneven lengte van allemaal oneven getallen. Het aantal pijlen moet dus oneven zijn (want geen enkele pijl wordt dubbel geteld). Anderzijds is elke boog in de roostergraaf bedekt door precies één pijl: één van beide toppen moet eerder zijn gekozen dan de ander. Het aantal bogen in de volledige roostergraaf is echter even; een contradictie!

Karel kan dus ten hoogste €9999 verdienen.