Оценка матриц

[kps]

Есть матрица $n\timesn$, в матрице n чисел, каждое встречается n раз.
Необходимо показать, что есть строка или столбец, где как минимум
$\sqrt{n}$ различных чисел.

Например, рассмотрим строки.
Общее количество различных строк равно числу сочетаний с повторением n чисел.
$DifLine = \mathsf{A}_{n}^{n} = \frac{(2n-1)! }{ n!(n-1)!} $.

из них нужно выбрать те k строк, у которых количество различных элементов больше либо равным $\sqrt{n}$.

$SoughtValue = \mathsf{C}_{DifLine}^{k} = \frac{DifLine! }{ DifLine!(DifLine-k)!} $.

Можно подсчитать вероятность данного события.
Общее количество возможных матриц из n элементов будет $TotalMatrix = (n!)^n$

Следовательно, вероятность выбрать из возможных матриц те, у которых есть строки, где как минимум
$\sqrt{n}$ различных чисел.
$P = SoughtValue/TotalMatrix$

Вроде, вероятность не нулевая и есть строка или столбец, где как минимум
$\sqrt{n}$ различных чисел.

Но как ее решить правильно и однозначно, я не очень понимаю

[deep down]

Пусть подходящих строк нет. Тогда в каждой строке найдётся число, которое присутствует более, чем $\sqrt{n}$ раз. Дальше рассматриваем только их, остальные числа стираем. Теперь сравните две величины.
1. Минимальное количество чисел, если считать по строкам.
2. Если в каждом столбце их не больше, чем $\sqrt{n}$, сколько всего их может быть (максимум)?
Другими словами, работает принцип Дирихле.

[kps]

deep down в сообщении #1249357 писал(а):

Пусть подходящих строк нет. Тогда в каждой строке найдётся число, которое присутствует более, чем $\sqrt{n}$ раз. Дальше рассматриваем только их, остальные числа стираем. Теперь сравните две величины.
1. Минимальное количество чисел, если считать по строкам.
2. Если в каждом столбце их не больше, чем $\sqrt{n}$, сколько всего их может быть (максимум)?
Другими словами, работает принцип Дирихле.

Спасибо, оказалось, что все очень просто)

[kps]

Все же не понятно)
Можно ли рассуждать следующим образом и можно ли как-то доказательство сделать более похожем на доказательство?)

1. Пусть не найдется таких строк и столбцов, в которых больше или равно $\sqrt{n}$ различных чисел.

2. Тогда в каждой строке найдётся число, которое присутствует более, чем $\sqrt{n}$ раз.

3. Общее возможное количество различных строк соответствует следующему значению:
$Total =\mathsf{C} _{n}^{k} \times k^n $, где $k < \sqrt{n}$.
Т.е. выбираем из $n$ $k$ чисел все возможными способами. И находим возможное количество различных строк из выбранных $k$ чисел.

Для наглядности рассмотрим простой пример.
Предположим $n=4$, тогда у нас будут следующий набор чисел:
1, 2, 3, 4.
$\sqrt{n} = \sqrt{4} = 2$, из первого допущения, в строке должно быть меньше 2 различных чисел, т.е. 1.
Получим следующий возможный набор строк:
$\begin{Bmatrix} 1 & 1 & 1 & 1 \end{Bmatrix}$
$\begin{Bmatrix} 2 & 2 & 2 & 2 \end{Bmatrix}$
$\begin{Bmatrix} 3 & 3 & 3 & 3 \end{Bmatrix}$
$\begin{Bmatrix} 4 & 4 & 4 & 4 \end{Bmatrix}$

