Problem B. 5147. (January 2021)
B. 5147. Let \(\displaystyle k>1\) be a positive integer. Is there
\(\displaystyle a)\) a finite subset (of any size)
\(\displaystyle b)\) an infinite subset
of the set of positive integers in which the greatest common divisor of any \(\displaystyle k\) elements is greater than 1 but the greatest common divisor of any \(\displaystyle k+1\) elements is equal to 1?
Proposed by G. Mészáros, Budapest
(5 pont)
Deadline expired on February 15, 2021.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
84 students sent a solution. 5 points: 60 students. 4 points: 4 students. 3 points: 3 students. 2 points: 9 students. 1 point: 2 students. 0 point: 6 students.
Problems in Mathematics of KöMaL, January 2021