Разделы 
Дополнительно
Задача по математике - 1927
2019-01-22 
В некоторых клетках доски $2n \times 2n$ стоят черные и белые фишки. С доски сначала снимаются все черные фишки, которые стоят в одной вертикали с какой-то белой, а затем все белые фишки, стоящие в одной горизонтали с какой-нибудь из оставшихся черных. Докажите, что либо черных, либо белых фишек на доске осталось не более $n^2$.
Решение:
Заметим, что в конце никакие две разноцветные фишки не стоят ни в одной строке, ни в одном столбце. Действительно, если исходно черная фишка стояла в одном столбце с белой, то ее сняли в первый раз, а если после первого снятия белая фишка стоит в одной строке с черной, то ее сняли во второй раз.
Пусть в конце черные фишки стоят в $a$ строках и $b$ столбцах, тогда белые могут стоять не более, чем в $2n - a$ строках и $2n - b$ столбцах. Но тогда черных фишек не более $ab$, а белых не более $(2n - a)(2n - b)$. Поскольку
$ab(2n - a)(2n - b) = a(2n - a)b(2n - b) \leq n^2 \cdot n^2 = n^4$,
то либо черных, либо белых фишек осталось не более $n^2$.
В некоторых клетках доски $2n \times 2n$ стоят черные и белые фишки. С доски сначала снимаются все черные фишки, которые стоят в одной вертикали с какой-то белой, а затем все белые фишки, стоящие в одной горизонтали с какой-нибудь из оставшихся черных. Докажите, что либо черных, либо белых фишек на доске осталось не более $n^2$.
Решение:
Заметим, что в конце никакие две разноцветные фишки не стоят ни в одной строке, ни в одном столбце. Действительно, если исходно черная фишка стояла в одном столбце с белой, то ее сняли в первый раз, а если после первого снятия белая фишка стоит в одной строке с черной, то ее сняли во второй раз.
Пусть в конце черные фишки стоят в $a$ строках и $b$ столбцах, тогда белые могут стоять не более, чем в $2n - a$ строках и $2n - b$ столбцах. Но тогда черных фишек не более $ab$, а белых не более $(2n - a)(2n - b)$. Поскольку
$ab(2n - a)(2n - b) = a(2n - a)b(2n - b) \leq n^2 \cdot n^2 = n^4$,
то либо черных, либо белых фишек осталось не более $n^2$.
