Problem B. 5187. (September 2021)
B. 5187. A subset of the set \(\displaystyle S=\{1,2,\dots,n\}\) is called primitive, if it does not contain two elements such that one is a divisor of the other. Show that if it is not possible to add a further element of \(\displaystyle S\) to a particular primitive set \(\displaystyle A\subseteq S\) and keep it primitive, then either \(\displaystyle A=\{1\}\) or the size of \(\displaystyle A\) is greater than or equal to the number of primes up to \(\displaystyle n\).
Proposed by Cs. Sándor, Budapest
(6 pont)
Deadline expired on October 11, 2021.
Sorry, the solution is available only in Hungarian. Google translation
1. megoldás. Legyen \(\displaystyle \{1\}\ne A\subseteq S\) egy primitív részhalmaz, amelyhez már nem vehető hozzá újabb \(\displaystyle S\)-beli elem úgy, hogy primitív maradjon. Megmutatjuk, hogy ekkor \(\displaystyle A\) elemszáma legalább annyi, mint \(\displaystyle n\)-ig a prímek száma, amit jelöljünk \(\displaystyle \pi(n)\)-nel.
Tetszőleges \(\displaystyle p\leq n\) prím esetén jelölje \(\displaystyle \alpha_p\) a legnagyobb olyan egész kitevőt, melyre \(\displaystyle p^{\alpha_p}\leq n\). A feltétel alapján \(\displaystyle p^{\alpha_p}\) vagy eleme \(\displaystyle A\)-nak, vagy nem vehető hozzá. Utóbbi esetben \(\displaystyle A\) már tartalmazza \(\displaystyle p^{\alpha_p}\) egy osztóját (ez csak egy 1-nél nagyobb \(\displaystyle p\)-hatvány lehet) vagy egy többszörösét (ez biztosan nem prímhatvány). Ha \(\displaystyle p^{\alpha_p}\in A\), akkor legyen \(\displaystyle a_p=p^{\alpha_p}\); ha \(\displaystyle p^{\alpha_p}\) valamely (valódi) osztója van \(\displaystyle A\)-ban, akkor legyen \(\displaystyle a_p\) ez az osztó; végül, ha többszöröse található \(\displaystyle A\)-ban, akkor legyen \(\displaystyle a_p\) egy ilyen \(\displaystyle A\)-beli többszörös.
Azt fogjuk igazolni, hogy az \(\displaystyle n\)-nél kisebb prímekhez ily módon rendelt \(\displaystyle A\)-beli \(\displaystyle a_p\) elemek páronként különbözők, ez igazolja állításunkat, miszerint \(\displaystyle |A|\geq \pi(n)\).
Világos, hogy az \(\displaystyle a_p\) elemek közötti prímhatványok egymástól és a többi, nem prímhatvány \(\displaystyle a_q\) elemtől is különböznek, hiszen különböző prímek (pozitív kitevős) hatványai. Így elég belátni, hogy ha \(\displaystyle p< q\) prímekre \(\displaystyle p^{\alpha_p}\mid a_p\) és \(\displaystyle q^{\alpha_q}\mid a_q\), akkor \(\displaystyle a_p\ne a_q\). Ellenkező esetben, felhasználva, hogy \(\displaystyle p,q\) különböző prímek, azt kapnánk, hogy \(\displaystyle a_p=a_q\) osztható a \(\displaystyle p^{\alpha_p}q^{\alpha_q}\) szorzattal, amelynek értéke azonban \(\displaystyle \alpha_p\) definíciója szerint \(\displaystyle n\)-nél nagyobb:
\(\displaystyle p^{\alpha_p}q^{\alpha_q}\geq p^{\alpha_p}q> p^{\alpha_p+1}>n,\)
ez viszont ellentmond annak, hogy \(\displaystyle 1\leq a_p\leq n\).
Ezzel igazoltuk a feladat állítását.
2. megoldás. Az előző megoldás jelöléseit (\(\displaystyle \pi(n),\alpha_p\)) használjuk.
Legyen most is \(\displaystyle \{1\}\ne A\subseteq S\) egy primitív részhalmaz, amihez már nem vehető hozzá újabb \(\displaystyle S\)-beli elem úgy, hogy primitív maradjon.
Ha \(\displaystyle p\leq n\) prímszám, akkor legyen
\(\displaystyle A_p := \{ a \in A : a \text{ legnagyobb prímosztója } p\}.\)
Megmutatjuk, hogy ha valamely \(\displaystyle p\leq n\) prímre \(\displaystyle A_p\) üres lenne, akkor \(\displaystyle p^{\alpha_p}\) hozzávehető lenne \(\displaystyle A\)-hoz. Mivel \(\displaystyle A\ne \{1\}\), ezért \(\displaystyle 1\notin A\), így \(\displaystyle p^{\alpha_p}\)-nek nem lehet osztója \(\displaystyle A\)-ban, hiszen egy ilyen osztó 1-nél nagyobb \(\displaystyle p\)-hatványként \(\displaystyle A_p\)-be került volna. Többszöröse szintén nem lehet \(\displaystyle A\)-ban, mert akkor lenne egy olyan \(\displaystyle p^{\alpha_p}\)-vel osztható \(\displaystyle a\in A\) elem, amelynek \(\displaystyle q>p\) prímosztója is van, azonban \(\displaystyle p^{\alpha_p}q>p^{\alpha_p+1}>n\) miatt ez nem lehetséges.
Tehát minden \(\displaystyle p\leq n\) prímre \(\displaystyle A_p\) nemüres részhalmaza \(\displaystyle A\)-nak, az \(\displaystyle A_p\) halmazok definíciója alapján világos, hogy páronként diszjunktak, így \(\displaystyle |A|\geq \pi(n)\).
Megjegyzés. Cameron és Erdős fogalmazta meg azt a sejtést, hogy az \(\displaystyle \{1,2,\dots,n\}\) halmaz primitív részhalmazainak \(\displaystyle f(n)\) számára az \(\displaystyle f(n)^{1/n}\) sorozat konvergens. Ezt a sejtést nemrég igazolták, és azóta olyan módszer is született, mellyel \(\displaystyle f(n)^{1/n}\) határértéke is meghatározható (\(\displaystyle \approx 1.57)\). Az viszont jelenleg sem ismert, hogy egy primitív halmaz átlagos mérete mekkora. A kitűzött feladat arról szólt, hogy egy nem bővíthető primitív halmaz vagy az \(\displaystyle \{1\}\) halmaz vagy legalább \(\displaystyle \pi(n)\) elemű.
Statistics:
72 students sent a solution. 6 points: Barát Benedek, Baski Bence, Ben Gillott, Bényei Borisz, Berkó Sebestyén , Bognár 171 András Károly, Christ Miranda Anna, Czanik Pál, Diaconescu Tashi, Duchon Márton, Fekete Richárd, Fülöp Csilla, Guthy Gábor, Jánosik Máté, Kalocsai Zoltán, Kercsó-Molnár Anita, Koleszár Domonkos, Lovas Márton, Melján Dávid Gergő, Mohay Lili Veronika, Móricz Benjámin, Nagy 551 Levente, Németh Márton, Nyárfádi Patrik, Páhán Anita Dalma, Rareș Polenciuc, Sági Mihály, Simon László Bence, Szemlér Bálint, Tóth 057 Bálint, Török Ágoston, Varga Boldizsár, Virág Rudolf, Wiener Anna. 5 points: Balogh Ádám Péter, Csonka Illés, Horváth Hanna Szabrina, Molnár István Ádám, Nádor Benedek, Seláf Bence, Tarján Bernát. 4 points: 5 students. 3 points: 2 students. 2 points: 3 students. 1 point: 12 students. 0 point: 7 students.
Problems in Mathematics of KöMaL, September 2021