Kezdőlap


Feladat:	1962. évi Kürschák matematikaverseny 1. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Kóta József , Máté Attila , Pósa Lajos , Sebestyén Zoltán
Füzet:	1963/március, 98 - 100. oldal		PDF \| MathML
Témakör(ök):	Prímszámok, Prímszámok száma, Prímtényezős felbontás, Legnagyobb közös osztó, Legkisebb közös többszörös, Osztók száma, Oszthatóság, Kombinatorikai leszámolási problémák, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1963/március: 1962. évi Kürschák matematikaverseny 1. 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.

Megjegyzések. 1. A feladat szövegének zárójelbe foglalt kiegészítése más szóval azt jelenti, hogy nem olyan $u$ , $v$ számpárok számát vizsgáljuk, amelyekben a két szám sorrendje közömbös, hanem az $u$ , $v$ rendezett számpárokét, hogy tehát az összeszámláláskor két számpár csak akkor tekintendő azonosnak, ha bennük az első számok és a második számok is egyenlők.
2. A feladat alábbi megoldásaiban használjuk a következő, általánosan is használt jelöléseket: természetes számok körében ( $a$ , $b$ ) az $a$ , $b$ számok legnagyobb közös osztóját, $[a, b]$ a legkisebb közös többszörösüket, $a | b$ pedig azt jelöli, hogy $a$ osztója $b$ -nek.

I. megoldás. Legyen

n

törzstényezős felbontása

\begin{matrix} n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{s}^{a_{s}}, \end{matrix}

ahol

p_{1}, p_{2}, ..., p_{s}

különböző törzsszámok,

a_{1}, a_{2}, ..., a_{s}

pedig nem-negatív egész számok. Minthogy a vizsgált számpárokra

[u, v] = n

, az

u

v

számok törzstényezői is csak a

p_{1}, p_{2}, ..., p_{s}

törzsszámok közül valók lehetnek.
Vizsgáljuk meg, hogy pl.

p_{1}

mekkora kitevővel szerepelhet

u

-ban és

v

-ben. E két kitevő között

[u, v] = n

miatt

a_{1}

-nek is szerepelnie kell, és egyik sem lehet

a_{1}

-nél nagyobb. Ez háromféleképpen következhetik be: 1.

p_{1}

kitevője mindkét helyen

a_{1}

, ez

1

lehetőség; 2.

p_{1}

kitevője

u

-ban

a_{1}

v

-ben viszont kisebb, tehát a

0, 1, 2, ..., a_{1} - 1

számok valamelyike, ami

a_{1}

lehetőséget jelent; 3.

p_{1}

kitevője

v

-ben

a_{1}

és

u

-ban kisebb, ami ismét

a_{1}

lehetőséget ad. Az összes lehetőségek száma ezek szerint

2 a_{1} + 1

.
Hasonlót mondhatunk a többi törzstényezőről is. Minthogy pl.

p_{1}

kitevőinek rögzítése után a többi kitevő számára ugyanazok a lehetőségek maradnak meg, a vizsgált

u

v

számpárok száma az egyes törzstényezőkre számba vett lehetőségek szorzata:

\begin{matrix} (2 a_{1} + 1) (2 a_{2} + 1) ... (2 a_{s} + 1) . \end{matrix}

Meg kell még mutatnunk, hogy

n^{2}

osztóinak száma ugyanennyi. Ez nyomban belátható abból, hogy

\begin{matrix} n^{2} = p_{1}^{2 a_{1}} p_{2}^{2 a_{2}} ... p_{s}^{2 a_{s}} \end{matrix}

osztóiban pl.

p_{1}

kitevője

0, 1, 2, ..., 2 a_{1}

lehet, azaz

2 a_{1} + 1

lehetőség van, s hogy az így adódó lehetőségek számát ismét össze kell szorozni, hiszen az egyes törzstényezőkre vonatkozó lehetőségek egymástól ismét függetlenek.

Megjegyzés. Megoldásunkban az

a

kitevő

2 a + 1

lehetőséghez vezetett. Ehhez az értékhez a következő, bonyolultabb módon is eljuthatunk:
Az

u

-ban és

v

-ben szereplő kitevők egyike sem nagyobb

a

-nál, azaz mindkettő a

0,1,2, ..., a

értékek valamelyike. Eszerint

a + 1

lehetőség adódik mindegyik megválasztására, és

{(a + 1)}^{2}

lehetőség a kitevőpár számára. E lehetőségek közül azonban csak azok felelnek meg, amelyekben legalább egyszer maga az

a

érték is szerepel. Ki kell tehát zárnunk azokat az eseteket, amelyekben mindkét kitevő a

0, 1, 2, ..., a - 1

számok közül való. Ez összesen

a^{2}

lehetőség kirekesztését jelenti, s ezért a tényleges lehetőségek száma

{(a + 1)}^{2} - a^{2} = 2 a + 1

.
Ez a bonyolultabb út azért tanulságos, mert magyarázat nélkül érthetővé teszi, hogy ha az

u

v

számpár helyett olyan

u_{1}, u_{2}, ..., u_{k}

számsorozatok számát keressük, amelyekben szereplő számok legkisebb közös többszöröse

n

