WisFaq!

Zoek veelvoud van 5¹⁰⁰ dat geen nullen bevat

Bewijs dat er een veelvoud van 5¹⁰⁰ bestaat dat in de decimale schrijfwijze geen nul bevat.

naam
8-12-2003

Antwoord

Hoi,

Deze vraag loopt op Pythagoras nog tot 15 december 2003. Daarom een kleine vertraging in de publicatie van mijn antwoord.

Een getal n bestaat uit m decimale cijfers {c_i:i=0..m-1}, wanneer n=sum(c_i.10ⁱ:i=0..m-1).
We leiden hieruit af dat 1.10^m-1n10. 10^m-1-1, zodat m-1log(n)m en dus m=int(log(n))+1. Zo weten we alvast dat 5¹⁰⁰ uit 70 cijfers bestaat.
In Excel bijvoorbeeld kan je de cijfers van de opeenvolgende machten van 5 één na één berekenen. Net zoals je met de hand dat op papier zou doen. Zo vind je dat 5¹⁰⁰ inderdaad een aantal nullen bevat, meer bepaald 12 op posities 3, 7, 13, 17, 18, 21, 23, 29, 53, 57, 62 en 64. Maar dat kunnen we verder niet echt gebruiken...

We definiëren: a_i=5ⁱ voor i=0,1,… en
b_i=5¹⁰⁰.2ⁱ= 5^100-i.10ⁱ=a_100-i.10ⁱ voor i=0,1,..,100 en b_i=10ⁱ voor i=101,102, …
Ze ziet onmiddellijk dat a_i nooit op 0 eindigt en dat 5¹⁰⁰ een deler is van elke b_i. Daarom is elke b_i van de vorm [..c_i+1 c_i00..0] waarbij c_i verschilt van 0. Elke b_i eindigt dus op precies i cijfers 0. We tonen nu aan hoe we de termen van de rij b_i kunnen gebruiken om de 0-gaatjes in de decimale notatie van 5¹⁰⁰ weg te werken. Het zijn dus de natural born 0-killers…

Voor een getal n dat minstens één 0 bevat in de decimale notatie {c_i:i=0..m-1}, kunnen we p(n)=min({i:c_i=0}) definiëren. Dit is dus de positie van het eerste 0-cijfer.
We construeren nu de rij:
n₀=5¹⁰⁰
n₁=n₀+b_p(n0)
n₂=n₁+b_p(n1)
…
n_i=n_i-1+b_p(nn-1)
…

Elke term n_i-1 van de rij heeft een eerste 0 op positie p(n_i-1). Omdat b_p(ni-1) op p(n_i-1) cijfers 0 eindigt, erft n_i de laatste zoveel cijfers van n_i-1. Op de plaats waar 0 stond, heeft n_i een cijfer verschillend van 0.
Bovendien geldt dat 5¹⁰⁰ een deler is van elke term n_i. Als we een term n_k vinden die geen enkel cijfer 0 bevat, is dit het gezochte veelvoud.
Bemerk dat wanneer we termen b_i toevoegen met i100 kan het gebeuren dat we extra 0-en toevoegen op hogere posities. Het volstaat daarom ook niet om zomaar de termen b_i toe te voegen waar c_i=0 in 5¹⁰⁰. Voor i100 is de toevoeging van een b_i wel een precisie-operatie: enkel het i-de cijfer wordt op 1 gezet, zonder andere cijfers te beïnvloeden. Het aantal cijfers van de termen van de rij n_i kan enkel groeien wanneer we termen b _p(ni-1) toevoegen met p(n_i-1) 100. Uit de constructie van de rij blijkt dat p(n_i-1) geheel en strikt stijgend is. Het aantal cijfers van de termen n_i kan dus niet blijven groeien en daarom is ook de rij n_i naar boven begrensd. Ze is uiteraard strikt stijgend en daarom heeft ze ook een limiet.
Praktisch kan je inzien dat we opeenvolgende cijfers 0 wegwerken door een gepaste 0-vulling toe te passen. Voor cijfers op posities tot en met 100 kunnen we cijfers bijmaken en ook 0-cijfers op hogere posities. Maar we blijven verder werken, tot we die eerste 101 cijfers 0-vrij hebben. Als er dan nog cijfers 0 staan op posities 100, kunnen we die met precisie-vullingen te lijf gaan, zonder complicaties op de lengte van het getal of het aantal hogere cijfers.

Groetjes,
Johan

PS: Collega CL gaf de tip dat je op Russische Wiskunde Olympiades iets gelijkaardigs kan vinden. Ze gebruiken andere 0-bestrijders en gaan op een andere (geniale) manier met de overloop over 101 cijfers om.

andros
16-12-2003