A B. 5209. feladat (2021. december)

B. 5209. Egy \(\displaystyle 2022\) elemű, egészekből álló halmaznak legfeljebb hány olyan kételemű részhalmaza lehet, melyre a két elem összege szintén a halmazhoz tartozik?

(5 pont)

A beküldési határidő 2022. január 10-én LEJÁRT.

Megoldás. Legyen \(\displaystyle n=2022\). A 2-elemű részhalmazok száma \(\displaystyle \binom{n}{2}\), azt fogjuk meghatározni, hogy legalább hány olyan van köztük, melyek összege nem tartozik a halmazhoz. A kapott értéket \(\displaystyle \binom{n}{2}\)-ből kivonva a feladat kérdésére is választ kapunk majd.

Először mutatunk egy konstrukciót: legyen a halmaz

\(\displaystyle A:=\{-1010,-1009,\dots,-1,0,1,\dots,1010,1011\}.\)

Itt két elem összege csak akkor lehet a halmazon kívül, ha mindkettő pozitív, vagy mindkettő negatív.

Tekintsük először a pozitív esetet. Az \(\displaystyle m=1011\) jelölést bevezetve a pozitív elemek \(\displaystyle 1,2,\dots,m\). Az összegben lévő nagyobb összeadandó szerint számoljuk össze az \(\displaystyle m\)-nél nagyobb összegeket. Ha a nagyobb elem az \(\displaystyle m\), akkor mind az \(\displaystyle m-1\) esetben \(\displaystyle m\)-nél nagyobb összeget kapunk. Ha a nagyobb összeadandó az \(\displaystyle m-1\), akkor pontosan akkor kapunk \(\displaystyle m\)-nél nagyobb összeget, ha a kisebb a \(\displaystyle 2,3,\dots,m-2\) számok valamelyike, ami \(\displaystyle m-3\) lehetőség. Ezt folytatva, \(\displaystyle m-2,m-3,\dots,\frac{m+3}{2}\) esetén rendre \(\displaystyle m-5,m-7,\dots,2\) darab \(\displaystyle m\)-nél nagyobb összeget kapunk. Ha a nagyobb összeadandó legfeljebb \(\displaystyle \frac{m+1}{2}\), akkor biztos, hogy nem lesz \(\displaystyle m\)-nél nagyobb az összeg. Tehát a halmazon kívüli összegek száma (a számtani sorozatot összegezve) \(\displaystyle (m-1)+(m-3)+\dots+2=(m+1)(m-1)/4=(m^2-1)/4=255\,530\).

Ehhez hasonlóan \(\displaystyle k=1010\) mellett a negatív elemek \(\displaystyle -1,-2,\dots,-k\), és itt a halmazon kívüli összegek száma \(\displaystyle (k-1)+(k-3)+\dots+1=k^2/4=255\,025\).

Tehát a fenti \(\displaystyle A\) halmazon kívüli kéttagú összegek száma \(\displaystyle 255\,530+255\,025=510\,555\).

Most belátjuk, hogy ennyi halmazon kívüli összeg mindig keletkezik. Legyen \(\displaystyle A\) egy tetszőleges 2022 elemű egészekből álló halmaz. Az elemek előjele szerint bontsuk három részre: \(\displaystyle A=A^+\cup A^0 \cup A^-\), ahol \(\displaystyle A^+\) a pozitív elemekből álló halmaz, \(\displaystyle A^-\) a negatív elemekből álló halmaz, \(\displaystyle A^0\) pedig a 0-t tartalmazza, ha \(\displaystyle 0\in A\). (Elképzelhető, hogy \(\displaystyle A^+,A^0,A^-\) közül egy vagy két részhalmaz üres.) Legyen \(\displaystyle |A^-|=k,\ |A^0|=\ell,\ |A^+|=m\), itt \(\displaystyle k+\ell+m=n\) és \(\displaystyle \ell\in \{0,1\}\).

