De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Verplaatsing

Ik moet een bewijs geven voor het volgende probleem:

Op hoeveel manieren kunnen de leerlingen in een 2n 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:

12, 22, 32, 52, 82, 132,...

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 2n 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 22-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 3g(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 2g(n-3).

Voor de eerste 4 rijen: idem (2g(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)+3g(n-2)+2g(n-3)+2g(n-4)+...+2g(1)+2g(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



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3