Задача
В таблице 2005×2006 расставлены числа 0, 1, 2 так, что сумма чисел в каждом столбце и в каждой строке делится на 3.
Какое наибольшее возможное количество единиц может быть в этой таблице?
Решение
Оценка. Пусть в таблице n нулей и d двоек. У нас есть 2005 строк длины 2006 и 2006 столбцов длины 2005. Чтобы сумма в строке делилась на 3, там должна быть хотя бы одна двойка или два нуля. Отсюда d + n/2 ≥ 2005. Аналогично в каждом столбце должен быть нуль либо две двойки минимум, поэтому n + d/2 ≥ 2006. Сложив неравенства, получим n + d ≥ 2674, то есть не единиц в таблице минимум 2674.
Пример. Этот результат достигается в приведённой таблице (1338 нулей в верхнем левом прямоугольнике 669×1338 и 1336 двоек в правом нижнем прямоугольнике 1336×668).
Ответ
2005·2006 – 2674 = 4019356 единиц.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь