Submitted by jonas on
We hebben jullie lang in spanning gehouden, maar uiteindelijk is de winnaar van de breinbreker van september-oktober bekend. Het antwoord op het probleem is dat de fotograaf $2^{(m-1)(n-1)}$ foto's kan nemen. De jury maakte een selectie van de mooiste oplossingen en dan heeft een onschuldige hand Jeroen Denoo als winnaar getrokken. Als prijs ontvangt Jeroen een jaarabonnement op het tijdschrift Pythagoras. Proficiat en veel leesplezier!
We kijken terug op een succesvolle eerste breinbreker, want we kregen ook nog juiste inzendingen van Igor Voulis, Eva Busseniers, Glenn Mangelinckx, Thomas Cnops, Mathias Jolie, Sofian De Clercq (twee juiste oplossingen) en Thomas Present.
Oplossing van Jeroen
We vertrekken door eerst random alle lichten aan of uit te zetten in het hele gebouw behalve een verdieping en een kolom (verder voor het gemak de bovenste verdieping en de rechtse kolom genoemd).
In alle verdiepingen behalve de bovenste kunnen we nu tellen hoeveel lichten al branden. Naargelang dit even of oneven is kunnen weten we of het licht moet branden in het raam in de rechtse kolom op die verdieping.
We doen nu hetzelfde voor alle kolommen. Hiermee kunnen we alle lichten in de bovenste verdieping bepalen. We weten nu zeker dat er een even aantal lichten brandt in elke kolom en op alle verdiepingen behalve de bovenste.
Aangezien in elke kolom een even aantal lichten brandt, brandt er in het hele gebouw ook een even aantal lichten.
Doordat in totaal een even aantal lichten brandt en aangezien op elke verdieping behalve de bovenste een even aantal lichten brandt, zal ook op de bovenste verdieping een even aantal lichten branden.
Vertrekkend vanuit het random $(m-1)\times (n-1)$ rooster is er dus precies één manier om de andere lichten te kiezen zodat aan alle voorwaarden voldaan is.
Het aantal mogelijkheden is dus het aantal mogelijkheden om random $(m-1)\times (n-1)$ roosters te vullen oftewel $2^{(m-1)(n-1)}$.