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

[dimkadimon]

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

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

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

Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные) пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14. Применяя методику дважды получаем 15 сильноокрашенный прямоугольник (169+2К)х14.

Ух ты - я совсем по другому делал. Из 13-strong 169х14 получил 14-coloring 169х182, а из этого получил 14-coloring 183х183. Ваш метод мне больше нравится.

[Nataly-Mak]

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

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

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

Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14.

Вот именно! 13-сильную раскраску 169х14 имеют все. А вот от неё уже все по-разному пляшут

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

во 2-ом классах.

Цитата:

Дык это , пусть на одну строку, уже лучше F(15)=F(14)+1.

Не поняла.
Ещё раз:
первый класс: C14N183, C15N184
второй класс: C14N184, C15N185

Это у меня. А у вас как?

В третьем классе у меня нерегулярное C14N185, от него C15N186.

-- Вт июл 24, 2012 13:04:32 --

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

Ух ты - я совсем по другому делал. Из 13-strong 169х14 получил 14-coloring 169х182, а из этого получил 14-coloring 183х183. Ваш метод мне больше нравится.

А я по-третьему делала
Вот и получается, что у всех свой алгоритм.

У меня из 13-strong 169х14 получается 169х196 14-coloring.
И соответственно: из любого прямоугольника C^2x(C+1) strong С-coloring (C=p^k, p - простое, k>=1) получается прямоугольник
C^2x(C+1)^2 (C+1)-coloring.

[Pavlovsky]

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

первый класс: C14N183, C15N184
второй класс: C14N184, C15N185

второй класс: C14N184, C15N186
третий класс: C14N185, C15N188

[Nataly-Mak]

Ага, теперь поняла.
Значит, во втором классе мой результат для С=15 можно чуть улучшить.

Но, как уже выясняется, алгоритмы у нас с вами разные, поэтому ещё неизвестно, можно ли мой алгоритм применить дважды.

[svb]

Nataly-Mak

Цитата:

Он вот, кстати, до сих пор не вступает в игру
Как вы думаете, почему?

Смотрю и думаю, думаю и смотрю Иногда отвлекаюсь на facebook и др., когда наступает полный тупик.

Pavlovsky

Цитата:

Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные) пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14. Применяя методику дважды получаем 15 сильноокрашенный прямоугольник (169+2К)х14.

Вот до сильной окрашенности так и не добрался , пока ни разу не воспользовался.

Имеются совершенно тривиальные идеи, которые, наверняка, обдумывали большинство участников. Переход от $C$ к $C+1$ требует достройки $2C+1$ строк. Первое $C$ получается достаточно быстро и самыми различными способами - так или иначе требуется некоторое перекрашивание основного квадрата, явно неполноценное, но где же взять полноценное . Рассматривание базовых квадратов дает картинку из $C^2$ маленьких квадратиков $C \times C$, которые путем перестановки строк легко превращаются в маленькие квадратики $(C-1)\times (C-1)$ - это, вроде, дает шанс на реализацию подхода с достраиванием, но шанс ли это?

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

Любопытны пары решений, которые внешне совершенно различные, но фактически основаны на одном методе. Эти "сопряженные" решения представляют интерес, но мало что дают ... пока?

[Nataly-Mak]

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

Цитата:

Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные) пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14. Применяя методику дважды получаем 15 сильноокрашенный прямоугольник (169+2К)х14.

Цитата:

Вот до сильной окрашенности так и не добрался , пока ни разу не воспользовался.

Это ещё раз подтверждает, что алгоритмы у всех разные.
Я тоже не строила прямоугольник (169+К)х14 strong 14-coloring в первом и втором классах.

Только в третьем классе начала использовать С-сильные раскраски.
Сначала это у меня получилось с 83х10 10-сильной раскраской, потом перешла к 123х12 12-сильной... Но это уже совсем другая опера

[Nataly-Mak]

Хорошо мы тут расписали, как находить решения в классах

dimkadimon стал третьим конкурсантом, нашедшим решение C10N94.

Pavlovsky
а вы чего отстаёте в четвёртом классе?

У меня тоже 10-сильная раскраска 84х10 никак не получается
5 ошибок никак не убиваются.

-- Вт июл 24, 2012 19:39:20 --

Положение в группе лидеров мне уже не нравится

Цитата:

1 Artem Karavaev 19.974300 07-11-2012 @ 17:37:19
2 Nick Gardner 19.947100 07-24-2012 @ 16:06:24
3 Alex Chernov 19.941800 07-07-2012 @ 20:56:57
4 Herbert Kociemba 19.926300 07-07-2012 @ 14:29:57

