Feladat:	B.3378	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Bákor Krisztina ,  Balka Richárd ,  Csikvári Péter ,  Csóka Endre ,  Deli Lajos ,  Dénes Attila ,  Gerencsér Balázs ,  Keszegh Balázs ,  Kunszenti-Kovács Dávid ,  Máthé András ,  Papp Dávid ,  Rácz Béla András ,  Somogyi Dávid ,  Szalay Zsófia ,  Venter György ,  Vörös László
Füzet:	2001/január, 30 - 32. oldal		PDF  |  MathML
Témakör(ök):	Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):	Feladatok: 2000/május: B.3378

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Képzeljük el, hogy a felvételi rendszer reformja miatt azoknak a felvételizőknek, akik egynél több egyetemre jelentkeznek, egyetempárokat kellene megjelölniük az erre a célra rendszeresített ,,dupla jelentkezési íveken". Aki persze nem akar továbbtanulni vagy pontosan tudja, mit akar, annak ilyesmivel nem kell vesződnie, de ha valaki például 4 egyetemre is jelentkezik, annak $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ dupla ívet kell kitöltenie. Egy diáknak így 0, 0, 1, 3, 6, illetve 10 dupla ívre van szüksége aszerint, hogy 0, 1, 2, 3, 4 vagy pedig 5 egyetemre jelentkezik. Mindenképpen igaz tehát, hogy aki $e$ helyre jelentkezik, az legalább $2e-3$ dupla ívet tölt ki. Ha az osztályba $n$ diák jár, akik rendre $e_1$, $e_2$, $\text{...}$, $e_n$ egyetemre jelentkeznek, akkor a fentiek szerint összesen legalább $\sum _{i=1}^{n}2e_i-3=2\sum _{i=1}^n{e}_i-3n$ dupla ívet írnak meg. Vizsgáljuk most a $\sum _{i=1}^n{e}_i$ összeget. Ez az összes jelentkezések száma, amit ha egyetemenként számolunk össze, akkor legalább $5\frac{n}{2}$-t kapunk, hiszen a feltétel szerint minden egyetemre legalább az osztály fele jelentkezett. A szükséges dupla ívek száma így legalább $2\sum _{i=1}^n{e}_i-3n\ge 2\cdot 5\frac{n}{2}-3n=2n$. Az összesen 10 egyetempárra így legalább $2n$ dupla ív érkezik, van tehát olyan egyetempár, ahová ennek legalább az egytizede, $\frac{n}{5}$, és ezt kellett bizonyítani.  Csóka Endre (Debrecen, Fazekas M. Gimn., 9. o.t.)   II. megoldás. Legyen az osztály létszáma $n$, és jelölje $s_i$ azoknak a számát, akik pontosan $i$ darab egyetemre jelentkeztek. Ha most $T$ a továbbtanulni szándékozók, $J$ pedig az egyetemi jelentkezések száma, akkor nyilván $T=s_1+s_2+s_3+s_4+s_5\le n$, másfelől $J=s_1+2s_2+3s_3+4s_4+5s_5$, ami a feltétel szerint legalább $5\frac{n}{2}$. Az egyszerűség kedvéért jelölje $k$ a $k$-adik egyetemet ($k=1$, 2, 3, 4, 5), az egyetemek egy tetszőleges $H$ részhalmazára pedig $e_H$ azon diákok számát, akik pontosan a $H$-beli egyetemekre jelentkeztek. Így azoknak a diákoknak a száma, akik jelentkeztek $H$-beli egyetemekre: $\sum _{H\subseteq G}^{}{e}_G=E_H$. (A szóban forgó halmazok valamennyien az $\{$1, 2, 3, 4, $5\}$ halmaz részhalmazai.) Ekkor $\begin{array}{c}{\displaystyle E_{12}=e_{12}+\left(e_{123}+e_{124}+e_{125}\right)+\left(e_{1234}+e_{1235}+e_{1245}\right)+e_{12345}\mathrm{,}}\end{array}$ ennyien jelentkeztek tehát az 1 és a 2 egyetemre. Még kilenc hasonló összeget írhatunk fel, $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle E_{13}=e_{13}+\left(e_{132}+e_{134}+e_{135}\right)+\left(e_{1324}+e_{1325}+e_{1345}\right)+e_{13245}\mathrm{,}}\\ \hfill {\displaystyle ⋮}\\ \hfill {\displaystyle E_{45}=e_{45}+\left(e_{451}+e_{452}+e_{453}\right)+\left(e_{4512}+e_{4513}+e_{4523}\right)+e_{45123}\mathrm{.}}\end{array}}}\end{array}$ Azt kell bizonyítanunk, hogy e tíz összeg között van olyan, amelyiknek az értéke legalább $\frac{n}{5}$, ez pedig következne abból, ha e tíz összeg $E$ összege ‐ amelyik szimmetrikus lévén könnyebben kezelhető ‐ legalább ennek 10-szerese, azaz legalább $2n$. Vizsgáljuk tehát az $E$ összeget. Egy adott $e_G$ tagot a $G$ minden kételemű $\left\{i\mathrm{,}j\right\}$ részhalmazához felírt $E_{ij}$ összeg tartalmaz, mégpedig pontosan egyszer. Eszerint az $E$ összegben pontosan $\left(\genfrac{}{}{0ex}{}{|G|}{2}\right)$ alkalommal fordul elő az $e_G$ tag. Így $\begin{array}{c}{\displaystyle E=\sum _{|G|=2}^5\left(\genfrac{}{}{0ex}{}{|G|}{2}\right)\cdot e_G=\sum _{|G|=2}^{}{e}_G+3\sum _{|G|=3}^{}{e}_G+6\sum _{|G|=4}^{}{e}_G+10\sum _{|G|=5}^{}{e}_G\mathrm{.}}\end{array}$ Másfelől a $\sum _{|G|=i}^{}{e}_G$ összeg éppen azoknak a diákoknak a száma, akik pontosan $i$ darab egyetemre jelentkeztek, korábbi jelölésünkkel $s_i$. Így az $\begin{array}{c}{\displaystyle E=s_2+3s_3+6s_4+10s_5}\end{array}$ egyenlőséget kapjuk, erről az összegről kell megmutatnunk, hogy legalább $2n$. Rendelkezésünkre állnak a $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{ccc}\hfill {\displaystyle T}& {\displaystyle \le n}\hfill & \hfill {\displaystyle \text{(1)}}\\ \multicolumn{3}{c}{\text{<br>és a}}\\ \hfill {\displaystyle J}& {\displaystyle \ge \frac{5}{2}n}\hfill & \hfill {\displaystyle \text{(2)}}\end{array}}}\end{array}$ feltételek, ebből kell bebizonyítanunk, hogy $E\ge 2n$. Tekintsük az (1) szerint nyiván teljesülő $\frac{3}{2}n+\frac{1}{2}E\ge \frac{3}{2}T+\frac{1}{2}E$ egyenlőtlenséget. Ennek jobb oldala $\mathrm{1,5}{s}_1+2s_2+3s_3+\mathrm{4,5}{s}_4+\mathrm{6,5}{s}_5$, ami nyilván nagyobb vagy egyenlő, mint $J=s_1+2s_2+3s_3+4s_4+5s_5$. Így (2) miatt $\frac{3}{2}n+\frac{1}{2}E\ge J\ge \frac{5}{2}n$, ahonnan rendezés után valóban $E\ge 2n$ adódik. Ezzel a bizonyítást befejeztük.  Dénes Attila (Békéscsaba, Rózsa F. Gimn., 12. o.t.)   Megjegyzések. 1. Mindkét megoldásból kiderül, hogy a feladat állítása éles. Egyenlőség pontosan akkor lehetséges, ha valamennyi becslésben egyenlőség van, senki nem jelentkezik 0, 1, 4 vagy 5 egyetemre, és az osztály tanulóinak pontosan a fele jelentkezik minden egyes egyetemre. 2. Az $s_i$ változók segítségével megfogalmazott feladat: keressük az $s_2+3s_3+6s_4+10s_5$ összeg minimumát az $s_1+s_2+s_3+s_4+s_5\le n$ és az $s_1+2s_2+3s_3+4s_4+5s_5\ge \frac{5}{2}n$ feltételek mellett mutatja, hogy a feladatnak ez a része az ún. lineáris programozás témakörébe tartozik. 3. Érdemes egybevetni a két megoldást. A másodikban a szerző szemmel láthatólan nem használta ki, hogy a feladat egy osztály tanulóiról szól, az $n$-nel való osztás után a megoldás szó szerint alkalmazható bármely halmazra és annak részhalmazaira, amennyiben a részhalmazokhoz mérőszámot ‐ például területet ‐ rendelünk. Ez a mérőszám a feladatban a halmazok elemszáma, az első megoldás kombinatorikai megközelítésében alapvető volt, hogy a szóban forgó halmazok végesek. A feladat állítása a második megoldás szerint nem csak ekkor igaz, tehát például a következő állítást is igazolta a szerző: Egy egységnyi területű zsákon öt folt található, amelyek bármelyikének a területe legalább $\frac{1}{2}$. Mutassuk meg, hogy van a foltok között kettő, amelyek közös részének területe legalább $\frac{1}{5}$. Ennek a feladatnak a megoldásáról és lehetséges általánosításairól szól I. M. Jaglomnak a Kvant című folyóiratban megjelent klasszikus cikke, amelynek fordítását számunk 10‐20. oldalán közöljük.