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

[Nataly-Mak]

И наконец последнее весьма оригинальное решение.

Это совсем оригинальный алгоритм, он основан на МБ-лемме.
Кто внимательно читал тему, помнит, что именно по этому алгоритму я построила решения 2-го класса.

Берём стандартную 7-сильную раскраску 49х8. Выполняем одну репликацию, но!.. возникший при репликации цвет 8 не заменяем на 1.
В результате такой операции мы получаем раскраску 49х16 (8,2)-strong по МБ-лемме!

Вот она - эта очень симпатичная раскрасочка:



Ну, а теперь, понятно, применяем МБ-лемму, всего 3 репликации и... раскраска 49х64 8-coloring готова. Приписываем к ней 9 строк и получаем решение 58х64 8-coloring:



Так я получила своё первое решение во 2-ом классе - C10N92. И для всех следующих С аналогично.

[Nataly-Mak]

Опубликую таблицу рекордов, полученных на конкурсе, вряд ли уже что-то изменится до конца конкурса:

Цитата:

2 4 16 Wes Sampson @ 05:33:15 on 05-30-2012 81
3 10 100 Mark Mammel @ 06:40:27 on 05-30-2012 55
4 18 324 Juha Saukkola @ 09:15:48 on 05-30-2012 45
5 25 625 Jarek Wroblewski @ 09:04:36 on 05-30-2012 41
6 36 1296 Alex Chernov @ 23:02:26 on 05-31-2012 23
7 49 2401 Jarek Wroblewski @ 09:05:38 on 05-30-2012 38
8 64 4096 Il brigante Pennastorta @ 14:08:50 on 05-31-2012 28
9 81 6561 Il brigante Pennastorta @ 17:12:43 on 05-31-2012 28
10 94 8836 Artem Karavaev @ 19:50:31 on 07-09-2012 4
11 121 14641 Jarek Wroblewski @ 09:06:25 on 05-30-2012 37
12 136 18496 Artem Karavaev @ 19:18:29 on 06-30-2012 2
13 169 28561 Jarek Wroblewski @ 09:07:27 on 05-30-2012 37
14 186 34596 Artem Karavaev @ 06:56:57 on 07-10-2012 2
15 197 38809 Alex Chernov @ 13:23:07 on 08-08-2012 1
16 256 65536 Dmitry Kamenetsky @ 07:49:18 on 06-01-2012 27
17 289 83521 Jarek Wroblewski @ 09:13:49 on 05-30-2012 37
18 310 96100 Artem Karavaev @ 17:37:19 on 07-11-2012 2
19 361 130321 Jarek Wroblewski @ 09:19:13 on 05-30-2012 37
20 384 147456 Artem Karavaev @ 08:19:18 on 07-10-2012 2
21 400 160000 Alex Chernov @ 22:10:03 on 08-11-2012 1

Забавно, 81 из 88 участников нашли решение C2N4

По-прежнему неповторенными остаются рекорды Алексея Чернова для С=15,21.
svb загадочно намекал, что должно получиться решение C21N401 в рамках какого-то достраивания, но я так и не поняла, где же оно

[Pavlovsky]

Рановато, я заявил о звершении участия в конкурсе. Появляются еще идеи!

Вспомогательная задача.
Дано: натуральные числа k,N.
Необходимо заполнить единичками прямоугольник MxN. M – количество строк, N – количество колонок. Такой что:
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно k единичек.
3) Количество строк M - минимально возможное.

В стиле доказательства Sirgedas можно оценить границу снизу для M

k\N   6   10   12   14   15   18   20   21
2     4    5    6    6    6    7    7    7
3     7    9    9   10   10   11   12   12
4     9   12   13   14   12   16      
5    12   15   16   18   18

Пример для k=3, N=6

1 1 1 0 0 0
1 0 0 1 1 0
1 0 0 0 0 1
0 1 0 1 0 1
0 1 0 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0

[dimkadimon]

Я наконец разгадал метод Herbert с cyclic difference set (CDS). CDS(v,k,lambda) это k цифр от 0 до v-1, где каждая разница (mod v) между любой пары цифр встречается ровно lambda раз. Для нашей задачи нам интересны имено lambda=1. Причём CDS(v,k,1) существуют для всех k=p^n+1 и v=p^2+p+1, где p простое число. CDS(v,k,1) дает нам решение где C=k и N=v. Вот они тут: http://www.ccrwest.org/diffsets/diff_sets/baumert.html
Значит мы можем построить вот эти решения: C3N7, C4N13, C5N21, C6N31, C8N57, C9N73, C10N91, C12N133, C14N183, C17N273, C18N307 и C20N381. Эти решения имеют диагональную форму и поетому очень красивые.

