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

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

Условие

Автор: Антипов М.

Каждая клетка доски 100×100 окрашена либо в чёрный, либо в белый цвет, причём все клетки, примыкающие к границе доски – чёрные. Оказалось, что нигде на доске нет одноцветного клетчатого квадрата 2×2. Докажите, что на доске найдётся клетчатый квадрат 2×2, клетки которого окрашены в шахматном порядке.


Решение

  Предположим противное: на доске нет ни одноцветных, ни шахматно окрашенных квадратов 2×2. Рассмотрим все отрезки сетки, разделяющие две разноцветных клетки (назовём их разделителями); пусть их количество равно N.
  В любом квадрате 2×2 есть либо ровно одна клетка одного из цветов и три клетки другого, либо две соседних белых клетки и две соседних чёрных. В обоих случаях внутри квадрата есть ровно два разделителя. Всего имеется 99² квадратов 2×2, а каждый разделитель лежит внутри ровно двух из них (по условию к границе разделители не примыкают). Значит,  N = 2·99² : 2 = 99².
  С другой стороны, N должно быть чётным. Действительно, в каждой строке и каждом столбце первая и последняя клетка – чёрные; поэтому там должно быть чётное число перемен цвета. Противоречие.

Замечания

1. Количество разделителей равно количеству разноцветных доминошек. Вместо него можно подсчитать количество одноцветных доминошек – оно равно  2·100·99 – N.

2. Чётность общего количества разделителей можно доказать разными методами. Например, можно заметить, что если все внутренние клетки белые, то число разделителей равно 4·98, а при любой перекраске внутренней клетки оно может измениться только на чётную величину.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 5
класс
Класс 9
задача
Номер 9.8
олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 5
класс
Класс 10
задача
Номер 10.7

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

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