WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Verplaatsing

Ik moet een bewijs geven voor het volgende probleem:

Op hoeveel manieren kunnen de leerlingen in een 2×n klas (2 rijen en n kolommen) ieder een stoel in een rij of in een kolom opschuiven?

Door wat mogelijkheden te tekenen, die ik hier niet geplaatst krijg, kwam ik bij:

(n staat voor het aantal kolommen)

n=1 -- 1 mogelijkheid op van plaats te wisselen (rij-en wisselen)
n=2 -- 4 mogelijkheden (rondje de ene kant op, rondje andere kant op, rij-en wisselen, kolommen wisselen)
n=3 -- 9
n=4 -- 25
n=5 -- 64

Mijn vermoeden is dat de volgende rij bij het aantal mogelijkheden hoort:

1², 2², 3², 5², 8², 13²,...

Dus de rij van Fibonacci in het kwadraat.
Maar nu het bewijs....?
Anne v
Student hbo - zondag 12 november 2006

Antwoord

Mooie vraag...

Je kan het beste proberen om een recursieve formule op te stellen: noem g(n) het gevraagde aantal voor een 2·n klas, probeer g(n) uit te drukken in functie van de voorgaande (g(n-1),g(n-2),...)

Nu, laten we kijken naar de eerste rij. Ofwel wisselen die onderling, dus
a b
wordt omgezet in
b a
en de rijen daarachter doen wat ze willen, dat kan op g(n-1) manieren.

Dan: de eerste twee rijen. Zoals je zelf opmerkte: een 2·2-klas kan op vier manieren gewisseld worden, één daarvan heb je echter in het vorige geval al besproken. Dus wat je hier nog mag doen is:
a b
c d
omzetten in
c a
d b
of:
b d
a c
of:
c d
a b

De n-2 rijen daarachter kunnen weer op g(n-2) manieren wisselen, dus dit geeft ons 3·g(n-2) manieren.

Next: stel dat de eerste drie rijen onderling verwisselen, maar wel op een zodanige manier dat je niet in één van de vorige gevallen terechtkomt. Je zal zien dat dit slechts op twee manieren kan:
a b
c d
e f
wordt omgezet in ofwel
b d
a f
c e
(tegenwijzerzindraai), ofwel
c a
e b
f d
(wijzerzindraai).
Weer mogen de n-3 rijen daarachter naar hartelust zich verzetten, wat ze op g(n-3) manieren kunnen. Dit geeft dus een bijdrage van 2·g(n-3).

Voor de eerste 4 rijen: idem (2·g(n-4)), de eerste 5, 6,..., n-1: idem. Tel daar nog bij de twee gevallen die je krijgt door de hele klas in (tegen-)wijzerzin te draaien.

Conclusie: g(n)=g(n-1)+3·g(n-2)+2·g(n-3)+2·g(n-4)+...+2·g(1)+2·g(0)
waarbij we afspreken dat g(0)=1.

Deze formule werkt voor n minstens 3, en ze geeft inderdaad de waarden die jij geeft.

Maar nu ben je er nog niet: je moet nu proberen te bewijzen dat bovenstaande formule voor g(n) inderdaad het kwadraat van de Fibonaccirij is. Dat moet je met inductie doen, en ik zou verwijzen naar deze site, waar je formule nummer 28 kan gebruiken. Na nog wat termen goed groeperen en zo, hier en daar een kwadraatje herkennen, kom je dan tot het juiste besluit. Succes ermee, als je er niet uitkomt reageer je maar.

Groeten,
Christophe.

Christophe

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zaterdag 18 november 2006