Выбрана 1 задача 
Убрать все задачи
Клетки таблицы 200×200 окрашены в чёрный и белый цвета так, что чёрных клеток на 404 больше, чем белых.
Докажите, что найдётся квадрат 2×2, в котором число белых клеток нечётно.
|
|
 |
Условие
Клетки таблицы 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 – простое число, то последнее уравнение не имеет решений в натуральных числах. Противоречие.
