Az A. 884. feladat (2024. szeptember)

A. 884. Egy $\displaystyle n\times n$-es táblázatot kitöltünk valós számokkal úgy, hogy minden sorban és minden oszlopban 1 legyen a számok összege. $\displaystyle K$ mely értékeire igaz a következő állítás: ha a táblázatban szereplő negatív számok abszolút értékeinek összege legfeljebb $\displaystyle K$, akkor biztosan ki lehet választani $\displaystyle n$ pozitív számot a táblázatból úgy, hogy minden sorból és minden oszlopból pontosan egy számot válasszunk.

Javasolta: Bencsik Dávid, Budapest

(7 pont)

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

Tekintsük azt a páros gráfot, melyet a következőképpen kapunk: az $\displaystyle s_1$, $\displaystyle s_2$,..., $\displaystyle s_n$ csúcsok felelnek meg a soroknak, az $\displaystyle o_1$, $\displaystyle o_2$,..., $\displaystyle o_n$ csúcsok az oszlopoknak, és az $\displaystyle s_i$ és $\displaystyle o_j$ csúcsokat akkor köti össze egy él, ha a táblázat $\displaystyle i$-ik sorának és $\displaystyle j$-ik oszlopának találkozásánál lévő mezőben pozitív szám áll. A feladat feltételei pedig pontosan akkor teljesülnek, ha ebben a páros gráfban lehet találni egy teljes párosítást, azaz $\displaystyle n$ élt, melynek végpontjai között mind a $\displaystyle 2n$ pont szerepel.

A König-tétel alapján ennek a feltétele a következő: a gráf éleit nem lehet $\displaystyle n$-nél kevesebb csúccsal lefogni. Ezt a feltételt a táblázatra visszafogalmazva a következőt kapjuk: nem lehet a táblázatban kiválasztani $\displaystyle n$-nél kevesebb sort és oszlopot úgy, hogy a kiválasztott sorokon és oszlopokon kívül csak nempozitív elemek szerepeljenek. Ez a feltétel teljesül, ha $\displaystyle K<1$: ekkor ugyanis ha $\displaystyle n-1$ sorral és oszloppal lefoghatók lennének a pozitív elemek, akkor a táblázatban szereplő elemek összege legfeljebb az ezekben a sorokban és oszlopokban szereplő számok összege, ami $\displaystyle n-1$, mínusz azon elemek összege, melyeket kétszer számoltunk, azaz ezen sorok és oszlopok találkozásánál szerepelnek, vagyis legfeljebb $\displaystyle n-1+K<n$ lenne, ami ellentmondás, hiszen a táblázatban szereplő összes szám összege $\displaystyle n$, ugyanis minden sorban 1 az elemek összege.

Most mutassunk példát a $\displaystyle K\ge 1$ esetre, ha $\displaystyle n>2$: az első sor első $\displaystyle n-2$ mezőjébe írjunk $\displaystyle -1/(n-2)$-t, az utolsó két mezőbe pedig $\displaystyle 1$-et. Az összes többi sor első $\displaystyle n-2$ mezőjébe írjunk $\displaystyle 1/(n-2)$-t, az utolsó kettőbe pedig 0-t. Látható, hogy a pozitív elemek lefedhetők az első sorral és az első $\displaystyle n-2$ oszloppal, ami miatt nem teljesülhet a kiválasztási feltétel, és könnyen láthatóan 1 az összeg minden sorban és minden oszlopban, a negatív elemek összege pedig -1.

Végül könnyen látható, hogy $\displaystyle n=1$ és $\displaystyle n=2$ esetén mindig teljesíthetők a feladat feltételei.

Statisztika:

25 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Czanik Pál, Forrai Boldizsár, Holló Martin, Prohászka Bulcsú, Szabó 721 Sámuel, Szakács Ábel, Varga Boldizsár, Vödrös Dániel László.
6 pontot kapott:	Bui Thuy-Trang Nikolett, Kocsis 827 Péter, Sánta Gergely Péter, Tamás Gellért, Virág Tóbiás.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	3 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2024. szeptemberi matematika feladatai