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

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


A KöMaL 2021. decemberi matematika feladatai