\infty - rij

Opgave - BxMO 2012 dag 1 vraag 1

Een rij (strikt) positieve gehele getallen $a_1,a_2,\cdots $ voldoet aan
$a_{n+1 } = a_n + b_n$ voor $n=1,2,3\cdots$
waar $b_n$ het laatste (meest rechtse) cijfer is in de decimale schrijfwijze van $a_n$. Bewijs dat zo'n
rij oneindig veel machten van $2$ bevat dan en slechts dan als $a_1$ niet deelbaar is door $5.$

Oplossing

Indien $a_1$ oneven is, zal zoiezo $a_2$ even zijn, gezien een oneven getal als laatste cijfer een oneven cijfer heeft en de som van twee oneven getallen even is. Indien $a_1$ even is, zal ook $a_2$ even zijn, gezien even getallen als laatste cijfer een even cijfer hebben en de som van twee even getallen even is.

Vanaf $n=2$ kunnen we dus stellen dat $a_n$ even is.
$b_n$ kan bijgevolg deze waarden aannemen: $2,4,6,8,0$.

Echter zou bij $b=0$ de volgende $a$ identiek zijn, dus kan in dat geval geen oneindig aantal machten van twee bereikt worden. Een $0$ als laatste cijfer kunnen we enkel hebben indien de vorige $a$ op $5$ eindigde of deelbaar was door $10$, dus indien $a_1$ deelbaar is door $5$, is een oneindig aantal machten van $2$ in de rij onmogelijk.

Indien $a_n$ eindigt op $2$, eindigt $a_{n+1}$ op $4$, met enkel dit laatste cijfer verschillend, dus moeten we de gevallen op $2$ niet apart bestuderen. Analoog kunnen we dit toepassen op $4$ en $8$, waardoor het te bewijzene nu dus enkel nog moet bewezen worden voor $6$ en $8$. De stappen vanaf $2$ en $4$ naar $8$ zijn hier van geen belang, gezien we een oneindig aantal moeten bewijzen.

We herschrijven $a_n$ tot $10x_n + y_n$, waarbij $y_n = a_n mod 10$ en $10x_n$ het wel door $10$ deelbare deel voorstelt.

Noteren we dus de rij beginnend met een getal eindigend op $6$:
$a_n = 10x_n + 6$
$a_{n+1} = 10(x_n+1) + 2$
$a_{n+2} = 10(x_n+1) + 4$
$a_{n+3} = 10(x_n+1) + 8$
$a_{n+4} = 10(x_n+2) + 6$

We zien dus dat de rest bij deling door $10$ dus repetitief per 4 stappen. Ook zien we dat in opeenvolgende tientallen afwisselend $6$ en $2,4,8$ als laatste cijfer voorkomt en dit proces zich onophoudelijk herhaalt.

Analoog vinden we voor een getal op $8$ perfect hetzelfde.
We bekijken nu de machten van $2$: $2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096...$
De laatste cijfers zijn dus steeds: $2,4,8,6,2,4,8,6...$
Waarbij bij een laatste cijfer $6$ en het daarop volgende getal met laatste cijfer $2$ het aantal tientallen steeds oneven is, terwijl bij laatste cijfers $4$ en $8$ het aantal tientallen altijd even is.
Vanaf $4$ zijn de machten van $2$ modulo $20$ cylisch $4,8,16,12,\cdots$

Gezien $(a_n)_n$ in het geval dat $5 \not| a_1$ zijn de resten $6,12,14,18 \pmod{20}$ of $16,2,4,8 \pmod{20}$ cyclsch repeterend voor $n \ge 2$ in een bepaalde volgorde.
De getallen $20k+12$ of $20k+16$ komen dan allen voor voor $k$ vanaf een bepaalde startwaarde.
Omdat $2^{4t+5}$ en $16^{t}$ resp. van deze vorm zijn voor elke natuurlijke $t$,
zullen er in elk geval oneindig veel machten van $2$ voorkomen.