Kezdőlap


Feladat:	1982. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Csillag Péter , Hetyei Gábor , Károlyi Gyula , Magyar Ákos , Szabó Endre , Tardos Gábor , Tóth Gábor
Füzet:	1983/február, 53 - 56. oldal		PDF \| MathML
Témakör(ök):	Természetes számok, Legkisebb közös többszörös, Oszthatósági feladatok, Prímtényezős felbontás, Oszthatóság, Egyenlőtlenségek, Sorozat határértéke, Prímszámok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1983/február: 1982. évi Kürschák matematikaverseny 2. 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.

(A legkisebb közös többszörös annyiszor fordul elő az alábbi szövegben, hogy röviden lkkt-t írunk helyette.)

I. megoldás. Az

a_{1}

a_{2}

...

a_{m}

számok lkkt-ét ‐ amit így szokás jelölni: [

a_{1}, a_{2}, ..., a_{m}

], ‐ úgy határozhatjuk meg, hogy minden prímszámot, amelyik a számok valamelyikének osztója, vesszük azon a legmagasabb hatványon, amelyiken osztója valamelyik

a_{i}

-nek, és ezeket a prímszámhatványokat összeszorozzuk. Eszerint

\begin{matrix} T_{n} = [n, n + 1, ..., n + k - 1] és T_{n + 1} = [n + 1, n + 2, ..., n + k - 1, n + k] \end{matrix}

prímhatványokra történő felbontásában egyenlő hatványon szerepelnek azok a prímszámok, amelyeknek a legmagasabb hatványa az

n + 1

n + 2

...

n + k - 1

számok valamelyikének a felbontásában fordul elő.

T_{n}

-ben magasabb hatványon szerepelnek, mint

T_{n + 1}

-ben azok a prímek (ha vannak), amelyeknek magasabb hatványa osztója

n

-nek, mint

n + 1

...

n + k

bármelyikének, és alacsonyabb hatványon azok az esetleges prímek, amelyeknek magasabb hatványa osztója

n + k

-nak, mint

n

...

n + k - 1

bármelyikének.
Legyenek

p_{1}

...

p_{g}

az előbbi tulajdonságú prímek és legyen

p_{j}

T_{n}

-nek (s így

n

-nek is) a

t_{j}

-edik hatványon osztója,

T_{n + 1}

-nek az

u_{j}

-edik hatványon osztója, ahol

t_{j} > u_{j}

(

j = 1, ..., g

); hasonlóan legyenek az utóbbi tulajdonsággal rendelkező prímek

q_{1}

...

q_{h}

és

q_{j}

T_{n}

-nek

v_{j}

-edik,

T_{n + 1}

-nek

w_{j}

-edik hatványon osztója,

v < w_{j} (j = 1, ..., h)

. Ekkor

\begin{matrix} T_{n + 1} = \frac{q_{1}^{w_{1} - v_{1}} ... q_{h}^{w_{h} - v_{h}}}{p_{1}^{t_{1} - u_{1}} ... p_{g}^{t_{g} - u_{g}}} T_{n} . \end{matrix}

(1)

Végtelen sok olyan

n

értékre van tehát szükségünk, amelyekre a

T_{n}

a jobb oldalon 1-nél kisebb számmal van megszorozva. Ehhez legegyszerűbb

n

-et úgy választani, hogy

n + 1

...

n + k - 1

egyikével se legyen 1-nél nagyobb közös osztója,

(n + k)

-nak viszont legalább az egyikükkel legyen. Ekkor a tört nevezője

n

lesz, a számlálója pedig legfeljebb

\frac{n + k}{2}

. A tört tehát nem nagyobb, mint

\frac{n + k}{2 n}

; ez pedig 1-nél kisebb, ha

n

nagyobb

k

-nál.

Ha végtelen sok

n

-re kielégítjük az első két feltételt, akkor közülük végtelen sok nagyobb is lesz mint

k

, tehát elég olyan

n

egészeket keresnünk, amelyekre

n

relatív prím az

n + 1

...

n + k - 1

számokhoz,

n + k

pedig legalább egyikhez nem relatív prím. A feladatot megoldó versenyzők mind ezt az utat választották, de az

n

kívánt tulajdonságait igen különböző, módokon biztosították. Bemutatjuk a lényegében legegyszerűbbnek látszót.
Ha valamilyen

