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

Проект МЦНМО
при участии
школы 57
Задача 64528
Темы:    [ Шахматные доски и шахматные фигуры ]
[ Четность и нечетность ]
[ Процессы и операции ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

На каждой клетке доски 10×10 стоит фишка. Разрешается выбрать диагональ, на которой стоит чётное число фишек, и снять с неё любую фишку.
Какое наибольшее число фишек можно убрать с доски такими операциями?


Решение

  Назовём (не)чётной диагональ, на которой (в данный момент) стоит (не)чётное число фишек. После снятия фишки чётная диагональ становится нечётной, а нечётная – чётной. Поэтому число нечётных диагоналей не уменьшается. В начале на доске есть 20 нечётных диагоналей, значит, и в конце их не меньше 20. Из них не менее 10 параллельных, и уже на них останется не менее 10 фишек.
  Снять 90 фишек можно, например, в следующем порядке. Снимем все фишки левого столбца. Теперь можно снять все фишки 2-го столбца, кроме верхней и нижней, затем все фишки 3-го столбца... и т.д.

Ответ

90 фишек.

Замечания

1. Возможны и другие алгоритмы. В некоторых полезно заметить, что фишки с белых и чёрных полей (в шахматной раскраске) снимаются независимо друг от друга. Поэтому достаточно суметь снять 45 "белых" фишек. Также отметим, что надо всегда снимать фишку с пересечения чётной и нечётной диагоналей (иначе число нечётных диагоналей увеличится).

2. 6 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 3

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

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