Республиканская олимпиада по математике, 2017 год, 10 класс

В каждую клетку таблицы $100\times 100$ записано одно из чисел 1,2,...,100, причем каждое из этих чисел встречается в таблице 100 раз. Назовем линией любую строку или столбец таблицы. За один ход разрешается взять линию, в котором сумма чисел больше 100, и обнулить все числа на этой линии. Какое наибольшее количество ненулевых чисел может остаться в таблице, если известно, что после нескольких ходов во всех линиях сумма чисел не превосходит 100? ( Сатылханов К. )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 650. Решение. Заметим, что при перестановки строк или столбцов условие задачи не меняется, поэтому можно считать, что на первые $m $строк и $n$ столбцов не сделано операция обнуления. Тогда наша задача сводится к следующей: найдите наибольшее возможное значение $mn$ $\left( 0\le m,n\le 100 \right)$, что в клетки таблицы $m\times n$ можно записать числа $1,2, \ldots,100$, причем каждое число можно записать не более 100 раз, чтобы сумма чисел в каждой строке и в каждом столбце не превосходило 100.
Сначала докажем, что $mn\le 650$. От противного, пусть $mn > 650$. Без ограничение общности $m\le n$. Обозначим через $s$ сумму всех чисел в таблице. Так как сумма чисел в каждой строке не превосходит 100, то $$s\le 100m. \qquad (1)$$ Пусть $mn=100k+r$, где $r$,$k$ целые числа и $0\le r < 100$. По предположению $k\ge 6$. В таблице $100k+r$ натуральных чисел, причем каждое число встречается не более 100 раз, следовательно $$s\ge 100\left( 1+2+\ldots +k \right)+r\left( k+1 \right). \qquad (2)$$ Из (1) и (2) следует, что $$100\left( m-\frac{k\left( k+1 \right)}{2} \right)\ge r\left( k+1 \right). \qquad (3)$$ Значит, $m\ge \frac{k\left( k+1 \right)}{2}$ $\Rightarrow 100\left( k+1 \right) > mn\ge {{m}^{2}}\ge {{(\frac{k\left( k+1 \right)}{2})}^{2}}\Rightarrow $ ${{k}^{2}}\left( k+1 \right) < 400$ $\Rightarrow k\le 7$. Если $k=7$, то $m\ge \frac{7\cdot 8}{2}=28$, но $mn < 800$, следовательно $m=n=28,r=84$, тогда неравенство (3) неверно.
Значит $k=6$. Тогда $r=mn-600 > 50$ и ${{m}^{2}}\le mn < 700$ $\Rightarrow m\le 26$. Из (3) следует, что $100\left( m-21 \right)\ge 7r > 350 \Rightarrow m\ge 25$. Если $m=25$, так как $650 < mn < 700$, то $n=27,r=75$, тогда неравенство (3) неверно. Если $m=26$, так как $650 < mn < 700$, то $n=26,r=76$, тогда неравенство (3) неверно, противоречие.
Теперь приведем пример когда $mn=650$. Пусть $m=25,n=26$ и заполним таблицу $25\times 26$ как показано на рисунке $\left( i+1 \right)$-вая строка является циклическим сдвигом вправо $i$-той строки для каждого $i=1,2,\ldots ,24$. Заметим, что числа от 1 до 6 встречаются в таблице 100 раз, а число 7 присутствует 50 раз. Сумма чисел в каждой строке равна $4(1+2+\ldots+6)+2\cdot 7=98$. Так как в каждом столбце числа $1,2, \ldots,6$ встречаются не более 4 раза, а число 7 не более 2 раза, то сумма чисел в каждом столбце не более 98.