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

Combinaties

30 schoenen (15 rechtse, 15 linkse) staan in willekeurige volgorde op een rij. Bewijs dat, in welke volgorde de schoenen ook staan, er in de rij altijd een rij van 10 opeenvolgende schoenen is die evenveel linkse als rechtse schoenen bevat.

$\rightarrow$ ik heb a.d.h.v een herhalingspermutatie van 15, 15 uit de 30 berekend (=30!/15!15!) dat er 155117520 mogelijkheden zijn maar ik vind maar niet hoe ik kan aantonen dat er altijd een rij van 10 is met evenveel rechtse als linkse

Nathal
3de graad ASO - woensdag 20 november 2013

Antwoord

We nummeren de plaatsen $1$ tot en met $30$ en we noteren met $f(n)$ het aantal linkerschoenen onder de schoenen op posities $n$, $n+1$, $\ldots$, $n+9$. Merk nu op dat $f(1)+f(11)+f(21)=15$: de intervallen $[1,10]$, $[11,20]$ en $[21,30]$ zijn disjunct en bevatten alle schoenen.
Als $f(1)$ of $f(11)$ of $f(21)$ gelijk is aan $5$ zijn we klaar; zo niet dan is zeker een van de drie kleiner dan $5$ en een is er groter dan $5$, Bijvoorbeeld $f(1)\prec5\prec f(11)$.
Vervolgens geldt dat voor elke $n$ de waarden $f(n)$ en $f(n+1)$ hooguit $1$ verschillen: als op posities $n$ en $n+10$ dezelfde schoenen staan (LL of RR) is het verschil $0$; als er verschillende schoenen staan (LR of RL) is het verschil $\pm1$.
Nu volgt dat $f(n)=5$ voor een $n$ tussen $1$ en $11$.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 20 november 2013
 Re: Combinaties 


klein |  normaal |  groot

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

©2001-2019 WisFaq - versie IIb