таблица nxn

[daogiauvang]

Дано положительное целое число n, и таблица размером $n $ x $ n$. Мы заполнили натуральные числа в сетках соответствуют $n$ x $n$. Оказалось, что 2 любых натуральных числа из двух соседних клеток (имеющие общие стороны), отличатются не более 1 ед. Доказать, что существует одно число заполнено не менее $n$ раз.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Toucan]

Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»
Причина переноса: вернул.

[maxal]

Рассмотрим первый и последний столбцы таблицы и упорядочим числа написанные в их клетках: $x_1 \leq x_2 \leq \dots \leq x_{2n}$.
Покрасим клетки содержащие числа $x_1, x_2, \dots, x_n$ в белый цвет, а клетки содержащие числа $x_{n+1}, x_{n+2}, \dots, x_{2n}$ -- в чёрный.

Лемма 1. Белые клетки можно соединить с чёрными непересекающимися путями.
(Под путем в таблице мы понимаем последовательность клеток, в которой последовательные пары клеток являются соседними, т.е. имеют общую сторону).

Как следствие, получаем набор из $n$ непересекающихся путей, каждый из которых обязан содержать хотя бы одну клетку с числом $x_n$. Поэтому число $x_n$ представлено в таблице не менее $n$ раз.

Остаётся доказать лемму 1. Она следует из более общего утверждения:

Лемма 2. Пусть в таблице $n\times k$, $n\geq k$, в первом и последнем столбцах $k$ клеток покрашено в белый цвет и $k$ клеток -- в чёрный цвет (покрашенные клетки могут быть произвольно распределёны между первым и последним столбцами). Тогда белые клетки можно соединить с чёрными непересекающимися путями.

Лемму 2 можно доказать индукцией по $k$.
Если в одном (пусть первом) столбце есть как белые, так и чёрные клетки, то найдем пару клеток белая-чёрная, между которыми нет других покрашенных клеток, и соединим их вертикальным путем. Далее, переносим раскраску клеток с первого столбца во второй (кроме только что соединённых клеток), отрезаем первый столбец и пользуемся индукцией.
Если же все белые клетки в одном столбце, а все черные - в другом, то непересекающиеся пути можно построить явно. Пойдём по парам клеток белая-черная сверху вниз и будем соединять их путями. Каждый такой путь будет состоять из трёх сегментов (возможно пустых): горизонтального-вертикального-горизонтального. Вертикальные сегменты будут располагаться каждый в своем столбце, причем если по вертикальному сегменту нужно проходить снизу вверх, то резервируем под него наименьший свободный столбец, а если сверху вниз -- то наибольший свободный.

[DeBill]

maxal
Здорово!
Или: в лемме 2 требовать "покрашено $s \leqslant k$ клеток" (условие $n\geqslant k$ в Вашей версии Л.2 выполняется всегда автоматически)
Тогда: в (последнем) шаге индукции можно верхние клетки в левом и правом столбцах соединить путем вверх-вправо-вниз, и удалить покрашенные и верхнюю строчку.

[maxal]

DeBill, можно и так. Только у вас не совсем понятно, что значит "удалить покрашенные".
Если соединяем клетку в строке $i$ первого столбца с клеткой в строке $j$ последнего, причём $i\leq j$, то удалять нужно первый столбец и первые $i$ строк. Кстати, крюк "вверх-вправо-вниз" можно сократить до вверх-вправо (т.е. вверх с $i$-й строки до $j$-й, а потом вправо по $j$-й строке), или до "вправо-вниз" если $i>j$.

[DeBill]

maxal в сообщении #1217555 писал(а):

удалять нужно первый столбец и первые $j$ строк.

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

[maxal]

Усиление:
каждое из чисел $x_n$ и $x_{n+1}$ встречается не менее $n$ раз;
каждое из чисел $x_{n-1}$ и $x_{n+2}$ встречается не менее $n-1$ раз;
...
каждое из чисел $x_1$ и $x_{2n}$ встречается не менее $1$ раза.
(некоторые из чисел здесь могут совпадать)

Например, если так случилось, что $x_i=i$, то, как ни крути, каждое число $i\leq n$ встречается в таблице не менее $i$ раз.

[Skeptic]

maxal в сообщении #1217472 писал(а):

Как следствие, получаем набор из $n$ непересекающихся путей, каждый из которых обязан содержать хотя бы одну клетку с числом $x_n$. Поэтому число $x_n$ представлено в таблице не менее $n$ раз.

Контрпример.
"13 не содержится во второй строке.
323
212
323

[DeBill]

Skeptic
Контрпримерность контрпримера полезно проверять на док-ве: либо найдем пробел в док-ве, либо обнаружим не контрпримерность контрпримера. В данном случае имеет место второе: одна из троек - белая, а три других - черные.
Разбиение на пути тогда легко строится (белую тройку соединяем горизонтальным путем с черной, двойки - с соседними тройками. Это доказывает, что троек - не меньше трех. А их даже четыре...)

[Skeptic]

DeBill

Вы правы, я не разобрался.
Но в этом доказательстве не учитывается постоянство разности между соседними числами. Это лишнее условие в задаче?

[DeBill]

Skeptic в сообщении #1217936 писал(а):

не учитывается постоянство разности между соседними числами. Это лишнее условие в задаче?

Э, нет , в условие сказано "не более чем на 1". В решении это использовано как "дискретная непрерывность": шагая от малого натурального к большому с шагами не боле единицы, мы наступим на все промежуточные.