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

[svb]

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

где x=[c/c']

В статье не такие скобочки, а вот такие $x = \left\lfloor {c/c'} \right\rfloor$, т.е. это целая часть от выражения в скобках.

Цитата:

Кстати, там в прямоугольнике 8х18, по-моему, есть ошибка.

Что вы имеете в виду?

Цитата:

Но... тогда почему к этому прямоугольнику применилась лемма 4.3?????
Я её применила и получила прямоугольник 7х36 6-coloring!!

Этот прямоугольник приведён выше (могу повторить). Программа Эда не показывает в нём ошибок

Так быстро не отвечу, хотя, формально, это может случиться, но лучше перепроверить.

Посмотрел. Если не ошибаюсь, то вы при увеличении 5 на 2 получили 1, а должно быть 2 - вот и появится прямоугольник с одинаково окрашенными углами.
- а это уже моя ошибка

[Nataly-Mak]

Да, про скобочки я поняла, что это целая часть.
У меня x=с/c'=6/2=3, тут всё нацело делится.

А ошибка в статье - это есть ошибка (ну, или опечатка), что тут можно иметь в виду? Посмотрите на прямоугольник 8х18 6-coloring в статье, увидите.

Что значит: "формально может случиться"?
То есть лемма применяется не только к тем прямоугольникам, которые в ней указаны, но и к любым другим? Нет, тут что-то не так!

-- Вт июн 19, 2012 07:17:14 --

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

Посмотрел. Если не ошибаюсь, то вы при увеличении 5 на 2 получили 1, а должно быть 2 - вот и появится прямоугольник с одинаково окрашенными углами.
- а это уже моя ошибка

Вот как раз в примере в статье (в прямоугольнике 8х18) при увеличении 5 на 2 получили 2, а должно быть 1
И в результате в прямоугольнике несколько прямоугольничков с вершинами одинакового цвета, чего быть не должно, т. к. этот прямоугольник 6-coloring.

[svb]

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

Вот как раз в примере в статье (в прямоугольнике 8х18) при увеличении 5 на 2 получили 2, а должно быть 1
И в результате в прямоугольнике несколько прямоугольничков с вершинами одинакового цвета, чего быть не должно, т. к. этот прямоугольник 6-coloring.

Мы, может, разные статьи смотрим? Вы про лемму 4.3 ?

-- Вт июн 19, 2012 06:29:20 --

А! Увидел

-- Вт июн 19, 2012 06:33:05 --

Ваш случай:

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

но могло быть и так:

3  1  5  3  1  5
3  1  5  3  1  5

-- Вт июн 19, 2012 06:44:20 --

Похоже, что прямоугольник

3  2
3  2

можно было бы отнести к $\left[ {2} \right]$ (если рассматривать его по модулю 2), но как это сформулировать в лемме?

[Nataly-Mak]

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

Ваш случай:

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

но могло быть и так:

3  1  5  3  1  5
3  1  5  3  1  5

-- Вт июн 19, 2012 06:44:20 --

Похоже, что прямоугольник

3  2
3  2

можно было бы отнести к $\left[ {2} \right]$ (если рассматривать его по модулю 2), но как это сформулировать в лемме?

Пока ничего не поняла

Где написано, что надо рассматривать все вершины прямоугольников по модулю 2?

-- Вт июн 19, 2012 07:53:11 --

Вот так:

3  1  5  3  1  5
3  1  5  3  1  5

вообще быть не могло, потому что все 4 вершины прямоугольника (как я понимаю) не могут быть одного цвета.

[svb]

Так, нигде - это я пишу

Цитата:

вообще быть не могло, потому что все 4 вершины (как я понимаю) не могут быть одного цвета.

но в основном прямоугольнике мог появиться вариант

3  1
3  1

и тогда мы не получили бы 6-coloring

[Nataly-Mak]

Я сделала добавление в посте.
Посмотрите, пожалуйста.

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

[svb]

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

[Nataly-Mak]

А вот это (мой случай):

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

мне нравится.

Посмотрите: все повторяющиеся цвета образуют точно множество всех цветов [1,2,3,4,5,6].
Вот это уже интересно!

-- Вт июн 19, 2012 08:03:32 --

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

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

Угу. Только давайте придерживаться формулировок статьи.

А если вы изобретёте свою лемму, это уже будет новая опера

-- Вт июн 19, 2012 08:07:48 --

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

Так, нигде - это я пишу

Цитата:

вообще быть не могло, потому что все 4 вершины (как я понимаю) не могут быть одного цвета.

но в основном прямоугольнике мог появиться вариант

3  1
3  1

и тогда мы не получили бы 6-coloring

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

[svb]

Вам не угодишь , то вам нравится, то "давайте придерживаться формулировок статьи". Если придерживаться формулировок статьи, то ваш пример не удовлетворял условиям леммы.

[Nataly-Mak]

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

Вам не угодишь , то вам нравится, то "давайте придерживаться формулировок статьи". Если придерживаться формулировок статьи, то ваш пример не удовлетворял условиям леммы.

Мне нравится как раз то, что есть в действительности (мой случай).

А то, что мой пример не удовлетворяет условиям леммы, я и сама вижу.
Тогда почему она применилась к моему прямоугольнику??? Вот о чём мой вопрос!

То есть получается, что лемму можно применять к какому угодно другому прямоугольнику, а не только к такому, как указан в условии леммы? Это как же?

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

И тогда действительно надо формулировать лемму иначе. Но как?

Или же... всё-таки мы чего-то не поняли в этой лемме и определении всех этих "coloring".

[svb]

"Тогда почему она применилась к моему прямоугольнику??? Вот о чём мой вопрос!" - я уже ответил.

-- Вт июн 19, 2012 07:25:36 --

Лемма ничего не говорит о случаях применения ее алгоритма к иным прямоугольникам - ваш случай показывает, как это происходит.

[Nataly-Mak]

Ага, понимаю...
Лемма гарантирует применение для прямоугольников указанного в ней типа и ничего не обещает для других прямоугольников.
Хорошая лемма

Другими словами: условие для исходного прямоугольника "strong (c,c')-coloring" является достаточным для получения с-coloring, но не является необходимым.

Нужна другая теорема: о необходимом и достаточном условии. Может быть, такая теорема уже есть в статье?

Так какой же тогда исходный прямоугольник strong (6,2)-coloring мне надо составлять?

Это я себя спрашиваю

[Pavlovsky]

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

Но! прямоугольник-то 7х36 получился правильный, программа Эда в нём ошибок не показывает, вот он:Код:
Так где и что не так? В чём мои неправильные действия? В непонимании термина strong-(6,2)-coloring?

Забавно. Лемму 4.3 можно усилить!
Пример. У нас есть прямоугольник 7х12 strong-(6,2)-coloring . По лемме 4.3 его можно реплицировать до прямоугольника 7х36. Оказывается, что лемму можно применять для прямоугольников не являющихся strong-(6,2)-coloring.

Добавка к лемме. Прямоугольник 7х12 должен быть в основном strong-(6,2)-coloring. Плюс, допускается один half-mono rectangle (где номера цветов >2) для любых двух строк прямоугольника.

-- Вт июн 19, 2012 09:44:04 --

Главное чтобы при репликации номера были различными.
В примере Наталии есть half-mono rectangle с цветами 3,2. При репликации получается 3,2->5,4->1,6. То есть запрещенного монохроматического прямоугольника у нас не образовалось.

Наталия срочно пишите статью, вы первая, кто заметил эту фичу! :)

[svb]

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

Добавка к лемме. Прямоугольник 7х12 должен быть в основном strong-(6,2)-coloring. Плюс, допускается один half-mono rectangle (где номера цветов >2) для любых двух строк прямоугольника.

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

[Pavlovsky]

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

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

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