Новый конкурс программистов

[Pavlovsky]

Nataly-Mak в сообщении #595395 писал(а):

у меня прошли 2,5 редукции! Не 2!

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

[Nataly-Mak]

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 репликации.
Может, посмотрите уже пример?

[whitefox]

Pavlovsky в сообщении #595394 писал(а):

А кто разрешил делать 3 редукции? Можно делать только две.

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

1  4  3  1
1  4  3  1

в первом случае.

1  4  4  2
1  4  4  2

во втором случае.

[Nataly-Mak]

Вот вам ещё пример. Это уже не на МБ-лемму, а на лемму 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

во втором случае.

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

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

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

[Pavlovsky]

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

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

[whitefox]

Nataly-Mak в сообщении #595403 писал(а):

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

Можно считать, что это две репликации исходного прямоугольника, но редукцию этого прямоугольника мы выполняем только один раз.

Nataly-Mak в сообщении #595403 писал(а):

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

Можно ещё убавлять по 2.
$3\equiv-2\pmod5$

[Pavlovsky]

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

[Nataly-Mak]

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.

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

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

[Pavlovsky]

Пример.
С=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 писал(а):

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

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

[whitefox]

Nataly-Mak в сообщении #595409 писал(а):

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

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

[Nataly-Mak]

Цитата:

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

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

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. Ничего не понимаю!

[Pavlovsky]

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

[Nataly-Mak]

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

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

[Pavlovsky]

репликация = редукция + 1 !!!

[alexBlack]

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

 (12345)
 (34521)

отсюда видно, что возможны и два расширения при переходе

 1 -> 3 -> 5       
 3    5    1   

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

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