|
|
 |
Условие
а) Докажите, что если в 3n клетках таблицы 2n×2n расставлены 3n звёздочек, то можно вычеркнуть n столбцов и n строк так, что все звёздочки будут вычеркнуты.
б) Докажите, что в таблице 2n×2n можно расставить 3n + 1 звёздочку так, что при вычеркивании любых n строк и любых n столбцов остаётся невычеркнутой хотя бы одна звёздочка.
Решение
а) Вычеркнем n строк с наибольшим количеством звёздочек. Менее 2n звёздочек в них быть не может – это означало бы, что в одной из этих n строк не более одной звёздочки, тогда и в оставшихся n строках не более чем по одной звёздочке, так что всего звёздочек меньше чем 2n + n = 3n. Итак, вычеркнуто не менее 2n звёздочек; оставшиеся (не более n) звёздочки можно убрать, вычеркнув соответствующие столбцы.
б) Расставим звёздочки так, как показано на рисунке: 2n – по диагонали, ещё n – на пересечении i-й строки с (i+1)-м столбцом (i = 1, 2, ..., n) и последнюю – на пересечении (n + 1)-й строки с первым столбцом.
Расставим по кругу 2n + 2 буквы a1, b1, a2, b2, ..., an+1, bn+1, соответствующие столбцам и строкам, в указанном порядке и покрасим в красный цвет буквы, соответствующие вычеркнутым строкам и столбцам. Заметим, что из каждых двух рядом стоящих букв хотя бы одна – красная. Например, если b1 – не красная, то есть первая строка не вычеркнута, то должны был вычеркнуты первый и второй столбцы, то есть a1 и a2 – красные. Поскольку красных букв ровно n + 1, то они должны стоять через одну. Это значит, что либо вычеркнута n + 1 строка, либо вычеркнут n + 1 столбец. Но разрешено вычеркнуть только n строк (столбцов). Противоречие.
Замечания
баллы: 4 + 4
