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

[Pavlovsky]

Похоже С10N100 у меня не будет. Максимум чего смог выжать из своего подхода С10N91. Так бывает. Зато согрелся.

-- Сб июл 14, 2012 17:55:32 --

Вот такая строка для С=10 получилась. Закономерностей море.

(Оффтоп)

[whitefox]

Складывается впечатление, что редукцией задачу C5N26 не решить.

Выскажу гипотезу:
Любой 5-сильно окрашенный прямоугольник 26х6 имеет не менее 15 ошибок.

[Nataly-Mak]

whitefox
попробуйте искать прямоугольник 26x11 с (5,2)-раскраской по нашей лемме.

Гарантии никакой!

Интересный момент, я его уже отмечала выше: в случае (5,2)-раскраски в соответствии с требованиями нашей леммы размножение происходит не 2 и не 3 раза, а именно 2,5 раза!
То есть в данном случае 27 столбцов гарантированы.
Можно попробовать на прямоугольнике nx11 (n<26) с (5,2)-раскраской по нашей лемме. Должен получиться прямоугольник nx27 5-coloring.

Нет, не получилось 27 столбцов. Что-то я тут напутала, надо разбираться. Вот с этой целой частью [5/2]. Был у меня выше аналогичный пример, значит, аналогия не полная.
Или же исходный прямоугольник сейчас составила неправильно.

whitefox
можете проверить мой прямоугольник 15х11?

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

Удовлетворяет ли он требованиям (5,2)-раскраски по нашей лемме?
У меня что-то сегодня совсем голова не варит, с утра жара жарит

Если удовлетворяет, то как его размножать? Сколько будет столбцов в итоговом прямоугольнике? Прибавлять по 2?

Где я ошиблась?

[whitefox]

