Trominoer
Legg merke til hvordan Roger bruker induksjonshypotesen i induksjonssteget. Induksjonshypotesen her er at et $2^n \times 2^n$-rutenett der en rute er fjernet kan dekkes av trominobrikker. Fra dette følger det at et
$2^{n+1} \times 2^{n+1}$-rutenett der en rute er fjernet kan dekkes av trominobrikker, fordi:
- Et slikt rutenett vil bestå av fire $2^n \times 2^n$-rutenett der en av disse $2^n \times 2^n$-rutenettene mangler en rute.
- $2^n \times 2^n$-rutenettet som mangler en rute vet vi at vi kan dekke fullstendig med trominobrikker (fra induksjonshypotesen).
- Vi kan fjerne nøyaktig en rute fra hver av de tre andre $2^n \times 2^n$-rutenettene ved å legge en tromino i midten slik Roger viser i videoen. (Dette er selve «trikset» som lar oss bruke induksjonshypotesen.)
- Nå har vi tre $2^n \times 2^n$-rutenett der det er fjernet en rute i hver av dem, så nå har vi kommet til et punkt der vi kan bruke induksjonshypotesen direkte. Vi vet jo fra induksjonshypotesen at vi kan dekke et $2^n \times 2^n$-rutenett der en rute mangler med trominoer, så vi vet at vi kan dekke hver av disse tre $2^n \times 2^n$-rutenettene der en rute mangler med trominobrikker.