Таблица с числами

[Simba]

В каждой клетке таблицы 2n x 2n вписаны числа $1, 2, ... , (2n)^2$. Доказать, что в таблице надётся $n+1$ столбцов (или строк, разницы нет), так чтобы каждое число в столбце (или в строке, разницы нет) было меньше суммы оставшихся $2n-1$ чисел в этом столбце (или в строке, разницы нет).

[worm2]

Что-то я не понял условие.

$$\begin{matrix} 16&1&5&9\\ 2&15&8&4\\ 6&3&11&12\\ 7&10&13&14 \end{matrix}$$

Какие 3 столбца (или 3 строки) удовлетворяют условию?

-- Сб май 14, 2011 16:43:44 --

Или я имею право сосчитать, скажем, 2 строки и 1 столбец, и у меня всего будет 3, как и требуется?

[ewert]

Это, по-видимому, действительно верно, но только начиная с $n=3$ (и при больших $n$ верно с большим запасом). Т.е. у меня получилось, что для доказательства достаточно выполнения неравенства $2n^3-6n^2+n-1>0$. Правда, я запросто мог ошибиться в арифметике.

[Simba]

Извините я забыл условие $n\geq 3$

-- Сб май 14, 2011 20:05:52 --

ewert в сообщении #445789 писал(а):

Т.е. у меня получилось, что для доказательства достаточно выполнения неравенства .

Как вы его получили?

[ewert]

Обратное утверждение: найдётся не менее $n$ столбцов, в каждом из которых наибольший элемент больше или равен суммы всех остальных. Тогда сумма этих наибольших элементов больше или равна суммы всех остальных. Надо доказать, что это невозможно, т.е. что сумма наибольших элементов всегда меньше суммы всех остальных.

Сумма наибольших элементов по $n$ столбцам не больше, чем $4n^2+(4n^2-1)+(4n^2-2)+\ldots+(4n^2-n+1)$.

Сумма остальных элементов по этим столбцам не меньше, чем $1+2+3+\ldots+n(2n-1)$.

Т.е. достаточно доказать, что

$4n^2+(4n^2-1)+(4n^2-2)+\ldots+(4n^2-n+1)<1+2+3+\ldots+n(2n-1)$

После всех сворачиваний-разворачиваний у меня получилось неравенство $2n(2n^3-6n^2+2n-1)>0$. При $n=1$ и $n=2$ оно нарушается (и, как видим, не напрасно). Начиная с $n=3$ оно выполняется.

Но это, конечно, если я ничего не напутал в арифметике.

-- Сб май 14, 2011 18:12:13 --

И вообще, я предлагаю подумать над более сильным (и технически более простым) утверждением. Доказать, что при любом натуральном $n$ в таблице найдутся как минимум $(2n-2)$ столбцов таких, что каждое число в столбце меньше суммы остальных чисел этого столбца. И что эта оценка точна в следующем смысле: при любом $n$ можно расположить числа так, чтобы в двух столбцах одно из чисел было больше суммы остальных.

(хотя в арифметике я так и не уверен)