KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4392. (November 2011)

B. 4392. There are chessmen standing on a few fields of a 20×20 chessboard. A chessman can be removed from the board if at least one half of the fields in its row or column are vacant. What is the minimum number of chessmen needed for an appropriate arrangement such that no chessman can be removed from the board?

(3 pont)

Deadline expired on December 12, 2011.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

208 students sent a solution.
3 points:115 students.
2 points:23 students.
1 point:6 students.
0 point:64 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley