Vierkant Kalender 1999

Oplossingen week 32 (9 t/m 15 augustus)

Reizen door de natuurlijke getallen (2).

Maandag 9 augustus:
4 -> 3 -> 6 -> 12 -> 11.
Dinsdag 10 augustus:
3 -> 6 -> 5 -> 10 -> 9.
Woensdag 11 augustus:
10 -> 9 -> 8 -> 7 -> 6 -> 12 -> 11; 6 stappen.
Donderdag 12 augustus:
8 -> 7 -> 6 -> 12 -> 24; 4 stappen.
Vrijdag 13 augustus:
1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 24.
Zaterdag 14 augustus:

Laat ak het aantal getallen op afstand k van 1 zijn. Dan is ak = 1 voor k < 3. Neem nu k groter of gelijk aan 3. Twee of meer keer -1 na elkaar geeft een getal dat al eerder voorkomt, dus na -1 komt alleen ×2.
Gevolg: alle even getallen ontstaan uit ×2 en alle oneven getallen ontstaan uit -1 (uitgaande van een even getal). Op niveau k-1 worden alle getallen verdubbeld; dit geeft ak-1 even getallen op niveau k. De even getallen op niveau k-1 (dat zijn er dus ak-2) worden met 1 verminderd; dat geeft ak-2 oneven getallen op niveau k. In totaal zijn er dus ak-1 + ak-2 verschillende getallen op niveau k.

Om te kunnen concluderen dat ak = ak-1 + ak-2, moeten we nog aantonen dat er geen getallen ontstaan die eerder zijn gevormd. Welnu, stel getal g staat op niveau p en op niveau q met p < q en p minimaal. Dit leidt al snel tot een tegenspraak.

Zondag 15 augustus:

Aanvulling op de kalender: "... gelijk aan b+g ..." moet zijn: "... minstens gelijk aan b+g ...".

We gebruiken de notatie b(n) voor het aantal bits van n en g(n) voor het aantal rijtjes opvolgende enen in de tweetallige representatie van n.

Als dat getal n even is (dus tweetallig op 0 eindigt), is n ontstaan door (n/2)x2. Nu is b(n) = b(n/2) + 1 en g(n) = g (n/2), zodat ook n/2 minder dan b + g stappen vereist: tegenspraak. Als n oneven is, is n ontstaan door (n+1) - 1. En b(n) = b(n+1), terwijl g(n) groter of gelijk g(n+1). Dus ook n+1 zou in minder dan b+g stappen zijn te maken. Dit is weer in tegenspraak met de minimaliteit van n.Een exacte formule voor de afstand van 1 tot n is gevonden door Stijn de Reede, leerling van het Erasmiaans Gymnasium te Rotterdam. De juistheid van de formule werd bewezen door zijn wiskundeleraar, drs. Chris Wildhagen. De formule luidt als volgt. Laat A(n) de afastand van 1 tot n zijn, b(n) het aantal bits van n in de binaire representatie, en i(n) het aantal nullen met uitzondering van een evt. blok nullen aan de rechterkant. Dan is A(n) = k als n = 2k, en A(n) = b(n) + i(n) + 1 als n geen macht van 2 is. De heer Wildhagen meldde ook dat het probleem in een enigszins andere formulering voorkomt in de probleemrubriek van Mathematics Magazine. Een oplossing staat op blz 150 van het aprilnummer van dit jaar.