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

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

Условие

В таблице 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  единиц.

Замечания

6 баллов

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

олимпиада
Название Турнир городов
Турнир
Номер 27
Дата 2005/2006
вариант
Вариант весенний тур, основной вариант, 8-9 класс
задача
Номер 5

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

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