|
|
 |
Условие
На прямоугольном экране размером m×n, разбитом на единичные клетки, светятся более (m – 1)(n – 1) клеток. Если в каком-либо квадрате 2×2 не светятся три клетки, то через некоторое время погаснет и четвёртая. Докажите, что тем не менее на экране всегда будет светиться хотя бы одна клетка.
Решение
Поставим в соответствие каждой погасшей клетке квадратик 2×2, в котором она была последней светящейся (если таких квадратиков несколько, выберем любой из них). Ясно, что двум клеткам не может соответствовать один и тот же квадратик. Значит, общее число погасших клеток не больше числа квадратов 2×2 в прямоугольнике m×n. Нетрудно подсчитать, что это число равно (m − 1) (n − 1). Таким образом, погаснут не более (m − 1)(n − 1) клеток, что меньше исходного количества светящихся клеток..
