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

Проект МЦНМО
при участии
школы 57
Задача 116637
Темы:    [ Шахматные доски и шахматные фигуры ]
[ Шахматная раскраска ]
[ Комбинаторная геометрия (прочее) ]
[ Четность и нечетность ]
[ Доказательство от противного ]
Сложность: 5
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Кноп К.А.

В некоторых клетках доски 100×100 стоит по фишке. Назовём клетку красивой, если в соседних с ней по стороне клетках стоит чётное число фишек.
Может ли ровно одна клетка доски быть красивой?


Решение

  Лемма. Для любой клетки доски X существует такое множество S, состоящее из чётного количества клеток и содержащее X, что у каждой клетки доски чётное число соседей лежит в S.
  Доказательство. Раскрасим клетки доски в шахматном порядке так, чтобы X стала чёрной. Рассмотрим одну из диагоналей, проходящих через X; пусть A и B – центры двух крайних клеток этой диагонали, а C и D – точки, симметричные им относительно центра доски. Обозначим через S множество всех чёрных клеток, центры которых лежат внутри или на границе прямоугольника ABCD. На рисунке показаны возможные виды множества S на доске 8×8 (прямоугольники ABCD обозначены пунктиром).

  Множество S состоит из чётного числа клеток, поскольку количества центров клеток на сторонах AB и AD имеют разную чётность. Чёрные клетки не имеют соседей в S, каждая белая клетка внутри ABCD граничит с четырьмя клетками из S, а каждая белая клетка вне ABCD – либо с нулём, либо с двумя клетками из S. Итак, множество S удовлетворяет всем условиям.

  Предположим, что существует ровно одна красивая клетка X. Рассмотрим для этой клетки множество S из леммы. Для каждой клетки этого множества посчитаем количество фишек в соседних с ней клетках; пусть g – сумма всех этих количеств. С одной стороны, в S чётное число клеток, из которых ровно одна красива, а все остальные – нет; поэтому сумма g нечётна. С другой стороны, каждая клетка с фишкой имеет чётное число соседей в S, поэтому она была сосчитана чётное число раз. Значит, сумма g чётна. Противоречие.


Ответ

Не может.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2010-2011
Этап
Вариант 5
Класс
Класс 9
Задача
Номер 9.8

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

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