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

[svb]

[Nataly-Mak]

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

svb в сообщении #586712 писал(а):

Почему только один? Если любой half-mono rectangle рассматривать по модулю и если при этом не получится одноцветный прямоугольник, то, похоже, алгоритм леммы можно применять.

Ну где то так. Так что формулируем Лемму Макаровой-Беляева-Павловского?!

Pavlovsky
не примазывайтесь третий - лишний.

-- Вт июн 19, 2012 09:19:50 --

Вот эта троица мне нравится:

1 Alex Chernov 19.932400 06-15-2012 @ 20:53:28
2 Nick Gardner 19.899900 06-14-2012 @ 16:35:43
3 Herbert Kociemba 19.864000 06-19-2012 @ 02:05:52

К "джентельменскому" набору, перечисленному Pavlovsky, они добавили ещё кое-что интересненькое

[Pavlovsky]

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

третий - лишний

Ну тогда в качестве гуманитарной помощи.

Лемма. Прямоугольник C-coloring допускает C/k репликацию. Если для любых двух строк выполняется условие. Количество одноцветных ячеек в одной колонке этих строк не больше k. И номера этих цветов дают различные остатки при делении на k.

[svb]

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

Количество одноцветных ячеек в одной колонке этих строк не больше k. И номера этих цветов дают различные остатки при делении на k.

Если цвета по модулю k различны, то их уже не может быть больше k.

[Pavlovsky]

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

К "джентельменскому" набору, перечисленному Pavlovsky, они добавили ещё кое-что интересненькое

К гадалке не ходи. Берут некое решение NxN и перебором пытаются добавить строку и колонку. Для себя на первые два месяца конкурса я наложил табу на реализацию переборных алгоритмов. Ищу "регулярные" решения.

-- Вт июн 19, 2012 10:45:34 --

svb в сообщении #586726 писал(а):

Если цвета по модулю k различны, то их уже не может быть больше k.

Вы меня в соавторы не берете так что дальше сами.

[svb]

Я беру, но за вами строгое доказательство

[Pavlovsky]

svb в сообщении #586729 писал(а):

за вами строгое доказательство

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

[Nataly-Mak]

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

К гадалке не ходи. Берут некое решение NxN и перебором пытаются добавить строку и колонку. Для себя на первые два месяца конкурса я наложил табу на реализацию переборных алгоритмов. Ищу "регулярные" решения.

Дык об этом я тут уже много раз говорила - метод достраивания называется.
Этим методом даже в программе Эда можно пользоваться, что я несколько раз делала. Хорошая игрушка!

Вашу гуманитарную помощь с чем "кушать" надо: с горчицей, с перцем, с хреном, с аджикой, с кетчупом или с каким другим соусом?

-- Вт июн 19, 2012 10:51:09 --

svb
после изобретения новой леммы
хочу попросить вас "перевести" вот этот фрагмент статьи:

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

Example 4.6

вижу такие разбиения:

|1|2|3|
|6|5|4|

|1|6|2|
|5|4|3|

|1|5|6|
|4|3|2|

|1|4|5|
|3|2|6|

|1|3|4|
|2|6|5|

Здесь участвуют как раз 6 цветов. Не являются ли эти разбиения ключом к алгоритму для C=6 (а также и для C=10,12,14,18,20)?

Перед этим в статье сформулирована теорема. Вот с неё и надо начать. Что это за теорема?

После формулировки теоремы приводятся эти примеры ( для 2n=6 и ещё для 2n=8, это я не скопировала).

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

[Nataly-Mak]

Кстати, если мой прямоугольник 7х12

1 1 1 1 1 1 1 5 5 5 5 3
1 2 2 2 2 2 2 1 1 1 1 1
2 1 3 3 3 3 2 1 2 2 2 2
1 2 3 4 4 4 3 2 2 3 3 4
1 2 4 3 5 5 4 3 3 2 4 5
1 2 5 5 3 6 5 4 4 4 2 6
1 2 6 6 6 3 6 6 6 6 6 2

не strong-(6,2)-coloring, но зато он strong-(6,3)-coloring!

И к нему опять же можно применить лемму, только теперь должен получиться прямоугольник 7Х24 6-coloring. И он действительно получается:

1 1 1 1 1 1 1 5 5 5 5 3 4 4 4 4 4 4 4 2 2 2 2 6
1 2 2 2 2 2 2 1 1 1 1 1 4 5 5 5 5 5 5 4 4 4 4 4
2 1 3 3 3 3 2 1 2 2 2 2 5 4 6 6 6 6 5 4 5 5 5 5
1 2 3 4 4 4 3 2 2 3 3 4 4 5 6 1 1 1 6 5 5 6 6 1
1 2 4 3 5 5 4 3 3 2 4 5 4 5 1 6 2 2 1 6 6 5 1 2
1 2 5 5 3 6 5 4 4 4 2 6 4 5 2 2 6 3 2 1 1 1 5 3
1 2 6 6 6 3 6 6 6 6 6 2 4 5 3 3 3 6 3 3 3 3 3 5

Эхма, какой же мне изобрести прямоугольник, чтобы получить 36х36 6-coloring?

[svb]

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

А сильно подозреваю, что они очень важные.

- аналогично. Давайте начнем.Итак,

Теорема 4.4
Пусть $c \ge 2$, тогда
1. Существует раскраска strong c-coloring прямоугольников $ G_{c + 1,m} $, где $\[ m = \left( {\begin{array}{{20}c} {c + 1} \\ 2 \\ \end{array}} \right) \] $
2. Существует раскраска c-coloring прямоугольников $ G_{c + 1,m} $, где $\[ m = c \left( {\begin{array}{{20}c} {c + 1} \\ 2 \\ \end{array}} \right) \] $

[Nataly-Mak]

Ага, спасибо.

Это вроде понятно.
Там дальше идёт пример для C=5.

1. Существует раскраска strong 5-coloring прямоугольника G6,15;
2. Существует раскраска 5-coloring прямоугольника G6,75.

Верно?

[svb]

Пока никак не пойму, как этот пример строить.

[Nataly-Mak]

Ну, если вы не поймёте, я тем более не пойму.
Сейчас глянула, там идёт описание (доказательство), но... перевод, сделайте, пожалуйста, перевод

[dimkadimon]

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

Example 4.6

вижу такие разбиения:

|1|2|3|
|6|5|4|

|1|6|2|
|5|4|3|

|1|5|6|
|4|3|2|

|1|4|5|
|3|2|6|

|1|3|4|
|2|6|5|

Здесь участвуют как раз 6 цветов. Не являются ли эти разбиения ключом к алгоритму для C=6 (а также и для C=10,12,14,18,20)?

Здесь цифра 1 остается на месте, а все остальные цифры врашаются по кругу по часовой стрелке.

[svb]

Похоже, что рассматриваются колонки с различными вариантами расположения цвета 5 - этих вариантов, конечно, 15. Остальные цвета просто идут по порядку. Как там написано, реальный порядок этих цветов не имеет значения. А дальше идет доказательство правильности раскраски, которому мы искренне верим, т.к. оно нам не очень и нужно в силу своей очевидности .