Re: Tellen

Dit is een reactie op vraag 83168

Hallo,

Ik volg uw redenering, maar volgende zinnen zijn me nog niet duidelijk:

"Bereken voor elke i de rest, ri, die je krijgt als je si deelt door 12."
-- Waarom delen door 12?

"Je hebt 77 resten en maar 21 verschillende mogelijkheden."
-- Waarom 77 resten?
-- Waarom 21 verschillende mogelijkheden?

"Bijvoorbeeld, omdat 77/21 groter is dan drie zijn er i, j, k en l met ri=rj=rk=rl"
-- Waarom 4 gelijke intervallen?

"Met wat puzzelen en gebruik van het feit dat 77=3·21+14 kun je zo'n viertal vinden met i=14 en dan heeft (ten minste) één van die intervallen precies 21 inspecties."
-- De intervallen kunnen toch ook 20, 20, 20, 17 zijn?
-- Waarom i=14?

Gr.

Lau
Student hbo - dinsdag 1 november 2016

Antwoord

Die $12$ moet een $21$ zijn, dat heb ik verbeterd.
Er zijn $77$ getallen $s_i$, die geven elk een rest $r_i$ bij deling door $21$, dat geeft een rij van $77$ resten.
Een rest bij deling door $21$ kan zijn $0$, $1$, $\ldots$, $20$; dat zijn $21$ mogelijkheden.
Ik heb bij die $r_i$, $r_j$, $r_k$ en $r_l$ nog niets over gelijke intervallen gezegd; uit $r_j=r_i$ volgt dat $s_j-s_i$ een $21$-voud is en dat betekent dat op de dagen $i+1$ tot en met $j$ een $21$-voud aan inspecties heeft plaatsgevonden.
Je kunt voor elke rest $r$ de $i$s bij elkaar nemen waarvoor $r_i=r$, schrijf bijvoorbeeld $A_r=\{i:r_i=r\}$. Bij elkaar genomen bevatten de $A_r$s dus de getallen $1$ tot en met $77$; er zijn $21$ verzamelingen $A_r$ en omdat $3\cdot21$ kleiner is dan $77$ moet er een $A_r$ zijn met meer dan drie elementen.
Aan de andere kant: een $A_r$ kan niet meer dan zeven elementen hebben want als $i$<$j$ in $A_r$ dan geldt $s_j-s_i\ge21$, dus als $A_r$ acht elementen $i_1$ tot en met $i_8$ zou hebben dan zou $s_{i_8}\ge s_{i_1}+7\cdot21=s_{i_1}+147$ gelden, maar elke $s_i$ is niet groter dan $132$.
Nu begin het puzzelen:
als er een $A_r$ is met zeven elementen dan geldt zelfs $s_j-s_i=21$ voor elk tweetal buren $i$ en $j$ in $A_r$ (als er een keer $42$ of meer als verschil optreedt is de laatste $s_i$ weer groter dan $132$).
Als er geen $r$ is zo dat $A_r$ zeven elementen heeft bekijken we het geval dat een een $A_r$ is met zes elementen; dan mag het verschil één keer $42$ zijn en krijge je weer een $i$ en een $j$ met $s_j-s_i=21$.
Volgende geval: geen $A_r$ met zes elementen maar nog wel een met vijf.
Laatste geval: elke $A_r$ heeft niet meer dan vier elementen dan moeten er ten minste veertien zijn met precies vier elementen en dan is er een waarbij de onderlinge verschillen niet allemeel $42$ of meer kunnen zijn.
Wat $20$, $20$, $20$, $17$ betreft: dat lijken me intervallen tussen de $i$s in zo'n $A_r$, die posities zijn niet echt belangrijk voor dit verhaal, het gaat vooral om de verschillen tussen de $s_i$s.

Zie Wikipedia: Pigeonhole principle

kphart
woensdag 2 november 2016

©2001-2024 WisFaq