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