2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 60, 61, 62, 63, 64, 65, 66 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 09:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #595414 писал(а):
Получается при взаимнопростых числах (C,k) можно применять только лемму 4.3 в классической постановке. Там все устроено так, например (5,2)-сильная раскраска. Можно делать репликацию всего два раза. При этом числа 1,2 перейдут в числа 3,4. То есть будут меньше 5-ти. Тогда их не надо брать по модулю 5. И значит они не сменят свою четность/нечетность.

Блин! Вы на пример посмотрите в классической лемме 4.3.
Прямоугольник 6х11 (5,2)-сильная ракраска в смысле леммы 4.3.
А репликаций у меня три! То есть исходный прямоугольник и два редуцированных.
Итоговый прямоугольник 6х33.

Или я опять ничего не поняла с репликациями и редукциями, или это вы ничего не поняли.
Сколько у меня в этом примере репликаций? Сколько редукций?
По-моему так: редукции две, репликации три.
Вы же сами вон крупно написали: репликация = редукция + 1.
Репликация = 3
редукция = 2
3 = 2 +1 :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 09:25 
Аватара пользователя


21/02/10
1594
Екатеринбург
alexBlack
Конгениально! МБ-лемма спасена!

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 09:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
alexBlack
так можно в этом примере (прямоугольник 15х11) применить лемму или всё же нельзя?
При замене, которую вы привели, сколько проходит репликаций? Одна или две?

А сколько их должно быть в случае (5,2)-сильной раскраски по лемме 4.3?

Так мне и не ответили на этот вопрос: сколько у меня репликаций в примере с прямоугольником 6х11 (5,2)-сильная раскраска? Это пример по лемме 4.3. Итоговый прямоугольник получился 6х33 5-coloring. Я считаю, что здесь три репликации.

Всё!
У меня голова треснула :D
Я ушла.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 10:22 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #595310 писал(а):
Любой 5-сильно окрашенный прямоугольник 26х6 имеет не менее 15 ошибок.


5-сильно окрашенный прямоугольник 26х6 не существует.
Sirgedas
26*6=156. 156 ячеек распределим равномерно (почему равномерно больше объяснять не буду) по 5-ти цветам. 156=31*4+32*1. 31 символ можно распределить равномерно по 6-ти колонкам так: 31=1*6+5*5. Такое распределение дает 1*(6*5/2)+5*(5*4/2)=65 одноцветних вертикально расположенных пар. 32 символа можно распределить равномерно по 6-ти колонкам так: 32=2*6+4*5. Такое распределение дает 2*(6*5/2)+4*(5*4/2)=70 одноцветних вертикально расположенных пар.
Итого одноцветных пар будет как минимум 4*65+1*70=330. А всего вертикально расположенных пар может быть 26*25/2=325. Значит обязательно есть минимум 5 пар строк, где есть две вертикально расположенные одноцветные пары.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 10:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #595419 писал(а):
alexBlack
Конгениально! МБ-лемма спасена!

Ничего пока не вижу конгениального :D
Ну, сделала я замену, получила такой прямоугольник:

Код:
3 3 4 3 2 3 3 4 2 2 4
3 1 2 5 1 4 4 3 1 2 5
3 2 4 1 5 5 4 1 5 4 2
3 5 3 4 2 2 4 2 3 5 1
3 4 5 2 4 1 4 5 2 1 3
4 1 1 4 3 5 1 5 2 5 2
1 3 1 2 1 4 5 4 3 1 2
2 1 5 3 4 2 5 4 5 4 1
4 2 3 5 4 3 1 1 4 2 3
4 5 2 1 3 3 5 2 1 4 4
2 2 1 5 5 4 3 2 2 3 1
1 4 3 1 2 4 3 5 4 4 5
5 5 2 4 1 5 2 4 4 3 3
5 2 3 2 3 2 2 3 5 1 4
2 4 4 3 3 1 2 1 3 3 5

А лемма как не применялась, так и не применяется, даже удвоить прямоугольник не получается.
Было бы странно ожидать, что после замены лемма применится.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:00 


02/05/10
26
Nataly-Mak в сообщении #595442 писал(а):
Ну, сделала я замену, получила такой прямоугольник:

А теперь поставьте их рядом

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И дальше что?
Какое будет третье расширение?

К тому же это уже не совсем применение леммы в том виде, как она представлена в статье.

-- Вс июл 15, 2012 12:10:58 --

Вот лемма 4.3:

Изображение

К чёрту все репликации и редукции! Напридумывали терминов :D

В формулировке леммы нет никаких репликаций и редукций.

Кто-нибудь скажет мне, чему равно $x в лемме в случае, когда С не делится нацело нс С'? :cry:
Здесь ведь, наверное, не обычная целая часть имеется в виду?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:17 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595449 писал(а):
Кто-нибудь скажет мне, чему равно в лемме в случае, когда С не делится нацело нс С'?
Здесь ведь, наверное, не обычная целая часть имеется в виду?


Имеется ввиду обычная целая часть. ЦелаяЧасть(5/2)=2.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:22 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #595451 писал(а):
Nataly-Mak в сообщении #595449 писал(а):
Кто-нибудь скажет мне, чему равно в лемме в случае, когда С не делится нацело нс С'?
Здесь ведь, наверное, не обычная целая часть имеется в виду?


Имеется ввиду обычная целая часть. ЦелаяЧасть(5/2)=2.

