 |
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