Az A. 803. feladat (2021. szeptember)

A. 803. Jelölje \(\displaystyle \pi (n)\) az \(\displaystyle n\)-nél nem nagyobb prímszámok számát. 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. Bizonyítsuk be, hogy ha \(\displaystyle n\ge 5\) és \(\displaystyle 1\le k <\frac{\pi (n)}{2}\), akkor az \(\displaystyle 1,2,\dots,n\) számok közül kiválasztható \(\displaystyle k+1\) elemű primitív halmazok száma legalább annyi, mint a \(\displaystyle k\)-eleműeké.

Javasolta: Sándor Csaba (Budapest)

(7 pont)

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

Megoldás. Adott \(\displaystyle 1<p\le n\) prímszámra legyen \(\displaystyle p^{k_p}\) a \(\displaystyle p\)-nek a legnagyob hatványa, amely nem nagyobb \(\displaystyle n\)-nél.

Először megmutatjuk, hogy egy \(\displaystyle 1<t\le n\) egész szám legfeljebb egy \(\displaystyle p\)-re lehet osztója vagy többszöröse \(\displaystyle p^{k_p}\)-nek. Valóban, ha \(\displaystyle t\) osztja valamilyen \(\displaystyle p\)-re \(\displaystyle p^{k_p}\)-t, akkor ő maga is a \(\displaystyle p\) hatványa (pozitív kitevős, mivel \(\displaystyle t\neq 1\)), akkor viszont a számelmélet alaptétele alapján nem lehet más \(\displaystyle q\)-ra sem osztója, sem többszöröse \(\displaystyle q^{k_q}\)-nek. Ha pedig \(\displaystyle p^{k_p}\)-nek és \(\displaystyle q^{k_q}\)-nak is többszöröse (tegyük fel, hogy \(\displaystyle p<q\) is teljesül), akkor (megint a számelmélet alaptétele és \(\displaystyle q>p\) alapján) \(\displaystyle t\ge p^{k_p}q^{k_q}>p^{k_p}\cdot p=p^{k_p+1}>n\), ami ellentmond a feltevésünknek.

Az eddigiek azt jelentik, hogy ha szeretnénk egy meglévő prímitív halmazt bővíteni egy új elemmel, akkor mindegyik meglévő elem legfeljebb egyet zár ki a \(\displaystyle p^{k_p}\) alakú számok közül.

Most az a célunk, hogy minden \(\displaystyle k\) elemű prímitív \(\displaystyle S\) halmazhoz hozzárendeljünk egyértelmű módon egy őt tartalmazó, \(\displaystyle k+1\) elemszámú prímitív halmazt.

Tekintsünk tehát egy \(\displaystyle k<\frac{\pi(n)}{2}\) elemű \(\displaystyle S\) prímitív halmazt, amely nem tartalmazza az \(\displaystyle 1\)-et. (Ez pl. \(\displaystyle k\ge 2\) esetén teljesül. A \(\displaystyle k=1\) esetet a megoldás végén vizsgáljuk.) Ekkor a \(\displaystyle \pi(n)\) darab \(\displaystyle p^{k_p}\) szám közül legfeljebb \(\displaystyle k\) darabot nem lehet kiválasztani. Jelöljük a ki nem választható prímhatványok halmazát \(\displaystyle T\)-vel. Az tehát a feladatunk, hogy a többi prímhatvány közül úgy válasszunk ki egyet \(\displaystyle S\)-hez, hogy abból az eredeti \(\displaystyle S\), azaz ekvivalens módon a \(\displaystyle T\) halmaz rekonstruálható legyen. A feladatunk tehát úgy is megfogalmazható, hogy van egy \(\displaystyle N(=\pi(n))\) elemű alaphalmazunk (a \(\displaystyle p^{k_p}\) prímhatványok halmaza), és annak egy \(\displaystyle k<\frac{N}{2}\) részhalmaza, melyhez hozzá kéne egyértelmű módon rendelni egy őt tartalmazó, eggyel nagyobb elemszámú részhalmazát az alaphalmaznak.

Ez pedig könnyen megmutatható a König-Hall tétel segítségével. Tekintsük azt a páros gráfot, amelynek csúcshalmaza az alaphalmaz \(\displaystyle k\) és \(\displaystyle k+1\) elemű részhalmazaiból áll, és egy él két olyan részhalmaz között fut, melyek közül az egyik tartalmazza a másikat (nyilvánvaló, hogy él csak \(\displaystyle k\) elemű és \(\displaystyle k+1\) elemű halmaz között futhat). A Hall-feltételt kell ellenőriznünk, azaz hogy ha van \(\displaystyle r\) darab \(\displaystyle k\) elemű részhalmazunk, ezek élszomszédainak darabszáma szintén legalább \(\displaystyle r\). Egy \(\displaystyle k\) elemű részhalmaz \(\displaystyle N-k\) darab másikkal van összekötve, míg egy \(\displaystyle k+1\) elemű részhalmaz \(\displaystyle k+1\) másikkal, így ha van \(\displaystyle r\) darab \(\displaystyle k\) elemű részhalmazunk, azok legalább \(\displaystyle r(N-k)/(k+1) \ge r\) másikkal élszomszédosak (mindegyik szomszédjukat legfeljebb \(\displaystyle k+1\)-szer számoljuk). Így tehát teljesül a Hall-feltétel, azaz a feladatot megoldottuk.

A \(\displaystyle k=1\) eset tárgyalása: 1-elemű prímitív halmazból \(\displaystyle n\) darab van, míg 2-eleműből is tudunk mutatni \(\displaystyle n\) darabot: könnyen ellenőrizhető, hogy ha \(\displaystyle n\ge 5\), akkor a \(\displaystyle \{2,x\}\), \(\displaystyle \{3,y\}\) és \(\displaystyle \{4,z\}\) alakú prímitív halmazokból legalább \(\displaystyle n\) darab van.

Statisztika:

18 dolgozat érkezett.
7 pontot kapott:	Bán-Szabó Áron, Jánosik Máté, Móricz Benjámin, Simon László Bence, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Ben Gillott, Berkó Sebestyén , Bognár 171 András Károly, Kovács 129 Tamás, Lovas Márton, Móra Márton Barnabás, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Török Ágoston.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.

A KöMaL 2021. szeptemberi matematika feladatai