Kezdőlap


Feladat:	Pontversenyen kívüli P.109	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Balogh Z. , Császár Gy. , Füredi Z. , Hermann P. , Kilen M. , Reviczky J. , Szeredi J. , Totik V. , Turi Erzsébet
Füzet:	1974/november, 146 - 148. oldal		PDF \| MathML
Témakör(ök):	Számhalmazok, Maradékos osztás, Legnagyobb közös osztó, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1971/szeptember: Pontversenyen kívüli P.109

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.

Azoknak az $x$ számoknak a $T$ halmazát kell meghatároznunk, amelyeknek megvan az a tulajdonságuk, hogy ha egy hatjegyű $A$ szám osztható $x$ -szel, akkor $A$ családjának minden tagja osztható $x$ -szel. Más szóval ez a tulajdonság azt jelenti, hogy $H (x)$ -szel jelölve az $x$ szám hatjegyű többszöröseit, a $H (x)$ halmaznak tetszőleges elemével együtt az illető $A$ elem egész családja is a $H (x)$ halmazhoz tartozik. Ez a követelmény semmitmondó azokra az $x$ számokra, amelyekre $H (x)$ üres, ami pontosan akkor következik be, ha $x \geq 10^{6}$ . A feladatban mondott tulajdonsága, tehát minden legalább $7$ jegyű természetes számnak megvan. A továbbiakban a vizsgált $T$ halmaz $10^{6}$ -nál kisebb elemeit határozzuk meg, s ezek halmazát $T_{0}$ -lal jelöljük.
Legyen egy tetszőleges hatjegyű $A$ szám tízes számrendszerbeli alakja
$A = a_{6} a_{5} a_{4} a_{3} a_{2} a_{1}$ . Feladatunk szerint

\begin{matrix} A_{k} = 10^{6 - k} C + B, \end{matrix}

ahol

C = a_{k} a_{k - 1} ... a_{1}

B = a_{6} a_{5} ... a_{k + 1}

, azaz

A_{k} = a_{k} a_{k - 1} ... a_{1} a_{6} ... a_{k + 1}

.
Az

A_{k}

számokat tehát egymásból is előállíthatjuk:

A_{k}

-ból úgy kapjuk

A_{k + 1}

-et, hogy

A_{k}

utolsó jegyét a többi jegy elé írjuk

\begin{matrix} A_{k + 1} = \frac{A_{k} - a_{k + 1}}{10} + 10^{5} a_{k + 1} . \end{matrix}

Érvényes lesz ez a megállapítás

A_{1}

képzésére is, ha

A

-t

A_{0}

-lal jelöljük. A családnak csak hat tagja van,

A_{6}

-ból már nem kapunk új számot:

A_{7}

azonos

A_{0}

-lal.
Legyen

x

T_{0}

, és

A

H (x)

halmaz tetszőleges eleme, azaz

A

legyen

x

-szel osztható hatjegyű szám. Mivel

x \in T_{0}

, az

A_{k}

számok is oszthatók

x

-szel, és velük együtt

x

-szel oszthatók a

\begin{matrix} 10 A_{k + 1} - A_{k} = (10^{6} - 1) a_{k + 1} (k = 0, 1, 2, 3, 4, 5) \end{matrix}

számok is. Mivel

a_{k + 1}

A

szám tetszőleges számjegye, és

A

H (x)

tetszőleges eleme, eredményünk azt jelenti, hogy

x

osztója a

(10^{6} - 1) \cdot a

alakú számok mindegyikének, ahol

a

H (x)

halmaz tetszőleges elemének tetszőleges számjegye.
Jelöljük

h (x)

-szel a

H (x)

-beli számok számjegyeinek legnagyobb közös osztóját, előbbi megállapításaink szerint ha

x \in T_{0}

, akkor

(10^{6} - 1) h (x)

osztható

x

-szel (hiszen a

(10^{6} - 1) a

számok mindegyike osztható

x

-szel, ha

a

befutja

H (x)

számjegyeit, így e számok legnagyobb közös osztója,

(10^{6} - 1) h (x)

is osztható

x

-szel).
Ha

x

maga is hatjegyű, akkor

h (x)

x

számjegyeinek is közös osztója; azaz

x

számjegyei az

\begin{matrix} x_{0} = \frac{x}{h (x)} \end{matrix}

szám számjegyeinek a

h (x)

-szeresei; és

x_{0}

(10^{6} - 1)

szám hatjegyű osztója. Mivel

\begin{matrix} 10^{6} - 1 = 3^{3} \cdot 7 \cdot 11 \cdot 13 \cdot 37, \end{matrix}

10^{6} - 1

-nek három hatjegyű osztója van:

\begin{matrix} K = \frac{10^{6} - 1}{9} = 111 111, \\ L = \frac{10^{6} - 1}{7} = 142 857, \\ M = \frac{10^{6} - 1}{3} = 333 333. \end{matrix}

x_{0}

szám ezek valamelyike lehet, és

x_{0}

számjegyeiből úgy kapjuk meg

x

számjegyeit, hogy mindegyiket megszorozzuk egy alkalmas

h

számmal. Így kapjuk

K

-ből a

\begin{matrix} K_{h} = h K = 111 111 h (h = 1, 2, 3, 4, 5, 6, 7, 8, 9) \end{matrix}

számokat;

L

-hez viszont csak a

h = 1

választás lehetséges, és

M

-ből nem kapunk új számot. A

K_{h}

számoknak triviálisan megvan a vizsgált tulajdonságuk, az

L

számra ezt ‐ lévén

L

(10^{6} - 1)

osztója ‐

(10^{6} - 1)

többi osztójával együtt az alábbiakban bizonyítjuk.
Ha

x < 10^{5}

, akkor

x

egymást követő többszöröseinek az első jegye vagy megegyezik, vagy

1

-gyel különbözik egymástól (hiszen ez a különbség épp az

x

), tehát

h (x) = 1

, így

T_{0}

-nak csak olyan

10^{5}

-nél kisebb eleme lehet, amelyik a

(10^{6} - 1)

szám osztója. Megmutatjuk, hogy

(10^{6} - 1)

minden osztója eleme

T_{0}

-nak;
Az

A_{k}

számok képzésére vonatkozó korábbi megállapításunk szerint elegendő azt bizonyítanunk, hogy ha

x

(10^{6} - 1)

tetszőleges osztója, és

A

osztható

x

-szel, akkor

A_{1}

is osztható

x

-szel. Valóban,

\begin{matrix} 10 A_{1} - A = (10^{6} - 1) a_{1} \end{matrix}

miatt (ahol

a_{1}

A

szám utolsó jegye) osztható

x

-szel a

D = 10 A_{1} - A

szám is. Emiatt

\begin{matrix} D + A = 10 A_{1} \end{matrix}

is osztható

x

-szel, ámde

x

és

10

relatív prímek (mint ahogy

(10^{6} - 1)

és

10

is azok), ez tehát csak úgy lehet, ha

A_{1}

is osztható

x

-szel.
A vizsgált

T

halmaz elemei tehát a következők:
‐ a legalább hétjegyű természetes számok,
‐ a

K_{h}

számok (ezek a csupa egyforma számjeggyel felírt számok), ‐ a

(10^{6} - 1)

szám osztói.