j

-re

n

-nek és

(n + j)

-nek van 1-nél nagyobb közös osztója, akkor ez közös osztója

n

és

(n + j) - n = j

-nek is és megfordítva is:

n

és

j

közös osztói

(n + j)

-nek is osztói. Azt kell tehát elérnünk, hogy kiválasztandó számaink az

\begin{matrix} 1, 2, ..., k - 1 \end{matrix}

(*)

számokhoz relatív prímek legyenek, tehát például a szorzatukhoz is. Ezzel a tulajdonsággal rendelkeznek az^{$^{*}$}

\begin{matrix} 1 \cdot 2 \cdot ... \cdot (k - 1) \end{matrix}

szorzat többszöröseinek a szomszédai, tehát a

c ((k - 1)!) \pm 1

számok.

Ahhoz, hogy a

k

-val nagyobb

c ((k - 1)!) + k \pm 1

a (*) alatti számok valamelyikéhez ne legyen relatív prím, a kettős előjelből a negatívat célszerű választani. Ez esetben a

k

-val növelt szám osztható (

k - 1

)-gyel, és az (

n + 1

)-ként adódó

c ((k - 1)!)

is osztható (

k - 1

)-gyel.
Ha tehát az

\begin{matrix} n_{c} = c ((k - 1)!) - 1 \end{matrix}

számokat választjuk, az (1) egyenlőség nevezője

n_{c}

lesz, számlálója pedig legfeljebb

\begin{matrix} \frac{n_{c} + k}{k - 1} . \end{matrix}

Így

\begin{matrix} T_{n_{c} + 1} \leq \frac{n_{c} + k}{(k - 1) n_{c}} T_{n_{c}} . \end{matrix}

Itt

k - 1 \geq 2

, mert a feladat feltétele szerint

k > 2

. Ha tehát

n_{c} > k

is teljesül (ami

k = 3

-nál

c \geq 3

-ra,

k > 3

esetén minden pozitív egész

c

-re igaz), akkor

\begin{matrix} \frac{n_{c} + k}{(k - 1) n_{c}} < 1, tehát T_{n_{c} + 1} < T_{n_{c}} . \end{matrix}

Ezzel a feladat állítását igazoltuk.

Megjegyezzük, hogy

k = 2

-re nem igaz a feladat állítása,

[n, n + 1] = n (n + 1)

és ez növekvő

n

-nel állandóan növekszik.

Megjegyzések. 1. A lkkt-nek a megoldás elején ismertetett megadásmódja ismét az első feladathoz fűzött 3. megjegyzésben említett számelmélet alaptételéből következik.

2. Egy versenyző

(k - 1)

! helyett a lényegesen kisebb

[1, 2, ..., k - 1]

számot használta, de elég lett volna ehelyett a

k

-nál kisebb prímek szorzatát venni, amint azt könnyen beláthatja az olvasó. Összehasonlításul már

k = 21

-re

(k - 1)

! felette van a 4700 billiónak,

[1, 2, ..., k - 1]

közel

233, 3

millió, a prímek szorzata pedig valamivel

9, 7

millió alatt van.

II. Megoldás. Megkaphatjuk az

[n, n + 1, ..., n + k - 1]

lkkt-t úgy is, hogy az

n (n + 1) ... (n + k - 1)

szorzatot elosztjuk bizonyos számokkal, tehát

\begin{matrix} [n, n + k, ..., n + k - 1] = \frac{n (n + 1) ... (n + k - 1)}{v_{n, k}} \end{matrix}

(2)

alakban, ahol

v_{n, k}

természetes szám.
Mielőtt ennek helyességét belátnánk, nézzük meg, hogyan alakul ennek felhasználásával a feladat állításában szereplő egyenlőtlenség. A megfelelő kifejezéseket beírva, kézenfekvő átalakításokkal az

\begin{matrix} n v_{n + 1, k} > (n + k) v_{n, k} \end{matrix}

vagy

\begin{matrix} n (v_{n + 1, k} - v_{n, k}) > k v_{n, k} \end{matrix}

(3)

adódik. A bal oldalnak pozitívnak kell lennie, amihez

\begin{matrix} v_{n + 1, k} > v_{n, k} \end{matrix}

(4)