4. Общее возможное количество различных столбцов также соответствует:
$Total =\mathsf{C}_{n}^{k} \times k^n $, где $k < \sqrt{n}$.
В рамках нашего примера, для матрицы $4 \times 4$. Из первого допущения, в столбце должно быть меньше 2 различных чисел, т.е. 1.
Получим следующий возможный набор столбцов:
$\begin{Bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{Bmatrix}$ $\begin{Bmatrix} 2 \\ 2 \\ 2 \\ 2 \end{Bmatrix}$ $\begin{Bmatrix} 3 \\ 3 \\ 3 \\ 3 \end{Bmatrix} $ $\begin{Bmatrix} 4 \\ 4 \\ 4 \\ 4 \end{Bmatrix}$

4. Таким образом, если сформировать данную матрицу, количество различных чисел будет встречаться больше, чем $n$ раз, что противоречит условию задачи.\\*
Следовательно в строке или столбце найдется строка или столбец, где как минимум $\sqrt{n}$ различных чисел.

[idle]

deep down в сообщении #1249357 писал(а):

Пусть подходящих строк нет. Тогда в каждой строке найдётся число, которое присутствует более, чем $\sqrt{n}$ раз. Дальше рассматриваем только их, остальные числа стираем. Теперь сравните две величины.
1. Минимальное количество чисел, если считать по строкам.
2. Если в каждом столбце их не больше, чем $\sqrt{n}$, сколько всего их может быть (максимум)?
Другими словами, работает принцип Дирихле.

Перечитал ваше решение несколько раз, но не могу понять, что предлагается посчитать.
Минимальное (и максимальное во втором пункте) количество различных чисел? Или общее количество ячеек, в которых не стерли числа?

[deep down]

kps в сообщении #1250506 писал(а):

Общее возможное количество различных строк соответствует следующему значению:
$Total =\mathsf{C} _{n}^{k} \times k^n $, где $k < \sqrt{n}$.

Что такое $k$? Не придётся ли суммировать по всем допустимым?
(Сразу не заметил, что Вы ответили).

idle в сообщении #1252123 писал(а):

Перечитал ваше решение несколько раз, но не могу понять, что предлагается посчитать.
Минимальное (и максимальное во втором пункте) количество различных чисел? Или общее количество ячеек, в которых не стерли числа?

Мы считаем только общее количество нестёртых ячеек (если число в строке повторяется 5 раз - оно считается как 5 ячеек).
Если в каждой строке выбрано минимум $\sqrt{n}$ ячеек, то всего выбрано минимум $n\sqrt{n}$.
Теперь мы пытаемся разместить их по столбцам, чтобы в каждом было не больше $\sqrt{n}$ из них. Получится?

PS. Если опять плохо объяснил, не постесняйстесь сказать. Буду благодарен.

[idle]

Теперь понял, спасибо.
Смущает один момент. Следую вашему решению: найдется столбец, в котором больше $\sqrt{n}$ нестёртых чисел. Но почему эти числа различны? Можно подобрать такой пример: в первых $\sqrt{n}$ строках матрицы число 1 встретилось $\sqrt{n}$ раз в каждой. Потом мы найдём столбец, который будет содержать $\sqrt{n}$ единиц, но он ничего не доказывает.

[deep down]

Вы правы, в таком виде не сработает. Ответа пока нет, буду думать

[idle]

Попробовал сделать такой заход: пусть в каждой строке $< \sqrt{n}$ различных чисел. Назовём для удобства множества одинаковых чисел в строке блоками. Тогда во всей матрице $< n \sqrt{n}$ блоков. И тогда найдётся блок, в котором $<\sqrt{n}$ чисел (одинаковых). Аналогично, найдётся число, распределённое по матрице в $\lte \sqrt{n}$ блоков. Неформально говоря, матрица разбивается на большое количество блоков. И наверное, это будет означать, что найдётся столбец из достаточно большого количества блоков. Но куда двигаться дальше, пока не вижу.

[idle]

Всё понял.
В предыдущем рассуждении нужно вместо столбца искать строку или столбец, тогда всё получается.
Я так понимаю, полное решение тут нельзя публиковать.

[deep down]

(Оффтоп)

Зависит от топикстартера и его вопросов. Написанного хватит для реконструкции полного решения.
В любом случае Вам спасибо от меня.