A B. 4392. feladat (2011. november)

B. 4392. A 20×20-as sakktábla néhány mezőjén bábu áll. Egy bábut akkor vehetünk le a tábláról, ha annak sorában vagy oszlopában a mezőknek legalább a fele üres. Legalább hány bábura van szükségünk ahhoz, hogy azokat alkalmasan elhelyezve egyiküket se lehessen levenni?

(3 pont)

A beküldési határidő 2011. december 12-én LEJÁRT.

Megoldás. Tegyük fel, hogy úgy helyeztünk el bábukat a táblán, hogy egyiket sem lehet levenni. A táblán legalább egy bábu áll; nézzünk ezek közül egyet. Ha ezt nem lehet levenni, akkor sorában legalább 11 bábu áll. Ha ezek egyikét sem lehet levenni, akkor mindegyikük oszlopában legalább 11 bábu áll, tehát legalább \(\displaystyle 11^2=121\) bábura szükség van. Ennyi elegendő is: ha például a tábla bal felső \(\displaystyle 11\times 11\)-es sarkát kitöltjük bábukkal, azok közül egyet sem lehet levenni.

Statisztika:

208 dolgozat érkezett.
3 pontot kapott:	115 versenyző.
2 pontot kapott:	23 versenyző.
1 pontot kapott:	6 versenyző.
0 pontot kapott:	64 versenyző.

A KöMaL 2011. novemberi matematika feladatai