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

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

Условие

На прямоугольном экране размером m×n, разбитом на единичные клетки, светятся более  (m – 1)(n – 1)  клеток. Если в каком-либо квадрате 2×2 не светятся три клетки, то через некоторое время погаснет и четвёртая. Докажите, что тем не менее на экране всегда будет светиться хотя бы одна клетка.


Решение

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

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

журнал
Название "Квант"
год
Год 1991
выпуск
Номер 7
Задача
Номер М1295
олимпиада
Название Московская математическая олимпиада
год
Номер 54
Год 1991
вариант
Класс 11
задача
Номер 5

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

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