Kezdőlap


Feladat:	1971. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1973/január, 27 - 28. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Legnagyobb közös osztó, Számsorozatok, Konstruktív megoldási módszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1971/szeptember: 1971. évi Nemzetközi Matematika Diákolimpia 13. 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.

Jelöljük az adott sorozat $2^{n} - 3$ elemét $a_{n}$ -nel és egy, a követelménynek megfelelő részsorozat $k$ -adik elemét $b_{k}$ -val. (Megjegyezzük, hogy a kívánt részsorozat elemeinek összeállítása többféleképpen lehetséges.) Azt fogjuk megmutatni, hogy ha már találtunk a részsorozat céljára $k$ számú megfelelő elemet, és ezek $b_{1}, b_{2}, ..., b_{k}$ , akkor találhatunk hozzájuk olyan $b_{k + 1}$ -et, amely amazok mindegyikéhez relatív prím (és nagyobb náluk). Egyszerűbben így mondhatjuk a talált követelményt:

\begin{matrix} b_{k + 1} és a b_{1} \cdot b_{2} \cdot ... \cdot b_{k} \end{matrix}

szorzat relatív prímek.

b_{1}

és

b_{2}

szerepére megfelel mindjárt

b_{1} = a_{3} = 5

b_{2} = a_{4} = 13

. Így a

b_{1} b_{2} = s_{2}

szorzathoz relatív prím, nála nagyobb

a_{n}

-et keresünk

b_{3}

szerepére. Azt a kizáró követelményt, hogy (

2^{n} - 3

)-nak ne legyen közös osztója

s_{2}

-vel, azzal fogjuk biztosítani, hogy a (

2^{n} - 3

) közelében levő

c_{n} = a_{n} + 2 = 2^{n} - 1

szám legyen többszöröse

s_{2}

-nek. Ha ugyanis ez teljesül, akkor

a_{n}

és

s_{2}

bármely közös osztója egyszersmind

a_{n}

-nek és

c_{n}

-nek is közös osztója, tehát osztója ezek különbségének, a 2-nek is. Így, ha ez a közös osztó nagyobb volna 1-nél, akkor csak 2-vel lehetne egyenlő. Ámde

a_{n}

és

c_{n}

páratlan volta miatt ez lehetetlen, tehát

a_{n}

és

s_{2}

valóban relatív prímek. ‐ Ilyen feltétellel sikerül

a_{n}

-et találnunk.
Tekintsük az

a_{n}

sorozat első (

s_{2} + 1

) számú eleméhez, vagyis az

a_{2}, a_{3}, ...

a_{3 + s_{2}}

számokhoz azokat a (legkisebb nemnegatív)

r

maradékokat, amelyek az

s_{2}

-vel való osztásuknál rendre föllépnek. Így

0 \leq r \leq s_{2} - 1

, a lehetséges különböző maradékok száma

s_{2}

. A tekintetbe vett elemek száma pedig 1-gyel több, van tehát legalább kettő az elemek közt, amelyekre a maradék egyenlő. Jelöljük ezeket (vagy ha több van, két ilyet)

a_{t}

-vel és

a_{u}

-val

(u > t)

, eszerint

\begin{matrix} a_{u} - a_{t} = 2^{u} - 2^{t} = 2^{t} (2^{u - t} - 1), \end{matrix}

osztható

s_{2}

-vel; és mivel

s_{2}

páratlan, azért a zárójelbeli tényezőnek osztója:

2^{u - 1} - 1 = d s_{2}

, ahol

d

természetes szám. Így pedig az előrebocsátottak szerint

d s_{2} - 2 = 2^{u - t} - 3 = a_{u - t}

-nek nincs közös osztója

s_{2}

-vel, tehát lehet

b_{3} = a_{u - t}

.
Eljárásunk alkalmas

b_{1}, b_{2}, ..., b_{k}

-hoz megfelelő

b_{k + 1}

keresésére is,

s_{2}

helyére a

b_{1} \cdot b_{2} \cdot ... \cdot b_{k} = s_{k}

szorzatot véve, hiszen az

s_{2}

-re mondottak érvényesek

s_{k}

-ra is és nem használtuk ki, hogy

s_{2}

-ben éppen 2 elemét szoroztuk össze a részsorozatnak. ‐ Ezzel feladatunkat megoldottuk.

Megjegyzések. 1. Vehettük volna

b_{3}

szerepére a következőket is:

\begin{matrix} 2 d s_{2} - 1 = 2^{u - t + 1} - 3 = a_{u - t + 1}, \\ 4 d s_{2} + 1 = 2^{u - t + 2} - 3 = a_{u - t + 2}, \end{matrix}

hiszen két szomszédos természetes szám mindig relatív prím egymáshoz, és ha

2 c s_{2}

nek, ill.

4 c s_{2}

-nek nincs közös osztója

b_{3}

-mal, akkor

s_{2}

-nek sincs.
2. Szemléletesen szólva: annak, hogy az

a_{n}

sorozatra igaz a feladat állítása, hogy tehát az

a_{n}

sorozatban ,,sok'' relatív prím szám van, az az oka, hogy

c_{n} = a_{n} + 2

sorozatban ,,sok'' nem relatív prím számpár van. Az utóbbi állítás pontos alakja a következő: tetszőleges páratlan

s

számhoz van olyan

n

index, hogy

c_{n}

osztható

s

-sel.