Kezdőlap


Feladat:	2003. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Pach Péter Pál
Füzet:	2004/október, 394 - 395. oldal		PDF \| MathML
Témakör(ök):	Oszthatósági feladatok, Tizes alapú számrendszer, Euler-Fermat-tételek, Lineáris kongruenciák, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2004/szeptember: 2003. évi Nemzetközi Matematika Diákolimpia 23. feladata

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.

Pach Péter Pál megoldása. Ha $20 ∣ n$ , akkor az $n$ utolsó jegye 0 és $4 ∣ n$ miatt az utolsó előtti jegy páros, így ekkor az $n$ -nek nincsen alternáló többszöröse. A továbbiakban több lépésben igazoljuk, hogy a $20 ∤ n$ feltétel elégséges, ebben az esetben létezik olyan alternáló szám, amelyik osztható $n$ -nel.

a)

Legyen először

n = 2^{k}

. Megmutatjuk, hogy létezik olyan alternáló számokból álló

A_{1}, A_{2}, ..., A_{k}, ...

sorozat, amelyben

A_{k}

-nak

k

jegye van

(k = 1,2, ...)

A_{k + 1}

A_{k}

,,folytatása'', tehát első jegyét elhagyva

A_{k}

-t kapjuk,

2^{k} ∣ A_{k}

, továbbá

2^{k + 1} ∣ A_{k}

pontosan akkor teljesül, ha

k

páros. Az

A_{k}

sorozatot teljes indukcióval állítjuk elő:

k = 1

, illetve

k = 2

esetén

A_{1} = 2

és

A_{2} = 32

megfelelő.
Legyen

k \geq 2

páros és tegyük fel, hogy az

A_{k}

számot már megadtuk a feltételeknek megfelelően, tehát

A_{k}

k

-jegyű alternáló szám és osztható

2^{k + 1}

-nel. Mivel

k

páros,

A_{k}

első jegye páratlan. Így akár 2-est, akár 4-est írunk a szám elejére,

(k + 1)

-jegyű alternáló számot kapunk és

2^{k + 1} ∣ 2 \cdot 10^{k}

, illetve

2^{k + 1} ∣ A_{k}

miatt mindkét esetben

2^{k + 1}

többszörösét kapjuk. Mivel

k + 1

páratlan, meg kell még mutatnunk, hogy

2 \cdot 10^{k} + A_{k}

és

4 \cdot 10^{k} + A_{k}

valamelyike nem osztható

2^{k + 2}

-nel. Ez nyilvánvaló, ellenkező esetben ugyanis a különbségük,

2 \cdot 10^{k} = 2^{k + 1} \cdot 5^{k}

is osztható volna

2^{k + 2}

-nel. Így ha

k

páros, akkor létezik a megfelelő

A_{k + 1}

.
Legyen most a

k

páratlan. Ekkor

A_{k}

első jegye páros, így 1-et, illetve 3-at írva a szám elejére

(k + 1)

-jegyű alternáló számot kapunk. A konstrukció szerint

2^{k} ∣ A_{k}

és

2^{k + 1} ∤ A_{k}

, így

A_{k} \equiv 2^{k} (mod 2^{k + 1})

, továbbá nyilván

1 \cdot 10^{k} \equiv 3 \cdot 10^{k} \equiv 2^{k} (mod 2^{k + 1})

. A megfelelő kongruenciákat összeadva kapjuk, hogy mindkét így adódó szám osztható

2^{k + 1}

-nel. Mivel a különbségükben,

2 \cdot 10^{k} = 2^{k + 1} \cdot 5^{k}

-ban is

k + 1

a 2 kitevője, azért legalább az egyikük még

2^{k + 2}

-nel is osztható. Így az

A_{k + 1} = 10^{k} + A_{k}

vagy

A_{k + 1} = 3 \cdot 10^{k} + A_{k}

választás megfelelő.

b)

n = 5^{k}

, akkor ismét indukcióval megmutatjuk, hogy az

n

-nek van legfeljebb

k

-jegyű

B_{k}

alternáló többszöröse. (

B_{k}

legelső jegye lehet 0 is.)
Ha

k = 1

, akkor

B_{1} = 5

megfelelő. Legyen

k \geq 1

és a

B_{k}

olyan, legfeljebb

k

-jegyű alternáló szám, amelyre

B_{k} \equiv 0 (mod 5^{k})

. Ekkor valamilyen

i \in {0; 1; 2; 3; 4}

számra

B_{k} \equiv i \cdot 5^{k} (mod 5^{k + 1})

. Ha

B_{k}

elejére egy újabb

x

számjegyet akarunk betoldani, akkor az oszthatósághoz

\begin{matrix} x \cdot 10^{k} + B_{k} \equiv 0 (mod 5^{k + 1}), azaz x \cdot 10^{k} + i \cdot 5^{k} = 5^{k} (x \cdot 2^{k} + i) \equiv 0 (mod 5^{k + 1}) \end{matrix}

szükséges. Ez pontosan akkor teljesül, ha

x \cdot 2^{k} + i \equiv 0 (mod 5)

. Mivel

(2^{k}; 5) = 1

