Kezdőlap


Feladat:	1991. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ujváry-Menyhárt Zoltán
Füzet:	1991/november, 338 - 339. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Skatulyaelv, Szitaformula, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1991/szeptember: 1991. é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.

Válasszuk ki az $S$ halmazból a $2$ , a $3$ , az $5$ és a $7$ többszöröseit. Ezek közül akárhogyan választunk ki 5 számot, lesz kettő, amelyek ugyanannak a prímnek a többszörösei, tehát nem relatív prímek. Az $S$ -ből kiválasztott elemek száma a szita-formula segítségével kiszámolva $216$ . Ezért a keresett $n$ egész legalább $217$ .
Bebizonyítjuk, hogy $n = 217$ esetén már teljesül a feltétel. Ehhez vizsgáljuk meg, hogy legfeljebb hány elem lehet $S$ -nek egy olyan részhalmazában, amelyben nincs $5$ olyan szám, amelyek páronként relatív prímek. A fent megadott $216$ elemű halmaz kiválasztásakor elhagytuk a prímek és az $1$ közül négy kivételével az összeset, a prímnégyzetek közül is négy kivételével az összeset, és ezeken kívül még hat darab két prím szorzataként felírható számot:

\begin{matrix} 11 \cdot 13 11 \cdot 23 11 \cdot 17 13 \cdot 17 11 \cdot 19 13 \cdot 19 \end{matrix}

Az eredeti feltételnek nem megfelelő bármely halmazban is a prímek és az

1

közül legfeljebb

4

lehet, különben lenne

5

szám, amelyek páronként relatív prímek, így ezek közül legalább annyit el kell hagyni, mint az előző példában. Ugyanez igaz a prímnégyzetekre is. Már csak az kell, hogy ezeken kívül még legalább 6 elemet el kell hagyni. Alább megadok 6 db 5 elemű diszjunkt halmazt, amelyek

S

részhalmazai, prímet és prímnégyzetet nem tartalmaznak, és mindegyikben páronként relatív prímek vannak, tehát mindegyik halmaznak legalább egy elemét el kell hagyni az

S

-ből ahhoz, hogy a feltétel ne teljesüljön.
A halmazok:

\begin{matrix} {2^{3}; 3^{3}; 5 \cdot 23; 7 \cdot 19; 11 \cdot 13} & {2^{6}; 3 \cdot 17; 5^{3}; 7 \cdot 13; 11 \cdot 23} \\ {2^{4}; 3^{4}; 5 \cdot 19; 7 \cdot 23; 11 \cdot 17} & {2^{7}; 3 \cdot 23; 5 \cdot 29; 7 \cdot 11; 13 \cdot 19} \\ {2^{5}; 3^{5}; 5 \cdot 13; 7 \cdot 17; 11 \cdot 19} & {2^{8}; 3 \cdot 19; 5 \cdot 11; 7 \cdot 29; 13 \cdot 17} \end{matrix}

Tehát, ha kiválasztunk

S

-ből egy 217 elemű halmazt, akkor az vagy tartalmaz egyet az előbbi 6 halmazból, vagy tartalmaz 5 prímet, vagy található benne 5 prímnégyzet. Ekkor van benne 5 szám, amelyek páronként relatív prímek. Tehát a keresett

n

szám a 217.