szükséges. Ha ez fennáll, akkor az utolsó egyenlőtlenség bizonyosan teljesül, ha maga

n

nagyobb a jobb oldalnál, mert a szorzója legalább 1.

Ezek alapján a feladat állítása következik abból, ha megmutatjuk, hogy

a) Minden adott

k

-ra

v_{n, k}

egy csak

k

-tól függő korlátnál nem nagyobb, és
b) ha

k \geq 3

, adott, akkor

v_{n, k}

értéke végtelen sokszor változik.

Valóban a b) szerinti változás nem lehet valamilyen határon túl mindig csökkenés, hiszen

v_{n, k}

-nak mindig pozitív egésznek kell lennie, de nem lehet valamilyen értéken túl mindig növekedés sem, hiszen akkor

v_{n, k}

minden korláton túlnőne, ami a) miatt nem lehet. Van tehát végtelen sok olyan

n

, amelyre (4) teljesül.
Legyen

V

egy olyan érték, aminél

v_{n, k}

sohasem nagyobb, akkor mindazokra az

n

-ekre, amikre (4) teljesül és amelyek

k V

-nél nagyobbak, igaz, hogy

\begin{matrix} n (v_{n + k - 1} - v_{n, k}) > k V \geq k v_{n, k}, \end{matrix}

tehát teljesül (3), abból pedig a feladat állításában szereplő egyenlőtlenség ekvivalens átalakításokkal következik.
A feladat állításának bizonyításához tehát elég a (2) alakú előállítás létezését bizonyítani (egész nevezővel) és a nevező a) és b) tulajdonságát.
A (2) felbontáshoz eljuthatunk úgy, hogy leírjuk egyenként a számláló tényezőit és

n + j

leírása után

(1 \leq j \leq k - 1)

nézzük annak prímszámhatványok szorzatára bontott alakját. Ha van a prím alapok közül valamelyiknek korábban is többszöröse, akkor veszünk egy olyan

n + i (0 \leq i < j)

tényezőt, amelyik az illető prím legnagyobb hatványával osztható, és ha ez a hatvány nem nagyobb az

(n + j)

-ben szereplő hatványnál, akkor a nevezőbe írjuk, különben az

(n + j)

-ben fellépő hatványt írjuk a nevezőbe. Világos, hogy így a

k

-adik lépésben megkapjuk a keresett lkkt-t.

v_{n, k}

a nevezőbe került prímhatványok szorzata.
A nevezőbe írt prímszámhatvány osztója

(n + i)

-nek is,

(n + j)

-nek is, tehát a különbségüknek

j - i

-nek is, ami pozitív és nem nagyobb

j

-nél. Az

n + j

sorravételénél tehát a

j

j - 1

...

, 2 bizonyos prímszámhatvány osztóival osztunk, tehát összességében nem nagyobb számmal, mint

j

! Ezt

j = 1, 2, ..., (k - 1)

-re alkalmazva kapjuk, hogy

\begin{matrix} v_{n, k} \leq 2! 3! ... (k - 1)!, \end{matrix}

v_{n, k}

csak véges sok értéket vesz fel.^{$^{*}$} Ezzel beláttuk a (2) alakú felbontás létezését és az a) állítást. Igazoljuk még b)-t.
Világos, hogy

v_{n,2} = 1

minden

n

-re.
Legyen

p

egy

k

-nál kisebb prímszám, amelyik nem osztója

k

-nak. ‐ Ilyenek pl. a

k - 1 (\geq 2)

prímosztói. ‐ Válasszuk

n

-et úgy, hogy

n + k

többszöröse legyen

p

-nek, és vizsgáljuk

p

kitevőjét

v_{n, k}

és

v_{n + 1, k}

prímhatványok szorzatára bontott alakjában.
Nem lehet

n

is többszöröse

p

-nek, mert különben az

(n + k) - n = k

is osztható volna

p

-vel, ellentétben

p

választásával.
Mivel

p < k

, van többszöröse az

n + 1

n + 2

...

n + k - 1

számok közt. Ha áttérünk

[n, n + 1, ..., n + k - 1]

-ről

[n + 1, ..., n + k - 1, n + k]

-ra, akkor a (2) jobb oldalának számlálójából elmarad a

p

-vel nem osztható

n

tényező és megjelenik a