Tekintsük most \(\displaystyle A^+\)-t, a pozitív elemek halmazát, legyenek az elemei \(\displaystyle (0<)a_1<a_2<\dots<a_m\). Két \(\displaystyle A^+\)-beli elem összege pozitív, így ha nem \(\displaystyle A^+\)-beli, akkor nem is \(\displaystyle A\)-beli. Az \(\displaystyle a_i\) elem (\(\displaystyle 1\leq i\leq m\)) legfeljebb \(\displaystyle \lfloor (i-1)/2 \rfloor \)-féleképpen áll elő két \(\displaystyle A^+\)-beli elem összegeként, hiszen az \(\displaystyle a_i\)-t adó (kéttagú) összegek az \(\displaystyle a_1,a_2,\dots,a_{i-1}\) elemekből képzett (diszjunkt) párokat alkotnak. Tehát az \(\displaystyle a_1,a_2,a_3,a_4,\dots,a_m\) számok összegként legfeljebb rendre \(\displaystyle 0,0,1,1,\dots,\lfloor (m-1)/2 \rfloor\)-féleképpen állnak elő. Az előbb felsorolt számok összegét \(\displaystyle \binom{m}{2}\)-ből kivonva alsó becslést kapunk a halmazon kívüli összegek számára. Vegyük azonban észre, hogy \(\displaystyle a_1=1,a_2=2,\dots,a_m=m\) esetén minden becslésünk éles (az \(\displaystyle a_i=i\) szám pontosan \(\displaystyle \lfloor (i-1)/2 \rfloor \)-féleképpen áll elő minden \(\displaystyle i\)-re kéttagú összegként), így a számolást nem szükséges elvégezni, a korábbiak szerint a kapott becslés \(\displaystyle (m^2-\varepsilon(m))/4\) lesz, ahol \(\displaystyle \varepsilon(m)=0\), ha \(\displaystyle m\) páros, és \(\displaystyle \varepsilon(m)=1\), ha \(\displaystyle m\) páratlan (hiszen az \(\displaystyle 1,2,\dots,m\) számokat véve ennyi összeg nagyobb, mint \(\displaystyle m\)).

Ehhez teljesen hasonlóan, a negatív elemeknél a halmazon kívüli összegek száma legalább \(\displaystyle (k^2-\varepsilon(k))/4\).

Azt kaptuk tehát, hogy a halmazon kívüli összegek száma legalább

\(\displaystyle \frac14\left(m^2+k^2-\varepsilon(m)-\varepsilon(k)\right),\)

ahol \(\displaystyle k+m\in \{n-1,n\}\). Mostantól csak ezen feltételek mellett keressük az előbbi kifejezés minimumát. Ha \(\displaystyle k+m=n\), akkor \(\displaystyle k\) és \(\displaystyle m\) közül a nagyobbnak az értékét 1-gyel csökkentve csökken \(\displaystyle m^2+k^2-\varepsilon(m)-\varepsilon(k)\) értéke, hiszen például \(\displaystyle k\leq m\) esetén \(\displaystyle m^2-\varepsilon(m)>(m-1)^2-\varepsilon(m-1)\). Így feltehető, hogy \(\displaystyle k+m=n-1\), és mivel \(\displaystyle n=2022\) páros, ezért \(\displaystyle k\) és \(\displaystyle m\) közül az egyik páros, a másik páratlan. Ezek alapján

\(\displaystyle \frac14\left(m^2+k^2-\varepsilon(m)-\varepsilon(k)\right)=\frac18\left((m+k)^2+(m-k)^2-2\right) \geq \frac18\left((n-1)^2+1-2\right)=\frac{(n-1)^2-1}{8}=510\,555. \)

Tehát legalább \(\displaystyle 510\,555\) (kéttagú) összeg a halmazon kívül lesz, és mutattunk példát amikor pontosan ennyi összeg van a halmazon kívül.

Tehát az olyan 2-elemű részhalmazok száma, ahol az összeg a halmazhoz tartozik, legfeljebb \(\displaystyle \binom{2022}{2}-510\,555=1\,532\,676\).

Statisztika:

65 dolgozat érkezett.
5 pontot kapott:	Bálint Béla, Baski Bence, Bényei Borisz, Berkó Sebestyén , Czanik Pál, Diaconescu Tashi, Dienes Ervin Fotisz, Foris Dávid, Jánosik Máté, Kalocsai Zoltán, Kercsó-Molnár Anita, Koleszár Domonkos, Kurucz Kitti, László Anna, Melján Dávid Gergő, Mohay Lili Veronika, Móricz Benjámin, Nagy 429 Leila, Nagy 551 Levente, Németh Márton, Páhán Anita Dalma, Rareș Polenciuc, Sági Mihály, Somogyi Dalma, Szakács Ábel, Szemlér Bálint, Tarján Bernát, Tóth 057 Bálint, Varga Boldizsár, Wiener Anna.
4 pontot kapott:	Bencsik Dávid, Chrobák Gergő, Fazokán Marcell, Fekete Richárd.
3 pontot kapott:	9 versenyző.
2 pontot kapott:	12 versenyző.
1 pontot kapott:	6 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2021. decemberi matematika feladatai