Feladat: B.3838 Korcsoport: 16-17 Nehézségi fok: könnyű
Megoldó(k):  Bozi Áron 
Füzet: 2007/január, 19 - 20. oldal  PDF file
Témakör(ök): Kettes alapú számrendszer, Számjegyekkel kapcsolatos feladatok, Feladat
Hivatkozás(ok):Feladatok: 2005/szeptember: B.3838

Az A pozitív egész szám kettes számrendszerbeli alakja n darab 1-esből áll. Bizonyítsuk be, hogy az nA szám kettes számrendszerbeli alakjában a számjegyek összege n.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Jelöljük az A kettes számrendszerbeli alakját A2-vel, a tízes számrendszerbelit A10-zel.

A2=111...111=1000...000-1.
A két kapcsos zárójel n db 1-est, illetve 0-t tartalmaz. Így A10=2n-1. Írjuk fel A2-t a következőképpen: A2=000...000111...111.
Így kapunk két darab n számjegyből álló részt. Vizsgáljuk ezeket a részeket külön-külön, mint n jegyű kettes számrendszerbeli számokat! Ha most hozzáadunk a kibővített A2-höz A2-t, akkor kettes számrendszerben írva 1000...000-1-et adunk hozzá. Tehát valahányszor hozzáadunk A2-t,
‐ a bal oldali n jegyű kettes számrendszerbeli számhoz 1-et adunk hozzá;
‐ a jobb oldali n jegyű kettes számrendszerbeli számból pedig 1-et veszünk el.
Tehát a bal oldali szám és a jobboldali szám összege (kettes számrendszerben) 111...111 (n db 1-es). Ez pedig csak úgy lehetséges, ha összesen n db 1-es van a bal oldali és a jobb oldali részben. (Mert ha pl. a bal oldali rész 3. számjegye 1, akkor a jobboldali rész 3. számjegyének 0-nak kell lennie stb.)
Ez tehát minden újabb A2-hozzáadásnál így működik egészen addig, míg a jobb oldali szám el nem fogy. Ez 2n-1 lépés alatt történne meg, vagyis 2nA-ig igaz az állítás.
Az állításnál általánosabban tehát azt mutattuk meg, hogy minden 2n-nél nem nagyobb pozitív egész szorzó esetén igaz a feladat állítása. (Az pedig világos, hogy n2n, hiszen 2n-1 kettes számrendszerbeli alakjában minden helyiértéken 1-es áll, a helyiértékek mindegyike nagyobb viszont 1-nél ‐ kivéve magát az 1-et.)