Poster 2009-2010

REKEN!

Kan je berekenen waarom je nooit een schaakbord, een rooster van 8x8 vakjes, volledig kan bedekken met L-vormige stukken?

Een 8x8 rooster bevat 64 vakjes. Aangezien 64 niet deelbaar is door 3, zal een schaakbord dus onmogelijk vol gepuzzeld kunnen worden.

Telt een rooster wél precies een drievoud vakjes, dan is het echter niet per se mogelijk om dat rooster met de L-vormige stukken vol te leggen. Denk maar aan een 1x3-rooster, of een 3x3-rooster. Dat het aantal vakjes een drievoud moet zijn, is dus een belangrijke voorwaarde.

PUZZEL!

Als je op één enkel vakje een pion zet, dan kan je de rest van het schaakbord wél vol puzzelen met L-vormige stukken!

Laten we één vakje weg, door er een pion op te zetten, dan blijven er 8x8-1=63 vakjes over. Misschien is het nu dus inderdaad mogelijk om de rest van het schaakbord wel vol te puzzelen, maar dat is nog niet helemaal zeker: het aantal vakjes moet wel een drievoud zijn, maar het is niet omdat het aantal vakjes een drievoud is, dat de puzzel kan gemaakt worden.

Met heel wat gepuzzel en veel geduld zal blijken dat het voor elke positie van de pion kan, maar uit een even pittige als interessante denkoefening zal zonder gepuzzel volgen dat het inderdaad steeds mogelijk is.

DENK!

Ook een 2x2-, 4x4-, 16x16- of 32x32-rooster kan je niet helemaal bedekken, maar kan je bedenken waarom het wel lukt op één vakje na?

Een 2x2 rooster kan je natuurlijk niet vol puzzelen met de L-vormige stukken: Het rooster bevat 4 vakjes en zo een tegel slechts 3, dus 1 tegel is te weinig en twee tegels zijn al te veel. Zetten we op één van de vakjes een pion, dan houden we precies de L-vorm over en kan het rooster op dat ene vakje na inderdaad betegeld worden.

Ook een 4x4-, 16x16-, 32x32- of zelfs 2^nx2^n-rooster kan niet worden vol gepuzzeld, want deze roosters tellen respectievelijk 16, 256, 1024 en 2^(2n) vakjes, alle zuivere tweemachten, bijgevolg niet deelbaar door 3. Net zoals bij het schaakbord is met veel naarstigheid te verifiëren dat deze roosters te betegelen zijn met L-vormige stukken, maar we kunnen dat ook op volgende manier beargumenteren.

BEWIJS...

We zullen geen formeel inductiebewijs geven, maar het argument op een intuïtieve manier schetsen.

We beginnen met het 4x4 rooster. Dit verdelen we in vier 2x2-roosters a, b, c en d. Het vierkant a bevat de pion, en kunnen we dus betegelen, van de rest is dat nog niet zo duidelijk... Leggen we nu een tegel op de hoek van a, zo dat deze precies 1 vakje van elk vierkant b, c en d bevat, dan blijft in b, c en d telkens de L-vorm over: De betegeling is mogelijk.

We maken ons rooster groter, een 8x8-rooster. Dit 8x8-rooster bestaat opnieuw uit 4 vierkanten A, B, C en D met telkens 4x4=16 vakjes. Het vakje A bevat de pion en kan dankzij het vorige paragraafje worden betegeld. Dat de andere vierkanten kunnen worden betegeld is opnieuw niet onmiddellijk duidelijk, maar we gebruiken dezelfde truc als hierboven: Eerst leggen we een tegel op de hoek van A, die één vakje van B, C en D bevat. Daardoor ontbreken de drie overblijvende 4x4-roosters B, C en D elk één vakje, en kunnen ze ook op de voorgaande manier worden betegeld.

Een groter rooster delen we op in vier kleinere stukken. Een van deze kleinere stukken bevat de pion en kan wegens voorgaande worden betegeld. In het midden van het grote rooster leggen we een tegel die van de overblijvende drie vierkanten telkens één vakje bevat. Nu tellen de drie overblijvende vierkanten één vakje minder en kunnen ook zij worden betegeld.

Hoe kan je dus een rooster dat 2^nx2^n vakjes bevat betegelen? Verdeel het rooster in 4 gelijke vierkanten, en het stuk dat de pion bevat opnieuw in vier vierkanten, en zo voort, tot je een 2x2-rooster met de pion overhoudt. In dit kleine rooster leg je een tegel, waarna je in het midden van het 4x4-rooster waartoe dit vierkant behoort een tegel legt... Eens het kwart van het rooster met de pion in afgewerkt, leg je een tegel in het midden van het grote rooster, en begint het puzzelen in elk van de drie andere vierkanten opnieuw, tot het ganse rooster vol ligt.