Тогда что вы скажете о моём примере?
Уже в третий раз повторяю этот пример:
у меня получилось, что для прямоугольника 6х11 (5,2)-сильной раскраски (именно в смысле леммы 4.3!) в результате применения леммы 4.3 получился прямоугольник 6х33 5-coloring. Пример выше показан.

Так разве здесь $x=2 ??

-- Вс июл 15, 2012 12:30:19 --

В статье приведён прямоугольник 8х28 strong (5,3)-coloring.
По-вашему этот прямоугольник вообще не допускает расширений по лемме 4.3?
Обычная целая часть 5/3 равна 1.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:39 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595403 писал(а):
Прямоугольник 6х11 strong (5,2)-coloring:

A,E,B,D,A,A,A,D,D,C,E,
D,E,D,C,B,C,B,A,E,A,C,
E,D,B,E,C,D,E,E,B,B,C,
C,C,A,A,D,D,B,D,A,D,A,
E,B,A,B,B,E,D,C,D,E,D,
A,A,C,A,E,E,C,B,B,A,B


Где в этом прямоугольнике, хотя бы один полу-прямоугольник? Сдается мне, что этот прямоугольник 6х11 5-strong coloring.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну, наконец-то вы вникли и пошёл предметный разговор :D
Ага, значит этот прямоугольник strong 5-coloring.
Хорошо!

А в примере с прямоугольником 16х10, где у меня получилось $x=2,5. Там-то есть полу-прямоугольники! Правда, в этом примере уже работает МБ-лемма. Так что же получается: в случае с МБ-леммой и х не такой, как в лемме 4.3?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 11:52 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595469 писал(а):
у меня получилось х=2,5


В лемме 4.3 нет понятия размножить исходный прямоугольник 2.5 раза. Лемма не распрастраняется на случай допиливания решения напильником. Это ее большой минус.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 12:08 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ничего я не допиливала напильником в своём примере!
Просто у меня получилось x=c/c' без всякой целой части. А в лемме 4.3 присутствует целая часть.
Но у меня другая лемма :D Поэтому нет никакой целой части.

В общем, плохи обе леммы :wink:

Кстати, в примере с прямоугольником 15х11 тоже должно быть x=2,5.

alexBlack
ещё половинку расширения можете сочинить? :-)
Пока у нас только удвоение исходного прямоугольника, то есть x=2.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 12:15 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595481 писал(а):
ещё половинку расширения можете сочинить?

Половинку мало. 26=10*2,6

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение15.07.2012, 12:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #595486 писал(а):
Nataly-Mak в сообщении #595481 писал(а):
ещё половинку расширения можете сочинить?

Половинку мало. 26=10*2,6

Не поняла!
У нас есть исходный прямоугольник 15х11 (5,2)-сильной раскраски в смысле МБ-леммы.
Должно быть x=5/2=2,5.
То есть 11 столбцов * 2,5 = 27 столбцов (т.к. половина столбца невозможна, я её отбросила).

У нас уже есть 11*2=22 столбца.
Осталось ещё 5 столбцов, то есть как раз половина исходного прямоугольника. Именно это я имею в виду под "ещё половинкой расширения".

-- Вс июл 15, 2012 13:41:41 --

alexBlack в сообщении #595444 писал(а):
Nataly-Mak в сообщении #595442 писал(а):
Ну, сделала я замену, получила такой прямоугольник:

А теперь поставьте их рядом

Поставила :roll:

Код:
3,3,4,3,2,3,3,4,2,2,4,1,1,2,1,4,1,1,2,4,4,2,
3,1,2,5,1,4,4,3,1,2,5,1,5,4,3,5,2,2,1,5,4,3,
3,2,4,1,5,5,4,1,5,4,2,1,4,2,5,3,3,2,5,3,2,4,
3,5,3,4,2,2,4,2,3,5,1,1,3,1,2,4,4,2,4,1,3,5,
3,4,5,2,4,1,4,5,2,1,3,1,2,3,4,2,5,2,3,4,5,1,
4,1,1,4,3,5,1,5,2,5,2,2,5,5,2,1,3,5,3,4,3,4,
1,3,1,2,1,4,5,4,3,1,2,5,1,5,4,5,2,3,2,1,5,4,
2,1,5,3,4,2,5,4,5,4,1,4,5,3,1,2,4,3,2,3,2,5,
4,2,3,5,4,3,1,1,4,2,3,2,4,1,3,2,1,5,5,2,4,1,
4,5,2,1,3,3,5,2,1,4,4,2,3,4,5,1,1,3,4,5,2,2,
2,2,1,5,5,4,3,2,2,3,1,4,4,5,3,3,2,1,4,4,1,5,
1,4,3,1,2,4,3,5,4,4,5,5,2,1,5,4,2,1,3,2,2,3,
5,5,2,4,1,5,2,4,4,3,3,3,3,4,2,5,3,4,2,2,1,1,
5,2,3,2,3,2,2,3,5,1,4,3,4,1,4,1,4,4,1,3,5,2,
2,4,4,3,3,1,2,1,3,3,5,4,2,2,1,1,5,4,5,1,1,3

Да, прямоугольник 15х22 5-coloring получился.

-- Вс июл 15, 2012 13:44:22 --

alexBlack в сообщении #595417 писал(а):
Неявно предполагается, что 2-расширение/репликация - это увеличение цветов на 2.

Почему неявно?
Насколько могу читать по-английски, это явно присутствует в доказательстве леммы 4.3.
Впрочем, я могу ошибаться, т.к. читать по-английски не умею.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 60, 61, 62, 63, 64, 65, 66 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

Сейчас этот форум просматривают: Mikhail_K


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

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