2014 dxdy logo

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

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




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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595395 писал(а):
у меня прошли 2,5 редукции! Не 2!


Как видите 2,5 репликации не всегда проходят. Формулируйте расширенную МБ-лемму. :-)

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #595396 писал(а):
Pavlovsky в сообщении #587516 писал(а):
Макарова-Беляев (c,k)-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B. A и B дают различные остатки при делении на k. В частном случае, при k=2 имеют разную четность.


Когда это формулировал, неявно полагал, что C lделится на k на цело. При этом допускается С/k репликаций. Если C не делится на k, то количество допустимых репликаций целая часть от C/k.

Блин!
Да не проходят в этом примере даже 2 репликации! Целая часть от 5/2 сколько будет? 2?

Pavlovsky
вы мои посты вообще читаете?
Ещё раз повторяю: в этом примере не проходят даже 2 репликации.
Может, посмотрите уже пример?

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


19/12/10
1546
Pavlovsky в сообщении #595394 писал(а):
А кто разрешил делать 3 редукции? Можно делать только две.

Речь идёт не о трёх или двух редукциях, а только об одной.
На 2 или на 3 соответственно. В обоих случаях получаем монохромный прямоугольник.
Код:
1  4  3  1
1  4  3  1
в первом случае.
Код:
1  4  4  2
1  4  4  2
во втором случае.

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


22/03/08

7154
Саратов
Вот вам ещё пример. Это уже не на МБ-лемму, а на лемму 4.3.

Прямоугольник 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

Ответьте на вопрос: сколько по лемме 4.3 этот прямоугольник допускает репликаций? Две?
Я сделала три репликации (для whitefox: утроила исходный прямоугольник), вот какой получился прямоугольник 6х33 5-coloring:

Код:
33,6,A,E,B,D,A,A,A,D,D,C,E,C,B,D,A,C,C,C,A,A,E,B,E,D,A,C,E,E,E,C,C,B,D,D,E,D,C,B,C,B,A,E,A,C,
A,B,A,E,D,E,D,C,B,C,E,C,D,C,B,A,B,A,E,D,E,B,E,D,B,E,C,D,E,E,B,B,C,B,A,D,B,E,A,B,B,D,D,E,D,C,
A,D,B,C,D,D,A,A,B,C,C,A,A,D,D,B,D,A,D,A,E,E,C,C,A,A,D,A,C,A,C,B,B,E,E,C,C,A,C,E,C,E,E,B,A,B,
B,E,D,C,D,E,D,B,D,C,D,D,B,A,E,A,B,A,D,A,E,A,A,D,C,B,C,D,C,A,A,C,A,E,E,C,B,B,A,B,C,C,E,C,B,B,
E,D,D,C,D,E,E,B,E,D,D,B,A,A,E,A


Так чему же равна целая часть 5/2 в лемме 4.3? Там, может, не обычная целая часть имеется в виду?

-- Вс июл 15, 2012 09:36:42 --

whitefox в сообщении #595402 писал(а):
Pavlovsky в сообщении #595394 писал(а):
А кто разрешил делать 3 редукции? Можно делать только две.

Речь идёт не о трёх или двух редукциях, а только об одной.
На 2 или на 3 соответственно. В обоих случаях получаем монохромный прямоугольник.
Код:
1  4  3  1
1  4  3  1
в первом случае.
Код:
1  4  4  2
1  4  4  2
во втором случае.

Не, ну совсем запутались :D
Когда мы один раз прибавили столбцы, это я уже понимаю как удвоение исходного прямоугольника, т.е. две репликации.

Ну, тогда даже и один раз тут не получается прибавить столбцы! Вообще не получается ни одной репликации.

И не надо здесь прибавлять по 3, здесь же (5,2)-раскраска. Прибавлять надо по 2.

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


21/02/10
1594
Екатеринбург
Макарова-Беляев (c,k)-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B. A и B дают различные остатки при делении на k. В частном случае, при k=2 имеют разную четность.

Предварительный диагноз такой МБ-лемму можно применять, если C делится на k на цело.
Для взаимнопростых (C,k)=1, надо смотреть.

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


19/12/10
1546
Nataly-Mak в сообщении #595403 писал(а):
Когда мы один раз прибавили столбцы, это я уже понимаю как удвоение исходного прямоугольника, т.е. две репликации.
Можно считать, что это две репликации исходного прямоугольника, но редукцию этого прямоугольника мы выполняем только один раз.
Nataly-Mak в сообщении #595403 писал(а):
И не надо здесь прибавлять по 3, здесь же (5,2)-раскраска. Прибавлять надо по 2.
Можно ещё убавлять по 2.
$3\equiv-2\pmod5$

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


21/02/10
1594
Екатеринбург
Смысл МБ-леммы как раз в том, что при репликиции числа остаются в том же классе вычетов по модулю С. Когда (C,k)=1 взаимнопростые. Это условие не выполняется.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #595404 писал(а):
Предварительный диагноз такой МБ-лемму можно применять, если C делится на k на цело.
Для взаимнопростых (C,k)=1, надо смотреть.

Неправильный диагноз!
Ведь есть же пример применения леммы для С=5: прямоугольник 16х10 с (5,2)-раскраской.
Вы почему этот пример игнорируете???

