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

Проект МЦНМО
при участии
школы 57
Задача 110046
Темы:    [ Таблицы и турниры (прочее) ]
[ Раскраски ]
[ Симметрия и инволютивные преобразования ]
[ Уравнения в целых числах ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Клетки таблицы 200×200 окрашены в чёрный и белый цвета так, что чёрных клеток на 404 больше, чем белых.
Докажите, что найдётся квадрат 2×2, в котором число белых клеток нечётно.


Решение

  Предположим, что в любом квадрате 2×2 чётное число белых клеток. Тогда если верхние клетки квадрата окрашены одинаково, то и нижние клетки окрашены одинаково, а если верхние клетки окрашены по-разному, то и нижние окрашены по-разному.
  Рассмотрим верхнюю строку таблицы и строку, стоящую под ней. Из сказанного следует, что эти строки либо окрашены одинаково (если их первые клетки окрашены одинаково), либо окрашены так, что под белой клеткой находится черная, а под чёрной – белая (если их первые клетки окрашены по-разному). Аналогичное утверждение справедливо для любых двух подряд идущих строк.
  Следовательно, в нашей таблице есть только два типа строк: первая строка и строка, полученная из нее перекрашиванием клеток в противоположный цвет.
  Пусть в первой строке a чёрных клеток, и строк такого типа в нашей таблице b. Тогда число чёрных клеток в таблице равно  ab + (200 – a)(200 – b),  а белых клеток –  a(200 – b) + b(200 – a).
  Их разность по условию равна 404, то есть  4ab – 2·200(a + b) + 200² = 404,  откуда  (a – 100)(b – 100) = 101.
  Так как  |a – 100| ≤ 100,  |b – 100| ≤ 100,  а 101 – простое число, то последнее уравнение не имеет решений в натуральных числах. Противоречие.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2000
Этап
Вариант 4
Класс
Класс 9
задача
Номер 00.4.9.8

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

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