Nataly-Mak
Подозреваю, что при $\mathrm{N}>\mathrm{C^2}$ редукция в принципе не возможна, ни при использовании
сильной $\mathrm{C}$-раскраски ни при использовании сильной $(\mathrm{C}{,}\mathrm{C'})$-раскраски.

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

[Nataly-Mak]

У меня лемма не работает
Из приведённого выше прямоугольника я даже один раз не могу прибавить столбцы, то есть получить прямоугольник 15х22 5-coloring. Получается куча ошибок.
В чём причина? Исходный прямоугольник 15х11 правильный?

Совсем, похоже, перегрелась

-- Вс июл 15, 2012 07:57:21 --

Вот нашла аналогичный пример, это прямоугольник 16х10 с (5,2)-раскраской в соответствии с требованиями нашей леммы:

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

Этот-то прямоугольник у меня размножился! И в итоговом прямоугольнике получилось 25 столбцов! И он получился 5-coloring, без ошибок!

Сейчас ещё раз применю к нему лемму, может тогда ошиблась тоже.

[whitefox]

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

whitefox
можете проверить мой прямоугольник 15х11?

Проверил, этот прямоугольник (5,2)-сильно раскрашенный (по МБ-лемме).

-- 15 июл 2012, 07:12 --

Нда-а-а
Что-то редукция не получается.
Возможно в моей программе проверки ошибка,
и на самом деле прямоугольник не (5,2)-сильно раскрашенный.

[Nataly-Mak]

Вот результат применения леммы - прямоугольник 16х25 5-coloring:

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

Проверила в программе Эда, всё правильно, ошибок нет:

25,16,A,A,A,A,A,B,B,B,B,B,C,C,C,C,C,D,D,D,D,D,E,E,E,E,E,A,D,B,C,B,B,E,C,D,C,C,A,D,E,D,D,B,E,
A,E,E,C,A,B,A,A,C,D,B,C,B,D,E,C,D,C,E,A,D,E,D,A,B,E,A,E,B,C,A,B,A,B,C,D,D,B,C,D,E,E,C,D,E,A,A
,D,E,A,B,B,E,A,B,C,C,B,B,B,B,A,C,C,C,C,B,D,D,D,D,C,E,E,E,E,D,A,A,A,A,E,B,C,A,D,B,C,D,B,E,C,D,
E,C,A,D,E,A,D,B,E,A,B,E,C,A,B,D,C,A,C,C,E,D,B,D,D,A,E,C,E,E,B,A,D,A,A,C,B,E,B,B,A,D,C,D,C,B,E
,D,E,D,C,A,E,A,E,D,B,A,B,A,E,C,B,C,C,C,C,C,A,D,D,D,D,B,E,E,E,E,C,A,A,A,A,D,B,B,B,B,E,C,B,D,A,
B,D,C,E,B,C,E,D,A,C,D,A,E,B,D,E,B,A,C,E,A,C,A,B,D,C,D,B,C,E,D,E,C,D,A,E,A,D,E,B,A,B,E,A,C,B,
C,D,A,B,D,D,E,B,C,E,E,A,C,D,A,A,B,D,E,B,B,C,E,A,C,D,D,D,D,A,E,E,E,E,B,A,A,A,A,C,B,B,B,B,D,C,
C,C,C,E,D,A,C,B,B,E,B,D,C,C,A,C,E,D,D,B,D,A,E,E,C,E,B,A,A,D,B,A,C,C,E,C,B,D,D,A,D,C,E,E,B,E,
D,A,A,C,A,E,B,B,D,C,B,A,D,E,D,C,B,E,A,E,D,C,A,B,A,E,D,B,C,B,A,E,C

Так почему же с прямоугольником 15х11 ни черта не получается?

У меня только одна версия: этот прямоугольник неправильно составлен, то есть он не удовлетворяет требованиям (5,2)-раскраски по нашей лемме.

[whitefox]

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

У меня только одна версия: этот прямоугольник неправильно составлен, то есть он не удовлетворяет требованиям (5,2)-раскраски по нашей лемме.

Ничего не понимаю.
МБ-лемма безусловно верна.
Прямоугольник 15х11 проверил двумя разными программами,
обе ответили, что этот прямоугольник (5,2)-сильно раскрашен в соответствии
с МБ-леммой.
Но редукция не проходит

Ручную проверку прямоугольника делать лень, буду писать новую программу проверки.

[Pavlovsky]

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

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

Число 5 нельзя разложить на сомножетели. Поэтому МБ-лемму надо применять осторожно. С числом 5 не должно быть полу-прямоугольников. Для оставшихся чисел 1-4 применяем МБ-лемму.

-- Вс июл 15, 2012 09:52:27 --

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

Подозреваю, что при редукция в принципе не возможна, ни при использовании
сильной -раскраски ни при использовании сильной -раскраски.

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

Полностью согласен.

[Nataly-Mak]

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

Число 5 нельзя разложить на сомножетели. Поэтому МБ-лемму надо применять осторожно. С числом 5 не должно быть полу-прямоугольников. Для оставшихся чисел 1-4 применяем МБ-лемму.

Ничего не поняла! Каких не должно быть полу-прямоугольников с числом 5?

Я же привела совершенно аналогичный пример с прямоугольником 16х10 тоже с (5,2)-раскраской. И в этом примере всё получилось.
И в нём есть прямоугольники с вершинами (5,5), например, такой:

4 5
4 5

Так почему же в этом примере всё получилось?

Вы вот как раз и процитировали прямоугольник 16х10, с которым всё получилось!
А не получается с прямоугольником 15х11.
Вот с этим:

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

[whitefox]

Нет, в моей программе ошибки нет.
Зато МБ-лемма нуждается в уточнение.
Так в первых двух строчках встречаются:

1  4
1  4

которые при редукции на 2 переходят в:

3  1
3  1

а при редукции на 3 переходят в

4  2
4  2

В обоих случаях имеем монохромный прямоугольник.

[Pavlovsky]

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

Вот нашла аналогичный пример, это прямоугольник 16х10 с (5,2)-раскраской в соответствии с требованиями нашей леммы:
Этот-то прямоугольник у меня размножился! И в итоговом прямоугольнике получилось 25 столбцов! И он получился 5-coloring, без ошибок!

25 столбцов это как? После репликации количество столбцов должно быть кратно 10.

-- Вс июл 15, 2012 10:14:45 --

whitefox

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

[Nataly-Mak]

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

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

Вот нашла аналогичный пример, это прямоугольник 16х10 с (5,2)-раскраской в соответствии с требованиями нашей леммы:
Этот-то прямоугольник у меня размножился! И в итоговом прямоугольнике получилось 25 столбцов! И он получился 5-coloring, без ошибок!

25 столбцов это как? После репликации количество столбцов должно быть кратно 10.

Да очень просто! Обрезала 5 столбцов! Хотя надо проверить, может и с 30 столбцами будет нормально.
А 16х25 точно 5-coloring. Не придерётесь. в программе Эда проверено.

-- Вс июл 15, 2012 09:16:20 --

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

whitefox

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

Дык в этом примере и две редукции не получаются!!!

-- Вс июл 15, 2012 09:18:29 --

Pavlovsky
вы бы уж проверили оба примера, прежде чем выдавать какие-то заключения с наскоку.
Во втором примере (с прямоугольником 16х10) у меня прошли 2,5 редукции! Не 2!

[Pavlovsky]

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

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

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

[Nataly-Mak]

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

Зато МБ-лемма нуждается в уточнение.
Так в первых двух строчках встречаются:

1  4
1  4

которые при редукции на 2 переходят в:

3  1
3  1

Так какое же это должно быть уточнение