Возьмём CDS(7,3,1) = (0,1,3). Это можно представить как замкнутую цепочку из 7 бусинок где бусинки на позициях 0, 1 и 3 чёрные, а остальные белые. Растояния между любой две чёрные бусинки все разные. Вот как выглядит таблица разниц (mod 7):

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

Заметьте что все разницы от 1 до 6 встречаются ровно 1 раз. Если передвинуть бусинки на одну позицию то опять получится правильная цепочка. Значит CDS(7,3,1) можно записать вот ещё так:

0,1,3  а
1,2,4
2,3,5
3,4,6
4,5,0  b
5,6,1
6,0,2  c

Это всё очень хорошо описано тут: http://www.inference.phy.cam.ac.uk/cds/part1.htm

Итак чтобы составить наше решение красим первым цветом (а) диагонали 0, 1 и 3, начиная сверху:

0123456
аа0а000
0аа0а00
00аа0а0
000аа0а
0000аа0
00000аа
000000а

Пустые клетки я обозначил нулём. Если сделаем 7 - (0,1,3) то получим (7,6,4). Теперь можно закрасить нижние диагонали 4 и 6 начиная слева:

  0123456
0аа0а000
10аа0а00
200аа0а0
3000аа0а
4а000аа0
50а000аа
6а0а000а

Остальные два цвета можно закрасить таким же образом. Для второго цвета b выбираем (4,5,0), а для третьего цвета c берём (6,0,2). Вот наконец получаем полное решение:

  0123456
0ааcabbc
1cааcаbb
2bcааcаb
3bbcааcа
4аbbcааc
5cаbbcаа
6аcаbbcа

Этот метод можно проделать и для других C. Красота!

К сожалению это совсем не даёт нам никаких улучшений. "Увеличивать" эти решения совсем не получается, например я даже не смог получить C10N92 из C10N91. Зато обнаружил что можно немного уменьшить требования CDS - можно искать цепочки где каждая разница встречается 0 или 1 раз. То есть какие то разницы вообще не встречаются. В этом случае, правда, для других цветов надо находить отдельные цепочки (которые отличны) от первой. Таким образом я теперь очень быстро могу находить диагональные решения C5N25 и C6N36, а вот для C>=10 никакого прогресса.

Идеи к сожалению кончаются, а их было очень много... написал столько разных методов и программ что уже сам точно не помню где что. В итоге написал 17 тысяч строк кода в Java - это далеко мой самый большой проект!

[svb]

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

А вот здесь вы разве не о супералгоритме писали?
Читая это, я поняла так, что у вас есть как минимум решение C21N401 и ещё куча рекордов

Писал я не об алгоритме, а о "базовой конфигурации". Основной целью было оживление темы, как говорит Павловский "интриганство"

А вот алгоритм? Может он и существует, а может и нет - не знаю. Вручную я пробовал заполнять дырки для C=5, получилось, но потом оказалось, что это слишком маленький опыт. Но предел у этого подхода C21401 - в сочетании с результатами alexBlack появилась возможность "интриговать" . В свое оправдание могу сказать, что обманом я никогда не занимался - можете проверить.

Вот сейчас появилось сообщение dimkadimon с исключительно богатой и интересной идеей. Сколько я с этими "разностями" возился, но жар-птица все-время улетала. Уложить все "разности" в одну строку - это блеск!

[Nataly-Mak]

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

Писал я не об алгоритме, а о "базовой конфигурации".

Вы писали о некотором способе построения решений. Это не алгоритмом разве называют?

Цитата:

Основной целью было оживление темы, как говорит Павловский "интриганство"

По-моему, мы находимся не на тусовке бомонда, чтобы плести интриги. Мне это непонятно.
"Трёп", "интриги"... Здесь вроде как научный форум. Я все сообщения воспринимаю серьёзно и начинаю обдумывать. Оказывается, тут интриги какие-то

-- Пт авг 24, 2012 16:14:51 --

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

Вот сейчас появилось сообщение dimkadimon с исключительно богатой и интересной идеей.

Да, dimkadimon, в отличие от вас, не интригует, а пишет совершенно конкретные вещи.
Я эту идею Герберта давным-давно отметила, но не разобралась в ней до конца. Даже свою попытку приводила (картинку).
dimkadimon сумел разобраться, молодец!

