|
|
 |
Условие
В прямоугольной таблице m строк и n столбцов (m < n). В некоторых клетках таблицы стоят звёздочки, так что в каждом столбце стоит хотя бы одна звёздочка. Докажите, что существует хотя бы одна такая звёздочка, что в одной строке с нею находится больше звёздочек, чем с нею в одном столбце.
Решение
Из исходной таблицы со звездочками построим две новые, в которых звездочки заменены числами: в первой таблице эти числа в каждом столбце, содержащем k звездочек, равны 1/k, а во второй – числа в каждой строке с l звездочками равны 1/l. Сумма всех чисел в первой таблице равна n, а во второй – m. Поскольку m < n, то существует такое место, на котором число из первой таблицы больше числа из второй, то есть 1/k > 1/l. Таким образом, число k звёздочек в соответствующем столбце меньше числа l звёздочек в соответствующей строке.
Замечания
1. Доказательство можно также провести по индукции.
2. 8 баллов.
