Kezdőlap


Feladat:	F.3269	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Babos Attila , Bákor Krisztina , Dénes Attila , Győri Nikolett , Györey Bernadett , Horváth Gábor , Keszegh Balázs , Kunszenti-Kovács Dávid , Lábó Eszter , Lábó Melinda , Máthé András , Naszódi Gergely , Pap Júlia , Papp Dávid , Pataki Péter , Pilászy István , Szabadka Zoltán , Székelyhidi Gábor , Terpai Tamás
Füzet:	1999/december, 538. oldal		PDF \| MathML
Témakör(ök):	"a" alapú számrendszer (a >1, egész szám), Maradékos osztás, Feladat
Hivatkozás(ok):	Feladatok: 1999/február: F.3269

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.

Ha $s = 2$ , akkor $s - 1 = 1$ és így a maradék 0. Tegyük fel a továbbiakban, hogy $s > 2$ . Jelölje $S_{i}$ az $(s + 1)$ -es alapú számrendszerben felírt ${\underset{︸}{i i i ... i}}_{i-szer}^{}$ számot.

\begin{matrix} S_{i} = i \cdot {\underset{︸}{111 ... 1}}_{i-szer}^{} = i \cdot ({(s + 1)}^{i - 1} + {(s + 1)}^{i - 2} + ... + 1) . \end{matrix}

(s + 1)

-et

(s - 1)

-gyel osztva a maradék 2, ezért

S_{i}

és

i (2^{i - 1} + 2^{i - 2} + ... + 1) = i (2^{i} - 1)

ugyanazt a maradékot adja

(s - 1)

-gyel osztva.
Tehát

1 + 22 + ... + s s ... s

ugyanakkora maradékot ad

(s - 1)

-gyel osztva, mint

\begin{matrix} 1 (2^{1} - 1) + 2 (2^{2} - 1) + ... + s (2^{s} - 1) = 1 \cdot 2 + 2 \cdot 2^{2} + ... + s \cdot 2^{s} - \frac{s (s + 1)}{2} . \end{matrix}

Legyen

\begin{matrix} \begin{matrix} B & = 1 \cdot 2^{1} + 2 \cdot 2^{2} + ... + s \cdot 2^{s} - 2, \\ ekkor \\ 2 B & = 1 \cdot 2^{2} + 2 \cdot 2^{2} + ... + s \cdot 2^{s + 1} - 4. \end{matrix} \end{matrix}

A két egyenlet különbsége:

\begin{matrix} B = - 2^{1} - 2^{2} - ... - 2^{s} + s \cdot 2^{s + 1} - 2 = (s - 1) 2^{s + 1}, \end{matrix}

ami osztható

(s - 1)

-gyel.
Tehát a feladatban meghatározandó mennyiség

(2 - \frac{s (s + 1)}{2})

-nek az

(s - 1)

-gyel való osztási maradéka.
Ez 1, ha

s

páros, és

\frac{s + 1}{2}

, ha

s

páratlan.

Máthé András (Budapest, ELTE Apáczai Csere J. Gimm., 11. o.t.) dolgozata alapján