Trap verven: antwoord uit het boek

Antwoord bij opgave 84

1597

Uitleg (niet uit boek)

Niet te gauw opgeven!

Er zijn meestal vele manieren om problemen op te lossen. Hieronder werken we één aanpak uit. Het kan en mag best anders.

Tellingen voor veel minder treden

Trap met 1 trede
Manier	Kleuring
1
2

Trap met 2 treden
Manier	Kleuring
1
2
3

Trap met 3 treden
Manier	Kleuring
1
2
3
4
5

Trap met 4 treden
Manier	Kleuring
1
2
3
4
5
6
7
8

Tabel maken

Aantal treden	Aantal kleuringen
1	2
2	3
3	5
4	8
5	?
...	...

Zoek maar eens naar een patroon in bovenstaande tabel.

Patroon herkennen en uitbuiten

Vanaf de derde rij is elk getal in de tweede kolom de som van de twee getallen erboven (ook bekend als de rij van Fibonacci). Nu kun je de tabel afmaken:

Aantal treden	Aantal kleuringen
1	2
2	3
3	5
4	8
5	13
6	21
7	34
8	55
9	89
10	144
11	233
12	377
13	610
14	987
15	1597

Het patroon bergrijpen

Dit patroon is als volgt te begrijpen.

Tel ook eens afzonderlijk het aantal kleuringen dat met een gele trede begint en dat met een blauwe trede begint:

Aantal treden	Aantal kleuringen	Beginnend met blauw	Beginnend met geel
1	2	1	1
2	3	1	2
3	5	2	3
4	8	3	5
5	13	5	8
6	21	8	13
7	34	13	21
8	55	21	34
9	89	34	55
10	144	55	89
11	233	89	144
12	377	144	233
13	610	233	377
14	987	377	610
15	1597	610	987

Laat A(n) het aantal kleuringen zijn bij n treden. Dan zijn A(1) en A(2) eenvoudig te bepalen. Voor n>1 geldt

A(n) = A(n-2) + A(n-1)

Waarom? Omdat een kleuring

hetzij met een blauwe trede begint, en de eerstvolgende trede mag dan niet blauw zijn maar moet geel zijn; waarna de resterende n-2 treden volgens dezelfde eis als van de opgave geverfd worden, wat dan op A(n-2) manieren kan.
hetzij met een gele trede begint, en de resterende n-1 treden volgens dezelfde eis als de opgave geverfd worden, wat dan op A(n-1) manieren kan;

Je kan zelfs stellen dat A(0)=1, net als een leeg product (zonder factoren) 1 is (denk aan 10⁰=1).

Nog meer ontdekkingen

Als je wat moeite neemt kun je bij zo'n opgave zelf nog veel meer wiskunde ontdekken.

Door bij het kleuren niet te beginnen met de eerste trede, maar bij een middelste trede, ontdek je de volgende twee formules:

Oneven aantal treden: A(2n+1) = A(n-1)² + A(n)²
Even aantal treden: A(2n) = A(n-1) A(n-2) + A(n) A(n-1) = A(n-1) ( 2A(n) - A(n-1) )

Hiermee kun je A(15) uitrekenen door alleen maar A(0) en A(1) A(2) en A(3), A(6) en A(7), uit te rekenen. Het is dan een klein kunstje om bijvoorbeeld A(255) te bepalen, door ook nog A(14), A(30) en A(31), A(62) en A(63), A(126) en A(127) uit te rekenen.