Nick Gardner очень активно продвигается вперёд.
Herbert Kociemba тоже сильный противник.

Наши ребята заметно снизили активность, примерно две недели нет новых результатов.
Кончились идеи?

[Nataly-Mak]

Любопытный сопутствующий результат - 6 попарно ортогональных обобщённых латинских квадратов 6-го порядка; правда, в них не хватает по 5 чисел:

(Оффтоп)

1 1 1 1 1 1
2 2 2 2 2 x
3 3 3 3 3 x
4 4 4 4 4 x
5 5 5 5 5 x
6 6 6 6 6 x

2 3 4 5 6 1
1 3 4 5 6 x
1 2 4 5 6 x
1 2 3 5 6 x
1 2 3 4 6 x
1 2 3 4 5 x

3 1 2 4 5 6
1 2 3 5 6 x
2 4 5 6 1 x
5 6 3 2 4 x
3 1 4 6 2 x
4 5 6 1 3 x

4 1 2 3 5 6
2 3 5 6 4 x
5 6 4 1 3 x
3 2 6 4 1 x
1 5 2 3 6 x
4 1 5 6 2 x

5 1 2 3 4 6
3 4 6 5 1 x
5 1 3 2 6 x
1 4 2 6 5 x
4 2 6 5 3 x
2 6 3 4 1 x

6 1 2 3 4 5
4 5 1 2 3 x
3 4 5 6 2 x
6 1 3 4 5 x
2 5 6 4 1 x
1 3 2 6 5 x

Получить 6 таких полных ЛК (без пробелов) невозможно.

Я очень мало в своё время занималась обобщёнными ЛК; статья есть им посвящённая, но в ней очень мало информации, несколько примеров, найденных в чужих статьях, ничего оригинального.
Может быть, после конкурса вернусь к этой статье.

Кстати, приведённый результат перекликается со строкой Pavlovsky для С=6.
Из его строки я получила аналогичный набор попарно ортогональных обобщённых ЛК.

[Pavlovsky]

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

Может быть, после конкурса вернусь к этой статье.

Надо еще латинскими прямоугольниками заняться!

-- Ср июл 25, 2012 08:30:11 --

svb

Появился ваш единомышленник по конечным полям.
http://infinitesearchspace.dyndns.org/c ... ic-squares
Algebraic approach to monochromatic squares

[Nataly-Mak]

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

Появился ваш единомышленник по конечным полям.

Ага, у этого единомышленника пока те же самые вопросы без ответов :

Цитата:

• Есть ли подобный подход в других случаях (C = 6,10, ...)?
• Есть еще один алгебраической структуры, связанные с этой проблемой? Я пытался использовать некоторые группы действий для построения сетей, но я не могу разобраться.

[Nataly-Mak]

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

Надо еще латинскими прямоугольниками заняться!

А представленные мной неполные ЛК 6-го порядка и есть в сущности попарно ортогональные прямоугольники. Отбросьте в моих квадратах последний столбец и получите прямоугольники 6х5.

Получен также весьма интересный набор из 6 попарно ортогональных прямоугольников 5х6.
Это тоже неполные ЛК 6-го порядка, в которых не заполнена последняя строка.
Интересно, что два из этих ЛК обобщённые, а 4 остальных классические.

Наконец, получен набор из 10 попарно ортогональных прямоугольников 5х10.
Любопытные прямоугольнички
Они проедставляют ровно половинки ЛК 10-го порядка. При этом два первых ЛК обобщённые, остальные 8 классические.

[Pavlovsky]

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

При этом два первых ЛК обобщённые, остальные 8 классические.

Если взять два обобщенных ЛК вида
11111
22222
......
и
123..
123..
....

То все остальные ортогональные ЛК обязаны быть классическими ЛК.

[Nataly-Mak]

Ага, так утверждает Холл в своей книге "Комбинаторика"

Кстати, весьма полезная книга. Я её просматривала на английском языке. А недавно узнала, что книга ещё в 1970 г. переведена на русский язык.
Вот ссылка на русское издание книги:
http://flyonmap.com/b/3d1p1m1m_2u._2s1p ... _1970.djvu

[svb]

Nataly-Mak

Цитата:

Ага, у этого единомышленника пока те же самые вопросы без ответов :

Одно из обобщений дало решения для $C=6$, но споткнулось об $C=10$ и это было странно.

Цитата:

Кстати, весьма полезная книга.

Павловский от нее отказался, когда я предложил список.

[Pavlovsky]

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

Павловский от нее отказался, когда я предложил список.

Кто не знает книгу Холла "Комбинаторика"?! Естественно она у меня есть.