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

[Nataly-Mak]

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

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

Блин! Вы на пример посмотрите в классической лемме 4.3.
Прямоугольник 6х11 (5,2)-сильная ракраска в смысле леммы 4.3.
А репликаций у меня три! То есть исходный прямоугольник и два редуцированных.
Итоговый прямоугольник 6х33.

Или я опять ничего не поняла с репликациями и редукциями, или это вы ничего не поняли.
Сколько у меня в этом примере репликаций? Сколько редукций?
По-моему так: редукции две, репликации три.
Вы же сами вон крупно написали: репликация = редукция + 1.
Репликация = 3
редукция = 2
3 = 2 +1

[Pavlovsky]

alexBlack
Конгениально! МБ-лемма спасена!

[Nataly-Mak]

alexBlack
так можно в этом примере (прямоугольник 15х11) применить лемму или всё же нельзя?
При замене, которую вы привели, сколько проходит репликаций? Одна или две?

А сколько их должно быть в случае (5,2)-сильной раскраски по лемме 4.3?

Так мне и не ответили на этот вопрос: сколько у меня репликаций в примере с прямоугольником 6х11 (5,2)-сильная раскраска? Это пример по лемме 4.3. Итоговый прямоугольник получился 6х33 5-coloring. Я считаю, что здесь три репликации.

Всё!
У меня голова треснула
Я ушла.

[Pavlovsky]

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

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

5-сильно окрашенный прямоугольник 26х6 не существует.
Sirgedas
26*6=156. 156 ячеек распределим равномерно (почему равномерно больше объяснять не буду) по 5-ти цветам. 156=31*4+32*1. 31 символ можно распределить равномерно по 6-ти колонкам так: 31=1*6+5*5. Такое распределение дает 1*(6*5/2)+5*(5*4/2)=65 одноцветних вертикально расположенных пар. 32 символа можно распределить равномерно по 6-ти колонкам так: 32=2*6+4*5. Такое распределение дает 2*(6*5/2)+4*(5*4/2)=70 одноцветних вертикально расположенных пар.
Итого одноцветных пар будет как минимум 4*65+1*70=330. А всего вертикально расположенных пар может быть 26*25/2=325. Значит обязательно есть минимум 5 пар строк, где есть две вертикально расположенные одноцветные пары.

[Nataly-Mak]

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

alexBlack
Конгениально! МБ-лемма спасена!

Ничего пока не вижу конгениального
Ну, сделала я замену, получила такой прямоугольник:

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

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

[alexBlack]

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

Ну, сделала я замену, получила такой прямоугольник:

А теперь поставьте их рядом

[Nataly-Mak]

И дальше что?
Какое будет третье расширение?

К тому же это уже не совсем применение леммы в том виде, как она представлена в статье.

-- Вс июл 15, 2012 12:10:58 --

Вот лемма 4.3:



К чёрту все репликации и редукции! Напридумывали терминов

В формулировке леммы нет никаких репликаций и редукций.

Кто-нибудь скажет мне, чему равно $x в лемме в случае, когда С не делится нацело нс С'?
Здесь ведь, наверное, не обычная целая часть имеется в виду?

[Pavlovsky]

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

Кто-нибудь скажет мне, чему равно в лемме в случае, когда С не делится нацело нс С'?
Здесь ведь, наверное, не обычная целая часть имеется в виду?

Имеется ввиду обычная целая часть. ЦелаяЧасть(5/2)=2.

[Nataly-Mak]

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

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

Кто-нибудь скажет мне, чему равно в лемме в случае, когда С не делится нацело нс С'?
Здесь ведь, наверное, не обычная целая часть имеется в виду?

Имеется ввиду обычная целая часть. ЦелаяЧасть(5/2)=2.

Тогда что вы скажете о моём примере?
Уже в третий раз повторяю этот пример:
у меня получилось, что для прямоугольника 6х11 (5,2)-сильной раскраски (именно в смысле леммы 4.3!) в результате применения леммы 4.3 получился прямоугольник 6х33 5-coloring. Пример выше показан.

Так разве здесь $x=2 ??

-- Вс июл 15, 2012 12:30:19 --

В статье приведён прямоугольник 8х28 strong (5,3)-coloring.
По-вашему этот прямоугольник вообще не допускает расширений по лемме 4.3?
Обычная целая часть 5/3 равна 1.

[Pavlovsky]

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

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

Где в этом прямоугольнике, хотя бы один полу-прямоугольник? Сдается мне, что этот прямоугольник 6х11 5-strong coloring.

[Nataly-Mak]

Ну, наконец-то вы вникли и пошёл предметный разговор
Ага, значит этот прямоугольник strong 5-coloring.
Хорошо!

А в примере с прямоугольником 16х10, где у меня получилось $x=2,5. Там-то есть полу-прямоугольники! Правда, в этом примере уже работает МБ-лемма. Так что же получается: в случае с МБ-леммой и х не такой, как в лемме 4.3?

[Pavlovsky]

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

у меня получилось х=2,5

В лемме 4.3 нет понятия размножить исходный прямоугольник 2.5 раза. Лемма не распрастраняется на случай допиливания решения напильником. Это ее большой минус.

[Nataly-Mak]

Ничего я не допиливала напильником в своём примере!
Просто у меня получилось x=c/c' без всякой целой части. А в лемме 4.3 присутствует целая часть.
Но у меня другая лемма Поэтому нет никакой целой части.

В общем, плохи обе леммы

Кстати, в примере с прямоугольником 15х11 тоже должно быть x=2,5.

alexBlack
ещё половинку расширения можете сочинить?
Пока у нас только удвоение исходного прямоугольника, то есть x=2.

[Pavlovsky]

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

ещё половинку расширения можете сочинить?

Половинку мало. 26=10*2,6

[Nataly-Mak]

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

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

ещё половинку расширения можете сочинить?

Половинку мало. 26=10*2,6

Не поняла!
У нас есть исходный прямоугольник 15х11 (5,2)-сильной раскраски в смысле МБ-леммы.
Должно быть x=5/2=2,5.
То есть 11 столбцов * 2,5 = 27 столбцов (т.к. половина столбца невозможна, я её отбросила).

У нас уже есть 11*2=22 столбца.
Осталось ещё 5 столбцов, то есть как раз половина исходного прямоугольника. Именно это я имею в виду под "ещё половинкой расширения".

-- Вс июл 15, 2012 13:41:41 --

alexBlack в сообщении #595444 писал(а):

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

Ну, сделала я замену, получила такой прямоугольник:

А теперь поставьте их рядом

Поставила

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

Да, прямоугольник 15х22 5-coloring получился.

-- Вс июл 15, 2012 13:44:22 --

alexBlack в сообщении #595417 писал(а):

Неявно предполагается, что 2-расширение/репликация - это увеличение цветов на 2.

Почему неявно?
Насколько могу читать по-английски, это явно присутствует в доказательстве леммы 4.3.
Впрочем, я могу ошибаться, т.к. читать по-английски не умею.