Олимпиадная задача Кохась К. П. по принципу крайнего для 7-9 классов: таблица и звёздочки

  а) Вычеркнем n строк с наибольшим количеством звёздочек. Менее 2n звёздочек в них быть не может – это означало бы, что в одной из этих n строк не более одной звёздочки, тогда и в оставшихся n строках не более чем по одной звёздочке, так что всего звёздочек меньше чем  2n + n = 3n.  Итак, вычеркнуто не менее 2n звёздочек; оставшиеся (не более n) звёздочки можно убрать, вычеркнув соответствующие столбцы.

  б) Расставим звёздочки так, как показано на рисунке: 2n – по диагонали, ещё n – на пересечении i-й строки с (i+1)-м столбцом  (i = 1, 2, ..., n)  и последнюю – на пересечении (n + 1)-й строки с первым столбцом.

  Предположим, что удалось убрать все эти звёздочки, вычеркнувnстрок иnстолбцов. При этом на  n– 1  звездочку внизу уйдёт  n– 1  рядов (строк и столбцов), а на верхние звездочки останется  n+ 1 ряд.   Расставим по кругу  2n+ 2  буквыa₁,b₁,a₂,b₂, ...,a_n+1,b_n+1,  соответствующие столбцам и строкам, в указанном порядке и покрасим в красный цвет буквы, соответствующие вычеркнутым строкам и столбцам. Заметим, что из каждых двух рядом стоящих букв хотя бы одна – красная. Например, еслиb₁– не красная, то есть первая строка не вычеркнута, то должны был вычеркнуты первый и второй столбцы, то естьa₁иa₂– красные. Поскольку красных букв ровно  n+ 1,  то они должны стоять через одну. Это значит, что либо вычеркнута  n+ 1  строка, либо вычеркнут  n+ 1  столбец. Но разрешено вычеркнуть толькоnстрок (столбцов). Противоречие.

Ответ задачи отсутствует