|
|
 |
Условие
В некоторых клетках доски 2n×2n стоят чёрные и белые фишки. С доски сначала снимаются все чёрные фишки, которые стоят в одной вертикали с какой-то белой, а затем все белые фишки, стоящие в одной горизонтали с какой-нибудь из оставшихся чёрных. Докажите, что либо чёрных, либо белых фишек на доске осталось не более n².
Решение
Заметим, что в конце никакие две разноцветные фишки не стоят ни в одной строке, ни в одном столбце. Действительно, если исходно чёрная фишка стояла в одном столбце с белой, то ее сняли в первый раз, а если после первого снятия белая фишка стоит в одной строке с чёрной, то её сняли во второй раз. Пусть в конце чёрные фишки стоят в a строках и b столбцах, тогда белые могут стоять не более чем в 2n – a строках и 2n – b столбцах. Но тогда чёрных фишек не более ab, а белых не более (2n – a)(2n – b). Поскольку ab(2n – a)(2n – b) = a(2n – a)b(2n – b) ≤ n²·n² = n4, то либо чёрных, либо белых фишек осталось не более n².
