Wiskundemeisjes

Plaatjesbewijs

Ik houd van plaatjesbewijzen: plaatjes die zo duidelijk het idee van het bewijs weergeven dat er nauwelijks of geen woorden meer nodig zijn. Op deze lijst op mathoverflow.net staan er een heleboel. Ik licht er voor jullie één mooi idee uit.

Een vierkant van 8x8 kun je precies bedekken met dominosteentjes van 1x2 veldjes. Kan dat nog steeds als je het veldje in de linkerbovenhoek en het veldje in de rechteronderhoek verwijdert? Het antwoord is nee, en het argument is als volgt (als spoiler voor de mensen die er eerst zelf over willen nadenken). Stel je het 8x8-vierkant voor als een schaakbord. Hoe je een dominosteentje ook op het schaakbord legt zodat het precies twee vakjes bedekt, je bedekt altijd een wit én een zwart vakje.

De twee vakjes die zijn verwijderd van het schaakbord hadden allebei dezelfde kleur (wit), dus nu zijn er meer zwarte dan witte vakjes over. Als het schaakbord nog gevuld zou kunnen worden met dominosteentjes, dan zouden er evenveel witte als zwarte velden bedekt zijn, maar er zijn niet evenveel witte als zwarte velden. Dus dat kan niet.

Een opvolgende vraag is nu: als je nou niet twee vakjes van dezelfde kleur weghaalt, maar willekeurig één wit en één zwart vakje, kun je het bord dan wèl altijd vullen met dominosteentjes? Het antwoord ligt niet meteen voor de hand, maar onderstaand plaatje laat zien dat dat inderdaad kan. Dit bewijs is van Ralph E. Gomory, en het plaatje komt van deze site.

5 reacties op “Plaatjesbewijs”

1. Jan Paul:
   vrijdag 12 maart 2010 om 10:54

   Leuk!

2. johan:
   vrijdag 12 maart 2010 om 13:42

   Zo bestaat er ook een bewijs over het al dan niet mogelijk zijn van een paardensprong ronde op een 4xN schaakbord.

3. johan:
   zaterdag 13 maart 2010 om 17:32

   Staat alvast iets van op wikipedia: http://en.wikipedia.org/wiki/Knight%27s_tour

4. Joke:
   dinsdag 16 maart 2010 om 14:03

   Heb het eerste probleem op het bord gehad en bij elke klas waren er al gelijk één of twee leerlingen die het zagen. Leuk probleem voor ze!

5. HJ:
   zondag 28 maart 2010 om 20:54

   Op zoek naar nieuws over Perelman kwam ik op de site van het Clay Mathematics Institute een verhaal tegen over tilings: betegelingen in allerlei varianten. Eén variant is net als hier het leggen van domino's op een schaakbord, eventueel met vakjes verwijderd. De algemene vraag of je een oplossing kan vinden is in het domino geval een speciale toepassing van de huwelijksstelling van Hall. Grappig!
   http://www.claymath.org/library/senior_scholars/stanley_ardila_tilings.pdf (Hoofdstuk 5)

Plaats een reactie