Hoe bewijs ik dat er een eindig aantal oplossingen is. Dus je telt 2009 breuken bij elkaar op en de som is 1. Al deze breuken hebben de teller 1 en als noemer een geheel getal.
Matt V
Student hbo - donderdag 22 oktober 2009
Antwoord
Beste Matt,
Niet alle noemers kunnen groter zijn dan 2009. Als alle noemers 2009 zijn heb je een oplossing. Andere oplossingen hebben dus bijvoorbeeld k (k2009) noemers kleiner dan 2009. Zowel de keuze van het getal k als de keuze van de noemers van die k breuken is eindig. Bij elke keuze waarvoor de som van die k breuken kleiner dan 1 is blijft een rest over van a/b. Er zijn dan nog 2009-k breuken over. Die kunnen op hun beurt niet allemaal een noemer hebben die groter is dan b·(n-k)/a (is niet perse een geheel getal). Kies hievoor weer een niew aantal breuken (k2)die een noemer hebben kleiner dan b·(n-k)/a. Ook dit aantal is weer eindig. Ga zo door tot er geen keuzemogelijkheden meer zijn.
Een ander bewijs gebruikt een bovengrens van de grootste noemer. Als daarvoor een bovengrens bestaat is het aantal mogelijkheden beperkt. Stel de rij breuken op volgens het "greedy" algoritme, waarbij je de grootst mogelijke breuk kiest zodat de som kleiner blijft dan 1 (Sylvester sequence: zie slaone A000058: http://oeis.org/A000058) Noemers worden : 2,3,7,43,1807,.... Deze rij van noemers voldoet aan de vergelijking u(n+1)=u(n)2-u(n)+1, met u(1)=2. u(2009)-1 is dan een bovengrens. Je kan namelijk de laatste noemer niet groter maken zonder dat je een van de andere noemers kleiner moet maken, wat niet kan. Deze laatste conclusie is echter niet geheel vanzelfspreken, omdat je wel nog een andere noemer groter zou kunnen maken en een latere uit de rij kleiner. Toch zal blijken dat je zo nooit kan compenseren voor de toename van de noemer u(2009).
Bedenk zelf welk bewijs je het mooiste vindt, vooral ook het meest overtuigend!
(Deze vraag werd beanwoord in samenspraak met Anneke.)
2009) noemers kleiner dan 2009.