[dimkadimon]

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

Я эту идею Герберта давным-давно отметила, но не разобралась в ней до конца. Даже свою попытку приводила (картинку).
dimkadimon сумел разобраться, молодец!

Спасибо. Кстати я догадался только благодаря вашей попытки. Все таки вместе мы гораздо сильнее.

-- 24.08.2012, 21:07 --

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

Рановато, я заявил о звершении участия в конкурсе. Появляются еще идеи!

Вспомогательная задача.
Дано: натуральные числа k,N.
Необходимо заполнить единичками прямоугольник MxN. M – количество строк, N – количество колонок. Такой что:
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно k единичек.
3) Количество строк M - минимально возможное.

Пока не вижу связь етой задачи с главной задачей, но готов поискать решения к ней. Какие k и N вас интересуют?

[Pavlovsky]

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

Пока не вижу связь этой задачи с главной задачей

Появилась идея. В случае удачи можно строить решения 4 и даже 5 класса! Первая попытка реализовать идею закончилась неудачей. Так как уже нет сил заниматься конкурсной задачей, готов опубликовать идею. Если никто не возражает.

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

готов поискать решения к ней. Какие k и N вас интересуют

Например N=10 k=3. В соответсвии с нижней оценкой M=9. То есть надо построить прямоугольник 9х10 (9 - строки 10 - колонки).
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно 3 единичек.

[svb]

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

Вы писали о некотором способе построения решений. Это не алгоритмом разве называют?

Я разве писал, что знаю как получить C21N401? Прошу вас не сочинять и не приписывать мне того, что я не говорил

Цитата:

По-моему, мы находимся не на тусовке бомонда, чтобы плести интриги. Мне это непонятно.
"Трёп", "интриги"... Здесь вроде как научный форум. Я все сообщения воспринимаю серьёзно и начинаю обдумывать. Оказывается, тут интриги какие-то

Слово "интриги" не я употребил, поэтому и ставлю это слово в кавычки.

Цитата:

Да, dimkadimon, в отличие от вас, не интригует, а пишет совершенно конкретные вещи.

Вот это уже переходит за рамки приличий, поэтому я, пожалуй, покину этот форум. Прощайте!

[Nataly-Mak]

dimkadimon
ещё раз спасибо вам за подробное описание идеи Герберта.
Вроде разобралась. Построила сначала 7х7 3-coloring точно по вашему описанию, чтобы лучше понять.
Затем повторила свою неудавшуюся давно попытку, это решение C6N31.
Теперь получилось:



Действительно, красивые решения получаются.
Вы писали, что можно по этому алгоритму получить решения C8N57, C10N91. Здорово.
Для С=10 решение 1-го класса диагональное!
Кстати, решение для С6N31, показанное мной, тоже 1-го класса. И C8N57 тоже 1-го класса.
То есть по этому алгоритму все решения 1-го класса получаются. Так?

Кстати, тут давно пытались искать диагональные решения для С=10. Какое максимальное удалось найти? Может быть, 91х91 и есть максимальное?
Построить бы его... но вручную долго, трудновато. Программку бы составить.

Не поняла один момент: что означает n в таблице CDS?
Например, я использовала CDS (31,6,1)

1, 5, 11, 24, 25, 27

здесь n=5. Что это такое? Где используется?

Вообще идея супер, конечно. Спасибо Герберту!

-- Сб авг 25, 2012 11:14:49 --

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

Появилась идея. В случае удачи можно строить решения 4 и даже 5 класса! Первая попытка реализовать идею закончилась неудачей. Так как уже нет сил заниматься конкурсной задачей, готов опубликовать идею. Если никто не возражает.

Вы тоже интригуете?

Что же это так сильно устали. Я тоже притомилась, но всё ещё занимаюсь задачей.
Правда, ничего не получается, но... я не виновата, стараюсь
Насчёт опубликования идеи не возражаю.

Цитата:

Например N=10 k=3. В соответсвии с нижней оценкой M=9. То есть надо построить прямоугольник 9х10 (9 - строки 10 - колонки).
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно 3 единичек.

Ну, вот, например, с ходу такой прямоугольник, он не совсем удовлетворяет вашим условиям, но близко; в одной колонке 4 единички, а в трёх колонках по 2 единички, в остальных - по 3 единички:

1 x x x x x x 1 x x
x x x x x 1 x x 1 1
x x x 1 1 x 1 x 1 x
x x 1 x x 1 1 1 x x
x 1 1 x x x x x 1 x
x 1 x 1 x x x 1 x x
x x 1 1 x x x x x 1
1 x 1 x 1 x x x x x
1 1 x x x x 1 x x x

