A B. 5147. feladat (2021. január)

B. 5147. Legyen $\displaystyle k>1$ pozitív egész szám. Megadható-e a pozitív egészek olyan

$\displaystyle a)$ tetszőlegesen nagy, véges

$\displaystyle b)$ végtelen
részhalmaza, melyben bármely $\displaystyle k$ elem legnagyobb közös osztója 1-nél nagyobb, továbbá bármely $\displaystyle k+1$ elem legnagyobb közös osztója 1?

Javasolta: Mészáros Gábor (Budapest)

(5 pont)

A beküldési határidő 2021. február 15-én LEJÁRT.

Megoldás. Azt fogjuk igazolni minden $\displaystyle k>1$-re, hogy tetszőlegesen nagy (véges) részhalmaz megadható, de végtelen részhalmaz nem.

Az a) rész megválaszolásával kezdjük. Legyen $\displaystyle n> k$ tetszőleges pozitív egész szám, megadunk $\displaystyle n$, a feltételeknek megfelelő számot. (A feladat megoldásához elég erre az esetre szorítkozni. Egyébként $\displaystyle n<k$ esetén bármely $\displaystyle n$ pozitív egész számra teljesülnek a feltételek, $\displaystyle n=k$ esetén pedig vehetünk például $\displaystyle k$ darab páros számot.) Mind az $\displaystyle n$ szám néhány különböző prímszám szorzata lesz. Válasszunk $\displaystyle \binom{n}{k}$ különböző prímszámot, és ezeket feleltessük meg az $\displaystyle \{1,2,\dots,n\}$ halmaz $\displaystyle k$ elemű részhalmazainak. Ha $\displaystyle H\subseteq \{1,2,\dots,n\}$ egy $\displaystyle k$ elemű részhalmaz, akkor a hozzá rendelt prímet jelölje $\displaystyle p_H$. Az $\displaystyle a_1,a_2,\dots,a_n$ számokat a következőképpen definiáljuk: $\displaystyle a_i$ legyen azon $\displaystyle p_H$ prímek szorzata, melyekre $\displaystyle i\in H$:

$\displaystyle a_i=\prod\limits_{i\in H\in \mathcal{H}} p_H,$

ahol $\displaystyle \mathcal{H}$ az $\displaystyle \{1,2,\dots,n\}$ halmaz $\displaystyle k$ elemű részhalmazainak halmaza.

Ily módon az $\displaystyle a_1,a_2,\dots,a_n$ különböző számok összes prímosztója a $\displaystyle p_H$ prímek közül kerül ki, és ezen prímek mindegyike az $\displaystyle a_1,a_2,\dots,a_n$ számok közül pontosan $\displaystyle k$-nak a prímtényezős felbontásában szerepel. Mivel nincs olyan prím, ami $\displaystyle k+1$ számot is osztana, ezért bármely $\displaystyle k+1$ szám legnagyobb közös osztója 1. Ha viszont csak $\displaystyle k$ számot választunk, akkor indexeik halmazát $\displaystyle H$-val jelölve, teljesül, hogy mindegyikük osztható $\displaystyle p_H$-val, vagyis legnagyobb közös osztójuk 1-nél nagyobb (nevezetesen $\displaystyle p_H$).

Most a b) résszel folytatjuk, belátjuk, hogy végtelen sok szám már nem adható meg a feltételeknek megfelelően. Az egyik kiválasztott szám prímosztóinak száma legyen $\displaystyle t$. Az összes többi szám osztható ezek közül legalább eggyel, különben lenne két szám, ami relatív prím, azonban $\displaystyle k>1$ alapján ez a pár kiegészíthető lenne egy $\displaystyle k$-assá (ha legalább $\displaystyle k$ számunk van), melyek legnagyobb közös osztója így 1 lenne, ellentétben a feltétellel. Tehát van $\displaystyle t$ darab prím úgy, hogy mindegyik szám osztható ezek közül legalább eggyel. Ha $\displaystyle n>kt$, akkor a skatulya-elv alapján a $\displaystyle t$ prím valamelyikével legalább $\displaystyle k+1$ szám osztható, melyek legnagyobb közös osztója így nem lehet 1. Ezért a megadott részhalmazban legfeljebb $\displaystyle kt$, vagyis csak véges sok elem szerepelhet.

2. megoldás a b) részre. Legyen $\displaystyle S$ a részhalmaz, célunk azt belátni, hogy $\displaystyle S$ véges. Ha $\displaystyle H\subseteq S$ egy $\displaystyle k$ elemű részhalmaz, akkor a $\displaystyle H$-beli elemek legnagyobb közös osztója, amit jelöljünk $\displaystyle m_H$-val, 1-nél nagyobb. Azt állítjuk, hogy az $\displaystyle m_H$ számok páronként relatív prímek. Ha ugyanis az $\displaystyle S$ halmaz két különböző $\displaystyle k$ elemű részhalmazára, $\displaystyle H$-ra és $\displaystyle H'$-re, $\displaystyle (m_H,m_{H'})>1$ lenne, akkor a $\displaystyle H\cup H'$ halmaz elemeinek legnagyobb közös osztója is 1-nél nagyobb lenne (nevezetesen $\displaystyle (m_H,m_{H'})$). Azonban $\displaystyle H\cup H'$ egy legalább $\displaystyle k+1$ elemű halmaz, így bármely $\displaystyle k+1$ elemű részhalmazára sérülne a feltétel. Ha most $\displaystyle a\in S$, akkor $\displaystyle a$ minden olyan $\displaystyle m_H$ számmal osztható, amelyre $\displaystyle a\in H\subseteq S$ és $\displaystyle |H|=k$. Csak véges sok ilyen $\displaystyle H$ létezhet, ezért $\displaystyle S$ is véges.

Statisztika:

84 dolgozat érkezett.
5 pontot kapott:	60 versenyző.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	9 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	6 versenyző.

A KöMaL 2021. januári matematika feladatai