Het domino probleem (deel 3)
Als we één zwart veld willen verwijderen, dan is een bedekking snel gevonden. Zie het volgende plaatje voor een hint.
![](elfbijelf.gif)
We bekijken nu het probleem waarbij 3 velden worden verwijderd.
We zullen veel meer aantonen. Daardoor wordt het probleem minder star, zodat je gebruik kunt maken van volledige inductie.
We tonen aan dat je elk rechthoekig 2k+1 bij 2m+1 bord met k>0 en m>0 volledig kunt bedekken als je er 2 zwarte velden en 1 wit veld uit hebt verwijderd.
De bewering is juist voor k=1, m=1. Zie hiervoor de plaatjes
Bekijk nu een 2K+1 bij 2M+1 rechthoek met KM>1 en veronderstel dat de stelling al bewezen is voor kleinere rechthoeken.
Markeer langs de langste zijde twee stroken van breedte 2 aan beide uiteinden van de rechthoek (zie figuur).
Een van de uiteinden bevat 0 of maximaal 1 verwijderd veld, zeg uiteinde A.
Geval 1: A bevat geen verwijderde velden. Dan bevat de rechthoek zonder A 3 verwijderde velden
en volgens de inductieveronderstelling kan dat gebied volledig met domino's worden bedekt.
Dat geldt ook voor strook A zelf (stapeltje domino's van breedte 2).
Geval 2: A bevat 1 verwijderd veld. Stel het is veld X (zie tekening).
Als we in de rechthoek zonder strook A ook nog veld Z verwijderen, dan is volgens de inductieveronderstelling
die rechthoek zonder strook A en zonder de 3 verwijderde velden volledig met domino's te overdekken.
Bedek nu strook A volledig met horizontaal geplaatste domino's en schuif domino XY een plaats naar rechts.
We hebben dan onze bedekking gevonden met veld X verwijderd uit A.
Stel veld X was niet een wit, maar een zwart veld en veld Z was een van de verwijderde velden.
Dan bevat strook B 0 of maximaal 1 (wit) verwijderd veld. We moeten dan niet uitgaan van strook A maar van strook B.
Tot slot. Stel A bevat 1 verwijderd veld in de tweede kolom. Zeg het is veld U (zie tekening).
Verwijder nu even ook veld V. Dan kan de rechthoek zonder strook A en zonder de verwijderde velden volledig worden overdekt.
Zie dan in de laatste 2 plaatjes hoe veld V door veld U kan worden vervangen.
Hiermee zijn alle gevallen besproken en is het bewijs rond.