A B. 5187. feladat (2021. szeptember)

B. 5187. Az \(\displaystyle S=\{1,2,\dots,n\}\) halmaz egy részhalmaza primitív, ha nincs benne két olyan elem, melyek közül az egyik osztója a másiknak. Mutassuk meg, hogy ha egy \(\displaystyle A\subseteq S\) primitív halmazhoz nem lehet úgy hozzávenni újabb \(\displaystyle S\)-beli elemet, hogy primitív maradjon, akkor vagy \(\displaystyle A=\{1\}\), vagy \(\displaystyle A\) mérete legalább annyi, mint \(\displaystyle n\)-ig a prímek száma.

Javasolta: Sándor Csaba (Budapest)

(6 pont)

A beküldési határidő 2021. október 11-én LEJÁRT.

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ű.

Statisztika:

72 dolgozat érkezett.
6 pontot kapott:	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 pontot kapott:	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 pontot kapott:	5 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	12 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2021. szeptemberi matematika feladatai