С сильной раскраской (5,2) по лемме 4.3 привела пример! Получилось утроение исходного прямоугольника 6х11. Это сколько репликаций выполнено: две или три? Ни черта не понимаю!

В статье приведён пример для (6,2)-сильной раскраски по лемме 4.3; там исходный прямоугольник тоже утроен. Я понимаю это как три репликации, здесь-то всё нацело делится: 6/2=3.

Давайте будем говорить уже о репликациях, а то я совсем запуталась: то редукции, то репликации.

Но, однако, вернёмся к примеру. В нём даже две(!) репликации не проходят! То есть даже один раз мы не можем выполнить прибавление.
Так значит, лемма наша ни черта не работает :-(

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


21/02/10
1594
Екатеринбург
Пример.
С=6
четные числа 2,4,6; нечетные числа 1,3,5. При репликации прибавляем 2 по модулю 6. Четные числа переходят в четные;нечетные числа в нечетные. То есть если у нас есть четно-нечетный прямоугольник с цветами A,B, то при репликации цвет A никогда не попадет в цвет B.

С=5
При репликации прибавляем 2 по модулю 5. Тогда скажем 4 перейдет в 1. То есть число поменяет четность. Появляется возможность, что в четно-нечетном прямоугольнике с цветами A,B, цвет A попадет в цвет B.

-- Вс июл 15, 2012 11:05:26 --

Nataly-Mak в сообщении #595409 писал(а):
Давайте будем говорить уже о репликациях, а то я совсем запуталась: то редукции, то репликации.

А чем репликация отличается от редукции??

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


19/12/10
1546
Nataly-Mak в сообщении #595409 писал(а):
С сильной раскраской (5,2) по лемме 4.3 привела пример! Полуилось утроение исходного прямоугольника 6х11. Это сколько репликаций выполнено: две или три? Ни черта не понимаю!

При утроении исходного прямоугольника, вы берёте сам этот прямоугольник и две его редуцированные формы. То есть редукцию выполняете два раза. Можно считать, что при этом Вы имеете три различные репликации исходного прямоугольника (одна из которых совпадает с этим исходным прямоугольником).

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


22/03/08

7154
Саратов
Цитата:
А чем репликация отличается от редукции??


Вот тут написано о репликации и о редукции:

whitefox в сообщении #595406 писал(а):

Nataly-Mak в сообщении #595403 писал(а):
Когда мы один раз прибавили столбцы, это я уже понимаю как удвоение исходного прямоугольника, т.е. две репликации.
Можно считать, что это две репликации исходного прямоугольника, но редукцию этого прямоугольника мы выполняем только один раз.


-- Вс июл 15, 2012 10:15:42 --

whitefox в сообщении #595411 писал(а):
Nataly-Mak в сообщении #595409 писал(а):
С сильной раскраской (5,2) по лемме 4.3 привела пример! Полуилось утроение исходного прямоугольника 6х11. Это сколько репликаций выполнено: две или три? Ни черта не понимаю!

При утроении исходного прямоугольника, вы берёте сам этот прямоугольник и две его редуцированные формы. То есть редукцию выполняете два раза. Можно считать, что при этом Вы имеете три различные репликации исходного прямоугольника (одна из которых совпадает с этим исходным прямоугольником).


O! Ну, так, значит, репликций всё-таки три? Ну вот, так я и поняла из пример в статье, там тоже три репликации. Но там пример для (6,2)-сильной раскраски. Тут 6/2=3.
А вот сколько репликаций будет в случае (5,2)-сильной раскраски (по лемме 4.3)? У меня ведь тоже три получилось! А в лемме написано, что целая часть 5/2. Так ведь целая часть 5/2 равна 2, а не 3. Ничего не понимаю!

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


21/02/10
1594
Екатеринбург
Получается при взаимнопростых числах (C,k) можно применять только лемму 4.3 в классической постановке. Там все устроено так, например (5,2)-сильная раскраска. Можно делать репликацию всего два раза. При этом числа 1,2 перейдут в числа 3,4. То есть будут меньше 5-ти. Тогда их не надо брать по модулю 5. И значит они не сменят свою четность/нечетность.

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


22/03/08

7154
Саратов
Так, вернёмся к МБ-лемме.
Формулировка леммы никуда не годится! Огромный минус авторам.
Лемму на доработку! :D

Получается, что для случая, когда С делится на С' нацело, лемма работает. В противном случае она то работает, то не работает.

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


21/02/10
1594
Екатеринбург
репликация = редукция + 1 !!!

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


02/05/10
26
Неявно предполагается, что 2-расширение/репликация - это увеличение цветов на 2. Это не так. Можно использовать любую замену. Нам важно сохранение четности, поэтому для примера выше (того, где не получается расширение) можно взять замену:

Код:
(12345)
(34521)


отсюда видно, что возможны и два расширения при переходе
Код:
1 -> 3 -> 5       
3    5    1   


но тогда не должно быть четных пар. Соответственно при четных C имеем две такие цепочки и всегда возможны два расширения (утроение).

reduction - сокращение/снижение/свертывание, по-моему термин не подходит

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

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



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

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


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

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