, azért ennek a kongruenciának van megoldása mod 5. Végül vegyük észre, hogy az

x

paritását megválaszthatjuk, hiszen a páros, illetve a páratlan számjegyek is egy-egy teljes maradékrendszert alkotnak (mod 5). Így a megfelelő választással

B_{k + 1} = x \cdot 10^{k} + B_{k}

is alternáló szám lesz, amely osztható

5^{k + 1}

-nel.

c)

(10; n) = 1

, akkor a feladat állításán túlmenően azt igazoljuk, hogy az

x \equiv r (mod n)

kongruenciának minden

r

maradék esetén létezik adott paritású alternáló megoldása.
Először azt mutatjuk meg, hogy ha

(10; n) = 1

, akkor van olyan teljes maradékrendszer (mod

n

), amelynek az elemei csak a 2 és a 0 számjegyeket tartalmazzák.
Az Euler‐Fermat-tétel szerint ugyanis

10^{φ (n)} \equiv 1 (mod n)

, így ha

k_{1}, k_{2}, ..., k_{r}

különböző pozitív egészek, akkor

\begin{matrix} T_{r} = 10^{k_{1} φ (n)} + 10^{k_{2} φ (n)} + ... + 10^{k_{r} φ (n)} \equiv {\underset{︸}{1 + 1 + ... + 1}}_{r}^{} \equiv r (mod n), \end{matrix}

T_{r}

számokból tehát teljes maradékrendszer készíthető (mod

n

). Mivel

(2; n) = 1

, azért a

2 T_{r}

számok is teljes maradékrendszert alkotnak (mod

n

) és rendelkeznek az előírt tulajdonsággal.
Tekintsünk most egy olyan

H = 1010 ... 10

alakú alternáló számot, amely a fenti

2 T_{r}

alakú számokból álló teljes maradékrendszer minden eleménél több jegyből áll. Ekkor az

A + 2 T_{r}

alakú számok is teljes maradékrendszert alkotnak (mod

n

), másrészt maguk is alternálók, hiszen a

H

alternáló számhoz olyan ,,rövidebb'' számokat adtunk, amelyek minden jegye páros és a jegyek kicsik, tehát nincs tízes átlépés. Ebben az alternáló teljes maradékrendszerben minden szám páros.
Ha most a

\begin{matrix} 10 H + 1 = {\underset{︸}{1010 ... 10}}_{H}^{} 1 \end{matrix}

páratlan alternáló számhoz adjuk hozzá a teljes maradékrendszer

2 T_{r}

elemeit, akkor alternáló páratlan számokból álló teljes maradékrendszert kapunk (mod

n

).
Ebből következik, hogy ha

(10; n) = 1

, akkor

n

-nek van alternáló többszöröse, az erősebb állításra a későbbiekben lesz szükség.

d)

Hátra van még az az eset, amikor

n

osztható 2-vel vagy 5-tel, de nem osztható 20-szal. Ha

n = 2^{α} \cdot 5^{β} \cdot n_{1}

, ahol

(n_{1}; 10) = 1

, akkor vagy

α \leq 1

és

β > 0

, vagy pedig

α \geq 1

és

β = 0

. Ha

α \leq 1

és

β > 0

, akkor

b)

szerint

5^{β - 1}

-nek létezik legfeljebb

(β - 1)

-jegyű

B

alternáló többszöröse, amelynek utolsó jegye, 5, páratlan. Így

B_{1} = 10 B

β

-jegyű alternáló szám és

α \leq 1

miatt

2^{α} \cdot 5^{β} ∣ B_{1}

.
Olyan

C

alternáló számot keresünk, amelyre

D_{1} = C \cdot 10^{β} + B_{1}

is alternáló és osztható

n

-nel. Mivel

2^{α} \cdot 5^{β} ∣ 10^{β}

, azért

2^{α} \cdot 5^{β} ∣ D_{1}

. Most

(10; n_{1}) = 1

, tehát

c)

szerint az

x \cdot 10^{β} + B_{1} \equiv 0 (mod n_{1})

kongruenciának létezik adott paritású alternáló megoldása, így

B_{1}

első jegyének paritásától függően olyan is, amelyre

D_{1}

is alternáló. Miután most

(n_{1}; 2) = (n_{1}; 5) = 1

, azért

n = 2^{α} \cdot 5^{β} \cdot n_{1} ∣ D_{1}

.
Végül ha

β = 0

és

α \geq 1

, akkor ugyanígy okoskodhatunk.

a)

szerint van olyan

α

-jegyű

A

alternáló szám, amelyre

2^{α} ∣ A

c)

szerint pedig a

10^{α} \cdot x + A \equiv 0 (mod n_{1})

kongruenciának van adott paritású alternáló megoldása. Ekkor

2^{α} ∣ 10^{α}

, tehát

2^{α} ∣ 10^{α} \cdot x + A

(2; n_{1}) = 1

miatt

n = 2^{α} \cdot n_{1} ∣ 10^{α} \cdot x + A

és

x

paritását az

A

első jegyével ellentétesnek választva

10^{α} \cdot x + A

is alternáló szám lesz.
Ezzel minden esetet megvizsgáltunk, a bizonyítást befejeztük.