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

[dimkadimon]

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

Zealint в сообщении #587477 писал(а):

Почему бы не добавить в программу возможность работать (c,c')-coloring? Или никому не нужно?

В свете леммы Макаровой-Беляева, понятие (c,c')-coloring становится не актуальным.

Пример (6,2)-coloring допускает half-прямоугольники с ракраской сторон (1,2). Тогда можем применять лемму 4.3

Лемма Макаровой-Беляева допускает half-прямоугольники у которых одна сторона имеет четный цвет, другая нечетный (в т.ч. 1,2). Как видите усиление по сравнению с леммой 4.3 колосальное!

Значит, если я правильно понял, лемма Макаровой-Беляева это лемма 4.3 только теперь полу-прямоугольники могут иметь одну чётную сторону и одну нечётную сторону?

Давайте дадим такое определение:

Макарова-Беляев (c,c')-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B

1) A!=B
2) 1<= A, B <= c'
3) A mod 2 != B mod 2

3) сильнее 1), поэтому получаем:

1) 1<= A, B <= c'
2) A mod 2 != B mod 2

[Pavlovsky]

dimkadimon в сообщении #587515 писал(а):

Значит, если я правильно понял, лемма Макаровой-Беляева это лемма 4.3 только теперь полу-прямоугольники могут иметь одну чётную сторону и одну нечётную сторону?

Верно когда c'=2.

-- Чт июн 21, 2012 11:53:05 --

dimkadimon в сообщении #587515 писал(а):

Макарова-Беляев (c,c')-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B

Не так

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

[dimkadimon]

Цитата:

Вот набор из 25 непересекающихся комбинаций из чисел 1,2,3,4,5:

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

Найден форумчанином на форуме nazva.net

Очень красивые комбинации! Закономерность и гармония!

И решение по базовому алгоритму №1 из этого набора получается элементарно.
Я даже нашла и изложила здесь два способа, как этот прямоугольник 25х5 strong-5-coloring превратить в квадрат 25х25 5-coloring. Оба способа очень простые в реализации.

Может быть, расскажете ваш четвёртый метод для С=5?
Научное любопытство

Вот это очень красивое решение! Я написал программу которая генерирует такие strong c-coloring для С^2 х С для простых С.

Мой четвёртый метод для 25х25 5-coloring совершено другой. Он скорее ближе к методу из статьи Немцов. Кстати, а почему никто не обсуждает эту статью?

Удивительно что столько разных решений для простых С, но они все приводят к одному результату - ни один квадрат не получаеться увеличить!

[Pavlovsky]

dimkadimon в сообщении #587519 писал(а):

статьи Немцов

Это где? Чего то не видел этой статьи.

[dimkadimon]

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

dimkadimon в сообщении #587519 писал(а):

статьи Немцов

Это где? Чего то не видел этой статьи.

На главном сайте выложены 3 статьи немцов. Их зовут Bernd Steinbach и Christian Posthoff. После 2.5 года поиска они первые нашли 17х17 и 18х18 4-coloring.

[Pavlovsky]

Аааа! Немцов=НемцЕв!

[dimkadimon]

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

Аааа! Немцов=НемцЕв!

Ах да... я просто плохо по Русски пишу...

[Pavlovsky]

dimkadimon в сообщении #587522 писал(а):

На главном сайте выложены 3 статьи немцов. Их зовут Bernd Steinbach и Christian Posthoff. После 2.5 года поиска они первые нашли 17х17 и 18х18 4-coloring.

Несколько раз просмотрел эти статьи. Ничего интересного, кроме конечного результата, не увидел. Надо будет еще раз внимательно прочитать эти статьи.

[Nataly-Mak]

dimkadimon в сообщении #587527 писал(а):

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

Аааа! Немцов=НемцЕв!

Ах да... я просто плохо по Русски пишу...

Вы довольно хорошо пишете по-русски. По крайней мере, я вас очень хорошо понимаю.

[dimkadimon]

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

dimkadimon в сообщении #587527 писал(а):

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

Аааа! Немцов=НемцЕв!

Ах да... я просто плохо по Русски пишу...

Вы довольно хорошо пишете по-русски. По крайней мере, я вас очень хорошо понимаю.

Спасибо - это приятно. Я только до 4ого класса учился в России, а потом учился по Русским учебникам и писал письма бабушкам. Поэтому Русский язык у меня немного страдает и постепенно забывается :(

-- 21.06.2012, 16:28 --

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

dimkadimon в сообщении #587522 писал(а):

На главном сайте выложены 3 статьи немцов. Их зовут Bernd Steinbach и Christian Posthoff. После 2.5 года поиска они первые нашли 17х17 и 18х18 4-coloring.

Несколько раз просмотрел эти статьи. Ничего интересного, кроме конечного результата, не увидел. Надо будет еще раз внимательно прочитать эти статьи.

В принципе сам метод (через SAT solver) у них очень скучный и некрасивый. Но они изобрели один трюк который уменьшил количество комбинаций цветов от 4^(18х18) до 4^(18х18/4) и это очень красиво. Очень хотелось бы обсудить этот трюк.

[Pavlovsky]

dimkadimon в сообщении #587534 писал(а):

количество комбинаций цветов от 4^(18х18) до 4^(18х18/4)

Если в C-coloring прямоуголньнике поменять две строки (колонки) местми, то полученный прямоугольник тоже будет C-coloring. То есть можно искать прямоугольники, где номера цветов в первой строке и в первой колонке составляют неубывающую последовательность. Не считал, но по первым прикидкам количество вариантов (для квадрата 18х18 С=4) получится гораздо меньше 4^(18х18/4).

Еще раз рекомендую книгу Ф.Кортеси "Введение в конечные геометрии". В ней описывается механизм Г-таблиц. Умелое использование этого механизма может дать катострофическое уменьшение узлов в дереве перебора.

[Nataly-Mak]

Решение C=5, N=20x20, не максимальное, но очень изящное.
Тоже интернетовское.
Наверное, регулярное

[Nataly-Mak]

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

Сейчас посмотрела в черновики. Решение C=5, N=25x25 я строила методом, описанным Pavlovsky в самом начале темы.
Искала разбиения, потом по этим разбиениям строила прямоугольник 25х5 strong-5-coloring, вот какой прямоугольник у меня получился:

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

Достаточно посмотреть на полную группу попарно ортогональных латинских квадратов 5-го порядка, чтобы увидеть, откуда взялись уникальные перестановки этого прямоугольника:



Бывает же такое затмение разума, когда не видишь очевидного

[svb]

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

Решение C=5, N=20x20, не максимальное, но очень изящное.

Аналогичное имеется и для C=5, N=25x25, и даже для C=6, N=36x36

[Nataly-Mak]

svb
так и заставите меня придумать решение C=6, N=36x36
а я уж решила остановиться на N=31x31.
Ну, не лезет мне в голову это "36"