ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98006
Темы:    [ Таблицы и турниры (прочее) ]
[ Принцип крайнего (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
[ Доказательство от противного ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

а) Докажите, что если в 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)-й строки с первым столбцом.

  Предположим, что удалось убрать все эти звёздочки, вычеркнув n строк и n столбцов. При этом на  n – 1  звездочку внизу уйдёт  n – 1  рядов (строк и столбцов), а на верхние звездочки останется  n + 1 ряд.
  Расставим по кругу  2n + 2  буквы a1, b1, a2, b2, ..., an+1, bn+1,  соответствующие столбцам и строкам, в указанном порядке и покрасим в красный цвет буквы, соответствующие вычеркнутым строкам и столбцам. Заметим, что из каждых двух рядом стоящих букв хотя бы одна – красная. Например, если b1 – не красная, то есть первая строка не вычеркнута, то должны был вычеркнуты первый и второй столбцы, то есть a1 и a2 – красные. Поскольку красных букв ровно  n + 1,  то они должны стоять через одну. Это значит, что либо вычеркнута   n + 1  строка, либо вычеркнут  n + 1  столбец. Но разрешено вычеркнуть только n строк (столбцов). Противоречие.

Замечания

баллы: 4 + 4

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1989
выпуск
Номер 10
Задача
Номер М1190
олимпиада
Название Турнир городов
Турнир
Дата 1988/1989
Номер 10
вариант
Вариант весенний тур, основной вариант, 7-8 класс
Задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .