Pythagoras oktober 1997

Opgave 6

Voor ieder positief geheel getal n is f(n) het aantal manieren waarop het getal n kan worden voorgesteld als de som van machten van 2 met niet negatieve gehele exponenten. Twee van deze manieren die alleen in de volgorde verschillen worden als gelijk beschouwd. Zo is bijvoorbeeld f(4)=4 omdat het getal 4 op de volgende vier verschillende manieren kan worden voorgesteld als som van machten van 2: 4; ; en . Bewijs dat voor ieder geheel getal geldt:

Oplossing

Zij n=2k+1 een willekeurig geheel getal groter dan 1. Dan bevat elke representatie van n in de gegeven vorm een ``1''. Door die weg te laten vinden we een representatie voor 2k. Andersom, door een ``1'' toe te voegen aan een representatie voor 2k vinden we een representatie voor 2k+1. Er geldt dus:

Verder, als n=2k een even positief geheel getal is dan vallen de representaties van n uiteen in die met tenminste een ``1'' en die zonder een ``1''. In het eerste geval kunnen we die ``1'' weglaten en vinden we een representatie voor 2k-1, in het tweede geval kunnen we alle getallen uit de representatie delen door 2 en vinden we een representatie voor k. Ook dit geldt andersom, zodat we vinden dat

Beide formules gelden voor alle . Het is duidelijk dat f(1)=1. Als we f(0)=1 definieren, dan geldt (4) ook voor k=0. Uit (4) en (5) volgt dat de functie f niet-dalend is.

Volgens (4) kunnen we f(2k-1) in (5) vervangen door f(2k-2) zodat we krijgen

Hieruit kunnen we afleiden dat

Nu hebben we genoeg informatie om af te kunnen schatten ( ).

De bovengrens is niet zo lastig. In (6) is elke volgende term tenminste gelijk aan zijn voorganger en aangezien voor vinden we

voor . Hieruit volgt:

Aangezien voor volgt de gezochte bovengrens.

Om de ondergrens te kunnen bepalen is het handig om eerst te laten zien dat

voor en a en b beide even danwel oneven.

Als a en b beide even zijn, dan volgt uit (4) dat we aan beide kanten van (7) nul hebben staan; als a en b allebei oneven zijn, dan volgt met behulp van (5) dat f(b+1)-f(b)=f((b+1/2), f(a+1)-f(a)=f((a+1/2) waar uit volgt dat (7) waar is, omdat de functie f niet-dalend is.

Als we willekeurige gehele getallen nemen, r even, en in (7) invullen a=r-j, b=r+j voor en al die ongelijkheden bij elkaar optellen, dan krijgen we

Omdat r even is geldt f(r+1)=f(r), en dus

Door al deze ongelijkheden bij elkaar op te tellen voor vinden we

Uit (6) volgt dat de linkerkant van de ongelijkheid gelijk is aan f(4r)-1, zodat

Door te nemen vinden we dus

Om te zorgen dat even is, moet m>2 zijn. Merk op dat de ongelijkheid echter ook waar is voor m=2.

Zij nu n een positief geheel getal groter dan 1, l een positief geheel getal zodanig dat . Dan vinden we

Neem voor even n: l=n/2, voor oneven n: l=(n-1)/2. We vinden dan:

We hebben voor alle positieve gehele getallen de ondergrens laten zien. Het is duidelijk dat de ondergrens voor n=1 ook klopt.

Up: IMO 1997 Previous: Opgave 5
Notice: Undefined variable: footer_php_included in /websites/users/pyth/public_html/pythwww/common/footer.php on line 2

Deprecated: setlocale() [function.setlocale]: Passing locale category name as string is deprecated. Use the LC_* -constants instead in /websites/users/pyth/public_html/pythwww/common/footer.php on line 5