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

[Alexu007]

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

Вы читать умеете?
Написано "решения для C=15, 21... получаю из решений для C=14, 20...". Что непонятно?
Где вы видите "решение для C=15, 21x21"???
Поясняю ещё раз: решение для C=15 (N=184x184) получаю из решения для С=14 (N=183x183), добавляя строку и столбец.

Не, ну на самом деле: "С=14, 183" понятно, "С=15, 184" тоже понятно (респект за высокие результаты), "C=15, 21" - объясните пожалуйста, что в этой записи значит цифра 21?

Цитата:

В конце концов, и решение для C=15, 21x21 (если уж вы так прочитали - дописали - мой текст) можно получить из решения для C=14, 20x20, добавляя строку и столбец. Разве нет?

Дарю C=15, 21х21 без добавления строки и столбца:

[Pavlovsky]

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

Докажите, что решения C=10, N=100x100С=12, N=144х144С=14, N=196x196C=15, N=225x225C=18, N=324x324C=20, N=400x400C=21, N=441x441существуют / не существуют. Тогда можно будет их искать в случае, если они существуют, и не искать в противном случае.

В известной всем ёжикам статье, глава 2 посвящена определению верхней оценки задачи. Главная лемма 2.7. Из которой следует. Что нельзя построить кавадрат C^2+C для C-coloring задачи. Доказательство очень красивое, рекомендую всем ёжикам разобраться.
Улучшить эту оценку будет очень трудно. В той же статье доказательство G(11,10)
is not 3-colorable (лемма 7.4) занимает несколько страниц!

С нижней оценкой все просто! Достаточно разработать алгоритм построения квадрата, заявленных размеров! Таблица рекордов текущего конкурса является нижней оценкой для C=2-21.

-- Вт июл 03, 2012 09:38:58 --

Алгоритм, с помощью которого получены последние результаты достаточно переспективен для получения новых результатов. Нет проблем с количеством колонок. Фактически получается довольно длинный прямоугольник. Приходится лишние колонки отрезать. Есть возможности и для увеличения количества строк, надо только решить технические трудности. Назвать алгоритм достраиванием наверно нельзя. За основу берется комплект ортогональных латинских квадратов для некоторого С=p^s, где p простое. В результате получается квадрат для количества цветов С+1 или С+2.
Кстати идея алгоритма пришла в результате подсказки-намека Сергея Беляева. В этом деле главное вовремя подставить голову под падающее яблоко.

Так как шкодю медленно, вбрасываю еще идею. С помощью диагональных алгоритмов построить прямоугольник 100х20 удовлетворяющий условиям теоремы 4.3 (усиленный вариант). Это же намного быстрее чем строить квадрат 100х100. Во-первых размеры меньше. Во-вторых требования жестче, значит отсечений вариантов при переборе будет больше.

[Nataly-Mak]

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

В известной всем ёжикам статье, глава 2 посвящена определению верхней оценки задачи. Главная лемма 2.7. Из которой следует. Что нельзя построить кавадрат C^2+C для C-coloring задачи.

Вы про верхнюю оценку ещё в прошлом году сказали
Я вас не о верхней оценке спрашиваю, а о существовании решений C^2xC^2 для С=10,12,14,18,20.

Цитата:

Кстати идея алгоритма пришла в результате подсказки-намека Сергея Беляева. В этом деле главное вовремя подставить голову под падающее яблоко.

Ну все подсказки-намёки вы у нас с полунамёка понимаете
И в кого только вы такой умный уродились?
Сам svb, небось, свою подсказку-намёк и не понял. Как в случае с dimkadimon получается Возвращайте теперь svb его подсказку-намёк

Цитата:

С помощью диагональных алгоритмов построить прямоугольник 100х20 удовлетворяющий условиям теоремы 4.3 (усиленный вариант). Это же намного быстрее чем строить квадрат 100х100. Во-первых размеры меньше. Во-вторых требования жестче, значит отсечений вариантов при переборе будет больше.

Zealint тут утверждал, что это не проще, а даже сложнее, чем делать перебор в квадрате 100х100. Посмотрите его сообщения по данному вопросу.
Мне тоже кажется, что с прямоугольником 100х20 работать проще, чем с квадратом 100х100. Но мало что кому кажется. Примеры давайте конкретные, результаты экспериментов.

-- Вт июл 03, 2012 09:20:05 --

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

...Требование же, быть полем, слишком сильное для нашей задачи.

Мне этот намёк очень нравится
Тут что-то есть!
Знать бы ещё, что значит "требование быть полем"

[Pavlovsky]

Может кто поможет.
http://dic.academic.ru/dic.nsf/enc_math ... 0%98%D0%99
ЛАТИНСКИЙ ПРЯМОУГОЛЬНИК

Цитата:

На Л. п. распространяются нек-рые понятия и теоремы, связанные с латинскими квадратами. Так, два Л. п. размера наз. ортогональными, если все пары вида различны. Множество Л. п. (mxn, m<=n), в к-ром любые два Л. п. ортогональны, имеет не более m-1 Л. п.

Возник такой вопрос. Как пострить множество m-1 ортоганальных латинских прямоугольников размером mxn, m<=n? В статье есть ссылка на Риордана. Скачал эту книжку, как построить нужное множество ЛП там нет.

Например элементарно построить p-1 ортогональных латинских квадратов размером pxp (p простое).
А как построить p-1 ортогональных латинских прямоугольников размером px(p+1)??

-- Вт июл 03, 2012 11:07:56 --

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

