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

Проект МЦНМО
при участии
школы 57
Задача 109646
Темы:    [ Свойства разверток ]
[ Цилиндр ]
[ Раскраски ]
Сложность: 5
Классы: 10,11
В корзину
Прислать комментарий

Условие

Квадрат n×n ( n 3 ) склеен в цилиндр. Часть клеток покрашена в черный цвет. Докажите, что найдутся две параллельных линии (две горизонтали, две вертикали или две диагонали), содержащие одинаковое количество черных клеток.

Решение

Докажем утверждение от противного. Пусть есть раскраска, при которой отсутствует пара параллельных линий с одинаковым числом черных клеток.
Будем называть весом линии количество черных клеток на ней. Пусть есть горизонталь веса n . Тогда n вертикалей и n диагоналей каждого направления должны иметь веса 1, 2, n , так как все они пересекают эту горизонталь. Тогда и n горизонталей имеют веса 1, 2, n , так как все они пересекают вертикаль веса n .
Циклически переставим горизонтали и вертикали так, чтобы нижняя горизонталь и левая вертикаль имели вес n (свойства раскраски при этом не изменятся). Пронумеруем горизонтали снизу вверх от 0 до n-1 , а вертикали – от 0 до n-1 слева направо.
Каждая диагональ пересекает по разу горизонталь и вертикаль веса n ; поэтому диагонали веса 1 должны проходить через клетку их пересечения – клетку (0,0) . Итак, все клетки (i,i) и (n-i,i) , i>0 , не закрашены.
Если n нечетно, то в каждом столбце, кроме 0, получаем не менее двух незакрашенных клеток, и столбца веса n-1 не найдется.
Если n=2m , то столбец m и строка m должны иметь вес n-1 (в любой из остальных строк и любом из остальных столбцов есть хотя бы две незакрашенные клетки). Тогда в них закрашены все клетки, кроме (m,m) , и мы не сможем найти столбца веса 1.
Если с самого начала отсутствует горизонталь веса n , то есть горизонталь веса 0, и мы можем провести те же рассуждения, поменяв ролями закрашенные и незакрашенные клетки.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1997
Этап
Вариант 5
Класс
Класс 10
задача
Номер 97.5.10.2

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

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