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

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

Условие

Автор: Иванов С.

Дана таблица n×n, заполненная числами по следующему правилу: в клетке, стоящей в i-й строке и j-м столбце таблицы записано число     В таблице зачеркнули n чисел таким образом, что никакие два зачёркнутых числа не находятся в одном столбце или в одной строке. Докажите, что сумма зачёркнутых чисел не меньше 1.


Решение 1

  Сумма чисел, стоящих в левой верхней и правой нижней вершинах любого прямоугольника, больше суммы чисел, стоящих в других двух вершинах:
  Действительно, это неравенство имеет вид


  Если в левой нижней клетке таблице число не зачеркнуто, то берем зачеркнутые числа, стоящие в первом столбце и n-й строке, рассматриваем прямоугольник, диагональ которого они образуют и заменяем их на числа, стоящие в других двух вершинах прямоугольника. При этом сумма зачеркнутых чисел уменьшится, а в левой нижней клетке таблицы появится зачеркнутое число. Выкинув из таблицы первый столбец и n-ю строку, повторим процедуру с уменьшенной таблицей и т. д.
  В результате получим таблицу, в которой зачеркнуты все числа по диагонали, ведущей из левого нижнего в правый верхний угол.
Сумма этих чисел равна 1.


Решение 2

Автор: Руденко Д.

  Пусть вычеркнуты клетки с номерами  (1, i1),  (2, i2),  ...,  (n, in).  Положим  ak = k + ik – 1  – это знаменатели вычеркнутых дробей. Заметим, что
a1 + ... + an = (1 + i1 – 1) + (2 + i2 – 1) + ... + (n + in – 1) = (1 + ... + n) + (i1 + ... + in) – n = 2(1 + ... + n) – n = n(n + 1) – n = n2.
  Согласно неравенству между средним арифметическим и средним гармоническим (см. задачу 61402 в)
  то есть  

Замечания

1. 8 баллов.

2. Задача предлагалась на Санкт-Петербургской математической олимпиаде (1992 г., 9 кл., задача 5).

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

журнал
Название "Квант"
год
Год 1992
выпуск
Номер 7
Задача
Номер М1353
олимпиада
Название Турнир городов
Турнир
Дата 1991/1992
Номер 13
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 3

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

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