Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

A B. 5187. feladat értékelése még nem fejeződött be.


A KöMaL 2021. szeptemberi matematika feladatai