svb в сообщении #589865 писал(а):...Требование же, быть полем, слишком сильное для нашей задачи.
Мне этот намёк очень нравится Тут что-то есть!Знать бы ещё, что значит "требование быть полем"

Это Сергей об алгебру ударился. Для построения разбиений в случае С=p^s, где p простое s>1, используется хитрый алгебраический алгоритм основанный на конечных полях Галуа. Сергей писал, что разобрался в этом алгоритме. Читал этот алгоритм. Разбираться не стал. Мне хватило комплектов ЛК из ваших статей.

[Nataly-Mak]

Несколько диагональных решений для С=5, может быть, пригодятся для анализа.
Начала с самого минимального, 3х3, далее строила все подряд в программе Эда, дошла до 17х17. Дальше уже туго строятся.



Характеристическая строка:

1,2,3,4,5

Характеристическая строка:

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

Характеристическая строка:

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

Характеристическая строка:

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

Характеристическая строка:

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

Следующие квадраты не показываю, сразу 17х17:



Для сравнения интернетовское решение 17х17:



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

Может быть, примитивные эксперименты, но мне всё равно интересно.
А диагональное решение C=7, N=49x49 построил кто-нибудь?

[Nataly-Mak]

Для С=6 аналогичные эксперименты, легко дошла до решения 21х21:



Красивые решения получаются.
Не удивительно, что svb легко нашёл по программе решение 36х36.

[Nataly-Mak]

Диагональный прямоугольник 50х20 10-coloring, в нескольких местах диагональность нарушается - диагональ меняет цвет.



Прямоугольник построился очень легко в программе Эда. Можно продолжить построение до 100 строк.

Очень интересен вопрос: много ли в этом прямоугольнике несоответствий требованиям усиленного варианта леммы 4.3
И второй вопрос: можно ли его привести в соответствие с этими требованиями

[Alexu007]

С14 100х100 неактуально?

[Nataly-Mak]

Это для кого как

[Alexu007]

У меня программа перебора такой составила, целых пол-часа думала. На экране он ессно целиком не помещается. Куда его теперь - в топку?

[svb]

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

Мне этот намёк очень нравится
Тут что-то есть!
Знать бы ещё, что значит "требование быть полем"

Дык... в первом классе проходили таблицу умножения - помните, в наше время на обложке тонких тетрадей печатали эту таблицу. Можно рассматривать эти таблицы по модулю - получим кольца с двумя операциями + и x, но в них могут появиться делители 0, но не всегда. Применительно к нашим квадратам, вписываем в маленький квадрат таблицу умножения, а далее используем таблицу сложения

[Nataly-Mak]

Alexu007 в сообщении #591585 писал(а):

У меня программа перебора такой составила, целых пол-часа думала. На экране он ессно целиком не помещается. Куда его теперь - в топку?

Зачем в топку? Отправьте на конкурс

-- Вт июл 03, 2012 16:19:15 --

Достроила прямоугольник 100х20 10-coloring:



Такой красавец! Как бы его... преобразовать, чтобы он удовлетворял требованиям нашей леммы

Сейчас прямо из этого (неправильного) попробую квадрат 100х100 построить.
Интересно: много в этот раз ошибок будет.

-- Вт июл 03, 2012 16:24:20 --

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

Дык... в первом классе проходили таблицу умножения - помните, в наше время на обложке тонких тетрадей печатали эту таблицу.

Таблицу умножения вроде помню

Я в одной статье описывала построение группы из 5 попарно ортогональных ЛК 12-го порядка из какой-то книги. По-моему, там это самое применяется, тоже какая-то таблица умножения. Мне тогда на форуме объяснили, как этой таблицей надо пользоваться.

А, нет, там абелева группа, а не поля Галуа.
Вот в этой статье:
http://www.natalimak1.narod.ru/mols12.htm

[Pavlovsky]

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

рассматривать эти таблицы по модулю

Поле Галуа какое то хитрое, не совсем сложение по модулю. Там a+a=0 для любого a.

[Alexu007]

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

Alexu007 в сообщении #591585 писал(а):

У меня программа перебора такой составила, целых пол-часа думала. На экране он ессно целиком не помещается. Куда его теперь - в топку?

Зачем в топку? Отправьте на конкурс

Так там для С=15 200х200 котируются, кому нужен мой скромный 100х100? Или с таким результатом тоже есть смысл? И где я буду - на последнем месте? Да ещё и региться для этого надо!

Далее, чтобы отправить на конкурс, нужно квадрат в файл скинуть, как я понимаю - чтобы "программа Эда" его приняла. Какие требования к этому файлу? Текстовый? Разделители между цифрами? Разделители между строками?

Отправляю в топку, потому что скидывать в файл моя прога не умеет - я её этому ещё не учил. Квадрат существует в виде массива в памяти и картинки на экране - всё, закрываю прогу - аминь... впрочем я могу ещё за полчаса сваять похожий.

Цитата:

Такой красавец! Как бы его... преобразовать, чтобы он удовлетворял требованиям нашей леммы

Так легко же. Уберите пересечения...

[Nataly-Mak]

Квадраты на конкурс отправлять очень просто. Числа разделяются запятыми, вот и все премудрости.

Цитата:

Такой красавец! Как бы его... преобразовать, чтобы он удовлетворял требованиям нашей леммы

Цитата:

Так легко же. Уберите пересечения...

Так нету у меня программы Писать её ещё надо.
К тому же Zealint писал, что не преобразовываются эти прямоугольники. А почему бы им не преобразовываться?