Если будет построен такой прямоугольник в точном соответствии с вашими условиями, дальше что с ним надо делать?

-- Сб авг 25, 2012 11:50:52 --

Цитата:

My clues never really reveal anything. But, as has already been mentioned, it WILL involve prime numbers. :)

Это пишет администратор конкурса на их форуме.
Как я понимаю, следующий конкурс будет как-то связан с простыми числами.

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

[dimkadimon]

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

Например N=10 k=3. В соответсвии с нижней оценкой M=9. То есть надо построить прямоугольник 9х10 (9 - строки 10 - колонки).
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно 3 единичек.

Вот решение для N=10, k=3 и М=9:

0,1,0,0,0,0,1,0,1,0,
1,0,0,0,0,1,1,0,0,0,
0,0,1,0,0,0,1,1,0,1,
1,0,0,1,0,0,0,0,1,1,
0,1,1,1,0,1,0,0,0,0,
0,1,0,0,1,0,0,0,0,1,
0,0,0,0,1,1,0,1,1,0,
0,0,0,1,0,0,0,1,0,0,
1,0,1,0,1,0,0,0,0,0

А что дальше? Неужели из етого можно получить C3N10? Кстати для М=9 решений не было.

-- 25.08.2012, 17:10 --

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

То есть по этому алгоритму все решения 1-го класса получаются. Так?

Кстати, тут давно пытались искать диагональные решения для С=10. Какое максимальное удалось найти? Может быть, 91х91 и есть максимальное?
Построить бы его... но вручную долго, трудновато. Программку бы составить.

Не поняла один момент: что означает n в таблице CDS?
Например, я использовала CDS (31,6,1)

1, 5, 11, 24, 25, 27

здесь n=5. Что это такое? Где используется?

По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1, точно не знаю какой ето класс. Немного изменив метод можно получить и лучше, например C5N25 и C6N36. Возможно 91х91 максимальное, но я еше не пробовал 92х92. 91х91 (и другие) я выложу в конце соревнования. Я не знаю что такое n.

[Nataly-Mak]

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

По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1...

По-моему, это не совсем правильная формула. У вас во второй формуле не участвует k.
Что за N у вас получится, например, при p=3, k=2 (С=10)?

[Pavlovsky]

Идея была такая. Берем сильноокрашенный прямоугольник 81х10 заполненный 9-ю цветами. Удаляем из него 6 строк. Добавляем 9 строк

0,1,0,0,0,0,1,0,1,0,
1,0,0,0,0,1,1,0,0,0,
0,0,1,0,0,0,1,1,0,1,
1,0,0,1,0,0,0,0,1,1,
0,1,1,1,0,1,0,0,0,0,
0,1,0,0,1,0,0,0,0,1,
0,0,0,0,1,1,0,1,1,0,
0,0,0,1,0,0,0,1,0,0,
1,0,1,0,1,0,0,0,0,0

Вместо 1 вставляем 10. Пытаемся заполнить ячейки с нулями. Если это удастся, то получим сильноокрашенный прямоугольник 84х10 для С=10. Из которого получаем решение C10N94.

Увы первые эксперименты дали отрицательный результат. Конечно над идеей можно еще работать, но это уже в следующем конкурсе.

-- Сб авг 25, 2012 15:24:37 --

Идея оказалась слишком заумной. Простой вариант идеи такой.
Берем сильноокрашенный прямоугольник 81х10 заполненный 9-ю цветами. Удаляем из него некоторое количество строк. К полученному прямоугольнику пытаемся добавлять строки с использованием 10-ти цветов.

[Nataly-Mak]

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

Если это удастся, то получим сильноокрашенный прямоугольник 84х10 для С=10. Из которого получаем решение C10N94.

Увы первые эксперименты дали отрицательный результат.

А вы к опыту коллег прислушиваетесь?
Я высказала гипотезу, что 10-сильная раскраска 84х10 не существует.

Гипотезу пока никто не опроверг, хотя... и не доказал

Ваш отрицательный результат только подтверждает гипотезу.

[dimkadimon]

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

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

По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1...

По-моему, это не совсем правильная формула. У вас во второй формуле не участвует k.
Что за N у вас получится, например, при p=3, k=2 (С=10)?

С это простое число в степени плюс один. p простое число, а k любая степень. Простите я формулу совсем напутал, должно быть N=C^2-С+1.