p

-vel osztható

n + k

. Világos, hogy

n

elhagyása a

p

kitevőjét nem befolyásolja, viszont

n + k

hozzávétele után az előállításra vonatkozó gondolatmenetet követve látható, hogy a nevezőbe kell írnunk

p

-nek valamilyen hatványát.

v_{n + 1, k}

tehát

p

-nek magasabb hatványával osztható, mint

v_{n, k}

, s így (függetlenül esetleges egyéb különbségektől) különböző számok, mivel a számok prímhatványokra történő felbontása lényegében egyértelmű.

Megjegyzések. 1. Az I. megoldás során több módon is megadtunk adott

k

-hoz végtelen sok olyan

n

értéket, amire teljesül a

T_{n} < T_{n + 1}

egyenlőtlenség, de távolról sem adtuk meg az összes ilyen

n

-et. Ez reménytelenül nehéz feladatnak is látszik. ^{$^{*}$} Belátható, hogy a legkisebb

n

is, ami ott adódik, sokkal nagyobb

k

-nál.
Jelöljük

n_{k}

-val adott

k

-hoz a legkisebb olyan

n

-et, amire teljesül a

T_{n} < T_{n + 1}

egyenlőtlenség. Néhány értéket a következő táblázat mutat:

\begin{matrix} k & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 29 & 30 & 31 & 32 & 210 \\ n_{k} & - & 5 & 5 & 7 & 9 & 8 & 11 & 11 & 11 & 13 & 13 & 17 & 16 & 17 & 17 & 31 & 47 & 32 & 37 & 237 \end{matrix}

Láthatólag ezek az értékek alig nagyobbak

k

-nál. Az világos, hogy

n_{k}

-nak

k

-nál nagyobbnak kell lennie, mert ha

n \leq k

, akkor az

n + 1, ..., n + k

között van

n

-nel osztható, hiszen

2 n \leq n + k

. Így

[n + 1, ..., n + k]

osztható

n

-nel, és természetesen

n + 1, ..., n + k - 1

-gyel is, tehát

[n, ..., n + k - 1]

osztója

[n + 1, ..., n + k]

-nak, amiből következik, hogy nem lehet az előbbi nagyobb.
A prímszámok eloszlására vonatkozó mély tételek segítségével belátható, hogy

n_{k} / k

tetszés szerinti 1-nél nagyobb

h

számnál kisebb lesz, amint

k

egy alkalmas (

h

-tól függő) korlátnál nagyobb.
2. Számolás közben sok olyan

n

-re találunk, amelyre

[n, ..., n + k - 1] = [n + 1, ..., n + k]

. Ez

n = k

-ra pl. csak akkor nem teljesül, ha

k

a 2-nek egy hatványa. De

k = 19

-re pl.

n = 19

-től

n = 22

-ig négy egymás utáni értékre teljesül az egyenlőség,

k = 210

-re, pedig

n = 213

-tól

n = 220

-ig nyolc egymás utáni esetben. Ezek után első pillanatra talán meglepően hat, hogy minden

k

-hoz legfeljebb véges sok esetben lehet két szomszédos lkkt egyenlő, pedig a (2) formula alapján ez legfeljebb az

\begin{matrix} n = \frac{k v_{n, k}}{v_{n + 1, k} - v_{n, k}} \end{matrix}

értékekre teljesül (és közülük az egész értékekre teljesül is). Mivel pedig

v_{n, k}

csak véges számú különböző értéket vehet fel, így csak véges számú megfelelő

n

létezik.

^{$^{*}$}Ezt a szorzatot "k-1 faktoriális"-nak nevezik és így jelölik: (

k - 1

^{$^{*}$}Belátható, hogy az is igaz, hogy $v_{n} \leq (k - 1)!$ pontosabban $v_{n, k} | (k - 1)!$ , és az egyenlőtlenségben végtelen sokszor az "='' jel érvényes.

^{$^{*}$} Figyeljük meg, hogy a II. megoldás csak végtelen sok ilyen $n$ létezését bizonyítja, anélkül, hogy megadna ilyen $n$ -eket. Annak a gondolatmenetnek az alapján csak a $v_{n, k}$ nevezők szerkezetének sokkal pontosabb ismerete tenné lehetővé ilyen $n$ -ek megadását.