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

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

Условие

В таблицу 10×10 нужно записать в каком-то порядке цифры  0, 1, 2, 3, ..., 9  так, что каждая цифра встречалась бы 10 раз.
  а) Можно ли это сделать так, чтобы в каждой строке и в каждом столбце встречалось не более четырёх различных цифр?
  б) Докажите, что найдётся строка или столбец, в которой (в котором) встречается не меньше четырёх различных чисел.


Решение

  а) См. рис. (цифры заменены цветами)

  б) Пусть в каждом ряду встречается не более трёх различных цифр, причём цифра n встречается в an строках и bn столбцах. Сумма  a0 + ... + a9  равна количеству "вхождений" всех цифр во все строки, то есть не превосходит 30. Аналогично  b0 + ... + b9 ≤ 30.
  С другой стороны,  anbn ≥ 10,  поэтому  an + bn ≥ 7.  Значит,  a0 + ... + b9 ≥ 70.  Противоречие.


Ответ

а) Можно.

Замечания

баллы: 6 + 16

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

журнал
Название "Квант"
год
Год 1985
выпуск
Номер 8
Задача
Номер М939
олимпиада
Название Турнир городов
Турнир
Дата 1984/1985
Номер 6
вариант
Вариант весенний тур, основной вариант, 7-8 класс
Задача
Номер 5

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

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