algoritmes

Opgave - IrMO 1991 dag 1 vraag 3

Toon aan dat, startend vanaf 4, we met een eindig aantal keer één van volgende (al dan niet verschillende) algoritmen uit te voeren ieder natuurlijk getal kunnen bekomen.
(i) Het getal vertienvoudigen;
(ii) Het getal vertienvoudigen en er vier bij optellen;
(iii) Het getal halveren.

Oplossing

Stel dat niet alle natuurlijke getallen te bekomen zijn. Zij van al deze "niet te bekomen natuurlijke getallen" $a$ het kleinste.

Als $a$ een vijfvoud is, dan zouden we vanuit $\frac{a}{5}$ (hetgeen kleiner is dan $a$ en dus wel te bereiken valt) naar $2a$ (i) en dus ook naar $a$ (iii) kunnen geraken. Contradictie.

Dus $a$ is geen vijfvoud. De techniek voor $a\in\{1,2,3,4,6,7,8,9\}$ (modulo 10) zal dezelfde zijn als de voorgaande: we zoeken een getal strikt kleiner dan $a$ (dat dus wel te vormen valt) en leiden daaruit af dat $a$ wel te bekomen is, een contradictie vormend. Als we overal een contradictie bekomen, betekent dat dat er geen minimale $a$ bestaat, dus dat alle getallen gevormd kunnen worden.

(De volgende congruenties zijn steeds modulo 10.)

Als $a\equiv 1$, dan gaan we van $(4a-4)/10$ naar $4a$ (ii), om dan na twee keer (iii) toe te passen, tot $a$ te komen.

Als $a\equiv 2$, dan $(2a-4)/10\to 2a\to a$.

Als $a\equiv 3$, dan $(8a-4)/10\to 8a\to 4a\to 2a\to a$.

Als $a\equiv 4$, dan $(a-4)/10\to a$.

Als $a\equiv 6$, dan $(4a-4)/10\to 4a\to 2a\to a$.

Als $a\equiv 7$, dan $(2a-4)/10\to 2a\to a$.

Als $a\equiv 8$, dan $(8a-4)/10\to 8a\to 4a\to 2a\to a$.

Als $a\equiv 9$, dan...wordt het spreekwoord bevestigd: het venijn zit in de staart. :lol: Uhm, Schrijf $a = 10k+9$. Omdat $(16a-4)/10 = 16k+14 \equiv 6(k-1) \not\equiv 9\ (\text{mod }10)$, is dit getal (omwille van al het voorgaande) zeker vormbaar. Bijgevolg is ook $16a$ vormbaar (ii), en na 4 toepassingen van (iii) komen we dan tot $a$.

En we zijn klaar.