Kapittel 11 – Matematisk induksjon / Trominoer

Trominoer

Hva syns du om denne videoen?
(Én stjerne er dårligst, tre stjerner er middels og fem stjerner er best.)
(Hvordan kan denne videoen bli bedre?)

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.