, akkor feleletül

\begin{matrix} [{(a_{1} + 1)}^{k} - a_{1}^{k}] [{(a_{2} + 1)}^{k} - a_{2}^{k}] ... [{(a_{s} + 1)}^{k} - a_{s}^{k}] \end{matrix}

adódik.

II. megoldás. A feladat állítását azáltal bizonyítjuk, hogy a vizsgált

u

v

rendezett számpárok és

n^{2}

osztói között kölcsönösen egyértelmű hozzárendelést létesítünk. Az

u

v

számpárhoz azt a

d

számot rendeljük hozzá, amelyre

\begin{matrix} \frac{u}{v} = \frac{d}{n} . \end{matrix}

(1)

Ez a

d

valóban egész szám, mert

[u, v] = n

miatt

v | n

, s így a baloldali törtet egész számmal kell bővíteni, hogy a jobboldali alakot vegye fel. Ez azt is mutatja, hogy

d

valóban

n^{2}

osztója, hiszen az

u

számlálót

n

egy másik osztójával ti.

n / v

-vel szorozva adódik.
Fel fogjuk használni, hogy ha

u_{1} : v_{1} = u_{2} : v_{2}

, akkor

\begin{matrix} u_{1} : u_{2} = v_{1} : v_{2} = [u_{1}, v_{1}] : [u_{2}, v_{2}] . \end{matrix}

(2)

Két szám legkisebb közös többszörösének keresésekor ugyanis két olyan, lehetőleg kicsiny egész számot kell keresnünk, amelyekkel az egyiket és a másikat megszorozva ugyanahhoz az eredményhez jutunk. Ezeknek az egész számoknak a megválasztása eszerint csak a megadott két szám arányától függ. Ha tehát az

u_{1}

v_{1}

számpárról az ugyanolyan arányú

u_{2}

v_{2}

számpárra térünk át, akkor ‐ miként állítottuk ‐ a legkisebb közös többszörös is velük arányosan változik meg.
Bebizonyítjuk most, hogy különböző

u_{1}

v_{1}

és

u_{2}

v_{2}

számpárokhoz nem tartozhat ugyanaz a

d

szám. Ha ez így volna, akkor rájuk

\begin{matrix} \frac{u_{1}}{v_{1}} = \frac{u_{2}}{v_{2}} = \frac{d}{n} \end{matrix}

s ennek következtében

(2)

is teljesülne. Minthogy pedig

[u_{1}, v_{1}] = [u_{2}, v_{2}] = n

(2)

szerint

u_{1} = u_{2}

és

v_{1} = v_{2}

adódik, ami állításunk helyességét bizonyítja.
Be kell még bizonyítanunk, hogy

n^{2}

minden

d

osztója szerepel az

u

v

számpárokhoz tartozó számok között. Ennek bizonyítása végett a

d / n

törtet redukált

\begin{matrix} \frac{d}{n} = \frac{p}{q} \end{matrix}

alakra hozzuk, ahol tehát

(p, q) = 1

. Elég bebizonyítanunk, hogy

[p, q] | n

, mert akkor

(2)

szerint a

p / q

tört olyan

u / v

törtté bővíthető, amelyre az

[u, v] = n

feltétel is teljesül.
Eszerint már csak

p | n

és

q | n

bizonyítása a feladatunk. Az utóbbi nyilvánvalóan helyes, hiszen

q

egy

n

nevezőjű tört egyszerűsítése után lépett fel nevezőként. A

p

-re vonatkozó állítás

\begin{matrix} \frac{n^{2}}{d} = \frac{n q}{p} \end{matrix}

következménye, mert itt a baloldalon egész szám áll, ezért a jobboldalon is, azaz

p | n q

. Minthogy pedig

(p, q) = 1

, eredményünkből

p | n

is következik.

III. megoldás. Az előző megoldáshoz hasonlóan okoskodunk és ugyanúgy indulunk el. A vizsgált számpárokhoz ismét

(1)

előírásával rendeljük hozzá

n^{2}

egy-egy osztóját.

(1)

-ből

(2)

-re hivatkozva

\begin{matrix} u : d = v : n = n : [d, n] \end{matrix}

(3)

következik, hiszen

[u, v] = n

. Eszerint

d

ismeretében

u

és

v

már meghatározható:

\begin{matrix} u = \frac{d n}{[d, n]}, v = \frac{n^{2}}{[d, n]} \end{matrix}

(4)

n^{2}

valamely

d

osztója tehát csak ehhez az egyetlen

u

v

számpárhoz tartozhat hozzá.
Ha

d | n^{2}

, akkor

(4)

egész számokat szolgáltat, hiszen

d n

és

n^{2}

egyaránt közös többszöröse a

d

n

számoknak, ezért legkisebb közös többszörösük egészszámszorosa. Ha tehát

n^{2}

valamely

d

osztójából kiindulva

(4)

előírásával az

u

v

számpárt képezzük, olyan egész számokat kapunk, amelyekre a

(4)

-gyel egyenértékű

(3)

is teljesül, ami csak

[u, v] = n

esetén következhetik be. Ezek szerint

n^{2}

minden osztója szerepel az

u

v

számpárjainkhoz rendelt számok között.