2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 таблица nxn
Сообщение09.05.2017, 07:49 
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение09.05.2017, 17:58 


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

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


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

 Профиль  
                  
 
 Posted automatically
Сообщение15.05.2017, 01:49 
Админ форума
Аватара пользователя


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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение20.05.2017, 05:43 
Модератор
Аватара пользователя


11/01/06
5660
Рассмотрим первый и последний столбцы таблицы и упорядочим числа написанные в их клетках: $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$.
Если в одном (пусть первом) столбце есть как белые, так и чёрные клетки, то найдем пару клеток белая-чёрная, между которыми нет других покрашенных клеток, и соединим их вертикальным путем. Далее, переносим раскраску клеток с первого столбца во второй (кроме только что соединённых клеток), отрезаем первый столбец и пользуемся индукцией.
Если же все белые клетки в одном столбце, а все черные - в другом, то непересекающиеся пути можно построить явно. Пойдём по парам клеток белая-черная сверху вниз и будем соединять их путями. Каждый такой путь будет состоять из трёх сегментов (возможно пустых): горизонтального-вертикального-горизонтального. Вертикальные сегменты будут располагаться каждый в своем столбце, причем если по вертикальному сегменту нужно проходить снизу вверх, то резервируем под него наименьший свободный столбец, а если сверху вниз -- то наибольший свободный.

 Профиль  
                  
 
 Re: таблица nxn
Сообщение20.05.2017, 14:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение20.05.2017, 15:12 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение20.05.2017, 15:17 
Заслуженный участник


10/01/16
2315
maxal в сообщении #1217555 писал(а):
удалять нужно первый столбец и первые $j$ строк.

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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение20.05.2017, 18:59 
Модератор
Аватара пользователя


11/01/06
5660
Усиление:
каждое из чисел $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$ раз.

 Профиль  
                  
 
 Re: таблица nxn
Сообщение21.05.2017, 15:36 


01/12/11

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

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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение21.05.2017, 15:55 
Заслуженный участник


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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение22.05.2017, 08:08 


01/12/11

1047
DeBill

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

 Профиль  
                  
 
 Re: таблица nxn
Сообщение22.05.2017, 08:25 
Заслуженный участник


10/01/16
2315
Skeptic в сообщении #1217936 писал(а):
не учитывается постоянство разности между соседними числами. Это лишнее условие в задаче?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group