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

[Nataly-Mak]

Вот вторая базовая матрица для той же свёртки блоков, приведена whitefox:

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

-- Сб сен 08, 2012 08:30:30 --

А теперь будем строить блоки 6x6 по-другому.
Предлагаю такую свёртку блоков R+:

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

Существует ли для такой свёртки базовая матрица?
Я попробовала заполнить блоками, построенными по данной свёртке, базовую матрицу whitefox. Не получилась правильная раскраска.

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

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

Задача (простенький перебор )

найти для приведённой выше свёртки блоков R+ базовую матрицу Rx.

Не уверена, что задача имеет решение.

[Nataly-Mak]

Не эту ли задачу решал здесь Pavlovsky?

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

С=10
Циклический ЛК 10х10.
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 3 4 5 6 7 8 9 0 1
3 4 5 6 7 8 9 0 1 2
4 5 6 7 8 9 0 1 2 3
5 6 7 8 9 0 1 2 3 4
6 7 8 9 0 1 2 3 4 5
7 8 9 0 1 2 3 4 5 6
8 9 0 1 2 3 4 5 6 7
9 0 1 2 3 4 5 6 7 8

Матрица перестановок
2 3 4 5 6 7 8
3 5 9 8 2 4 6
4 9 8 6 5 10 3
5 8 6 2 10 3 7
6 2 5 10 3 9 4
7 4 10 3 9 6 2
8 6 3 7 4 2 9


ЛК 10х10. Таблица сложения.
0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 6 7 8 9 5
2 3 4 0 1 7 8 9 5 6
3 4 0 1 2 8 9 5 6 7
4 0 1 2 3 9 5 6 7 8
5 6 7 8 9 0 1 2 3 4
6 7 8 9 5 1 2 3 4 0
7 8 9 5 6 2 3 4 0 1
8 9 5 6 7 3 4 0 1 2
9 5 6 7 8 4 0 1 2 3

2 3 4 6 7 8 9
3 8 10 4 6 5 7
4 10 8 7 3 6 2
6 4 9 2 5 10 8
7 9 5 10 4 2 6
8 6 3 5 10 9 4
10 2 6 9 8 4 3


По этим матрицам можно получить решение C10N90. Интересно можно ли его нарастить до приличных значений?! Например до C10N94??

Представлены пары матриц R+, Rx для С=10.
Выше описаны эксперименты для С=6.

-- Сб сен 08, 2012 09:53:22 --

Интересен и пример dimkadimon для С=5.

Вот его решение:



dimkadimon
только вы перепутали местами матрицы, у вас базовой будет матрица:

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

Вторая матрица - свёртка блоков - у вас задаётся исходным квадратом 5х5 (первый блок), который не является никаким латинским квадратом, и правилом получения следующих блоков.

[Nataly-Mak]

dimkadimon
это все ваши пять блоков:

(Оффтоп)

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

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

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

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

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

А вот свёртка блоков в вашем примере совсем не составляется, как раз потому, что у вас блоки не являются никакими латинскими квадратами.

[whitefox]

В развитие моего предложения по базовым матрицам перестановок.

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

То есть в каждой клетке базовой матрицы будет стоять перестановка $i\cdot j$, где $i$ - перестановка общая для всех клеток одной строки, а $j$ - перестановка общая для всех клеток одного столбца.

Условие корректности базовой матрицы будет следующим:
для всех $i_1,i_2,j_1,j_2$ перестановка $m=(i_1j_1)(j_2^{-1}i_1^{-1})(i_2j_2)(j_1^{-1}i_2^{-1})$ есть беспорядок.

Очевидна следующая лемма.
Лемма 1: Для любых перестановок $i,m$ перестановка $m$ будет беспорядком тогда и только тогда, когда беспорядком будет перестановка $imi^{-1}$.

Используя лемму 1 приведём условие корректности базовой матрицы к следующему виду:
для всех $i_1,i_2,j_1,j_2$ перестановка $(j_1j_2^{-1})(i_1^{-1}i_2)(j_2j_1^{-1})(i_2^{-1}i_1)$ есть беспорядок.

Будем называть две перестановки не пересекающимися если в одинаковых позициях у них стоят разные числа.
Например, перестановки 2 3 1 5 6 4 и 3 2 1 5 4 6 пересекаются так как в четвёртой позиции у них стоит одно и тоже число -- 5, а перестановки 1 2 3 4 5 6 и 2 3 4 5 6 1 не пересекаются.

Очевидна следующая лемма.
Лемма 2: Для любых перестановок $a,b$ перестановка $ab^{-1}$ будет беспорядком тогда и только тогда, когда перестановки $a,b$ не пересекаются.

Используя лемму 2 преобразуем условие корректности базовой матрицы к виду:
для всех $i_1,i_2,j_1,j_2$ перестановки $(j_1j_2^{-1})(i_1^{-1}i_2)$ и $(i_1^{-1}i_2)(j_1j_2^{-1})$ не пересекаются.

На время забудем о базовых матрицах и будем искать два множества перестановок для которых выполнено следующее условие:
для любых двух различных перестановок $i_1,i_2$ из первого множества и любых двух различных перестановок $j_1,j_2$ из второго множества перестановки $(j_1j_2^{-1})(i_1^{-1}i_2)$ и $(i_1^{-1}i_2)(j_1j_2^{-1})$ не пересекаются.

В частности, если для двух множеств перестановок, каждое по девять перестановок десятого порядка, будет выполнено приведённое выше условие, то решение C10N100 существует и легко строится по этим множествам.

[Nataly-Mak]

whitefox
пока не вникала (пойти пожевать надо, а то умру с голоду за компьютером ), но чувствую, что вы в полёте за жар-птицей

[whitefox]

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

чувствую, что вы в полёте за жар-птицей

Жар-птица сиречь мираж?

Возможно.

Не решёнными остаются два вопроса:
1. Каким условиям должны удовлетворять перестановки A и B, чтобы перестановки AB и BA не пересекались?
2. Если первый вопрос решён, то каким условиям должны удовлетворять перестановки $i_1,i_2$, чтобы перестановка $i_1^{-1}i_2$ удовлетворяла условиям из первого пункта?

Решив эти вопросы, можно, либо построить C10N100, либо доказать, что таким методом построить C10N100 невозможно (из чего, впрочем, не будет следовать не существование C10N100).

[Nataly-Mak]

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

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

чувствую, что вы в полёте за жар-птицей

Жар-птица сиречь мираж?

Не совсем так.

Мираж - обманчивый призрак; нечто, созданное воображением, кажущееся.

Жар-птица - волшебная птица русских народных сказок с сверкающими (горящими как жар) перьями.

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

А. Фет. Фантазия

Когда я говорю о жар-птице, имею в виду очень красивое, волшебное решение, которое очень трудно найти.

alexBlack в своей статье пишет, что для С=10 удалось сделать полный перебор. Максимальная найденная матрица 8х8, что даёт решение 90х90.

Но тут сразу же возникает вопрос: при каких условиях он сделал полный перебор?
Имеется ли в виду полный перебор только для блоков, строящихся циклическим сдвигом, то есть как раз тех, которые у него показаны в самом начале статьи для С=5?

Если только для таких блоков, то это, разумеется, очень мало, чтобы сделать однозначный вывод о несуществовании решения C10N100.

Я чуть выше показала цитату из сообщения Pavlovsky. Мы видим у него две пары матриц R+, Rx для С=10.
Эти модификации матриц можно продолжить.
Pavlovsky подчёркивает, что очень многое зависит от исходного ЛК.

Ну, и ваше расширение метода тоже, конечно же, надо проработать.
К сожалению, пока мне это всё сложно для понимания.
Может быть, выскажутся коллеги, как они смотрят на ваше расширение.

[whitefox]

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

Каким условиям должны удовлетворять перестановки A и B, чтобы перестановки AB и BA не пересекались?

Вот ответ.

Наложим перестановки $\mathrm{A}$ и $\mathrm{B}$ друг на друга (порядок перестановок важен). Получим множество упорядоченных пар.

Тоже самое проделаем с перестановками $\mathrm{B^{-1}}$ и $\mathrm{A^{-1}}$ (порядок по-прежнему важен). Получим второе множество упорядоченных пар.

Перестановки $\mathrm{AB}$ и $\mathrm{BA}$ не пересекаются тогда и только тогда, когда полученные множества упорядоченных пар не пересекаются.

Не знаю, чем этот ответ лучше вопроса.

[Nataly-Mak]

Удивительные вещи открываются!
Может быть, я открыла Америку?

На это меня натолкнул пример dimkadimon.
Оказывается, матрицы R+ и Rx можно менять местами.
Покажу на примере из статьи alexBlack для С=5.

У него базовая матрица Rx такая:

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

а это свёртка блоков R+:

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

Теперь поменяем местами эти матрицы, базовой матрицей будет свёртка блоков.
А бывшая базовая матрица теперь будет блок №1. А следующие блоки получаются, как у dimkadimon, плюс один цвет.
Всё получается!

Вот готовое решение:



У svb есть теорема, там что-то про обращённые матрицы. Может, это как раз то, что я сейчас открыла для себя?

[Nataly-Mak]

Проделала то же самое в примере dimkadimon: поменяла местами матрицы.
Всё получилось!

Вот решение:



dimkadimon
по-моему, это решение симпатичнее получилось

Ничего не обобщаю, много неясностей у меня. Может быть, менять местами матрицы можно только для С, являющихся простыми числами (?)
Попробовала для классических таблиц сложения и умножения для С=8, ничего не получилось.

[Nataly-Mak]

alexBlack отмечает в своей статье, что для С=5 достаточно найти базовую матрицу 4х4. В самом деле, потом добавляем обрамление и получаем решение C5N25.

Не помню, приводила ли такой пример. Ну, не беда, если повторю.
Сейчас открыла файл, в котором этот метод у меня описан, и там вижу, что примеры рассматривала и для С=4, и для С=5. Вот для С=4 точно помню, что выкладывала пример.
Но я строила это решение без таблиц сложения и умножения в GF(4), потому что я их просто не знаю.

Внимание!
Подскажите, пожалуйста, таблицы сложения и умножения в GF(4).
В Википедию заглянула, там пример приведён для GF(9).
svb тоже не приводил таблицы сложения и умножения в GF(4).
Как строятся такие таблицы, я пока так и не разобралась. Мудрёно как-то
А мне интересны все примеры, начиная с самых маленьких С.

Итак, решение C5N25, полученное матричным методом.
Базовая матрица Rx:

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

Базовую матрицу я нашла даже не пребором, а просто подбором в программе Эда. Здесь это элементарно.

Свёртка блоков R+:

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

Очевидно, что блоки строятся циклическим сдвигом.

Готовое решение:



Очевидно, что матричный метод работает для всех простых С аналогичным образом.
Также матричный метод работает и для степеней простых, как мы уже знаем, тут просто используем таблицы сложения и умножения в соответствующем GF(p^k).
Наконец, мы видели примеры применения матричного метода для С=6, С=10.

Таким образом, матричный метод вообще самый базовый прямо-таки универсальный, годится для всех С.

[Nataly-Mak]

Рассказала о матричном методе на форуме конкурса:
http://infinitesearchspace.dyndns.org/c ... -aftermath

Пожалуйста, покритикуйте перевод (это тоже Google работал).
Могут ли что-то понять иностранцы в моём сообщении?

Главное, чтобы поняли приглашение принять участие в решении проблемы

[Nataly-Mak]

Для С=7 у нас ещё не было примера

Базовую матрицу взяла в статье alexBlack:

1 2 3 4 5 6
2 2 7 7 4 4
3 2 4 3 3 2
4 2 1 6 2 7
5 2 5 2 1 5
6 2 2 5 7 3

Блоки строятся циклическим сдвигом.
Решение такое получилось:

Цитата:

Очевидно, что матричный метод работает для всех простых С аналогичным образом.

А вообще-то для простых С не надо искать базовую матрицу.
Для таких С тоже ведь существуют конечные поля и таблицы сложения и умножения. Вот их и надо использовать.
Вспомнила, что в самом начале обсуждения этого метода Pavlovsky приводил пример для С=11. Там всё элементарно, не надо искать никакие матрицы. Блоки строятся циклическим сдвигом. Базовая матрица, как написал Pavlovsky, легко угадывается

Не знаю, насколько "легко угадывается" базовая матрица, но я угадала
Вот она для С=7:

1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 5 7 2 4 6
1 4 7 3 6 2 5
1 5 2 6 3 7 4
1 6 4 2 7 5 3
1 7 6 5 4 3 2

Легко написать базовую матрицу по аналогии для любого простого С.

Решение для С=7, построенное по приведённой базовой матрице (блоки строятся циклическим сдвигом, как и в приведённом выше примере с базовой матрицей из статьи alexBlack):



Здесь нет обрамления.
Кому как больше нравится: с обрамлением или без него.

[dimkadimon]

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

На время забудем о базовых матрицах и будем искать два множества перестановок для которых выполнено следующее условие:
для любых двух различных перестановок $i_1,i_2$ из первого множества и любых двух различных перестановок $j_1,j_2$ из второго множества перестановки $(j_1j_2^{-1})(i_1^{-1}i_2)$ и $(i_1^{-1}i_2)(j_1j_2^{-1})$ не пересекаются.

В частности, если для двух множеств перестановок, каждое по девять перестановок десятого порядка, будет выполнено приведённое выше условие, то решение C10N100 существует и легко строится по этим множествам.

Спасибо whitefox, теперь я вроде понял о чем вы говорите. Появился такой вопрос:

Почему нельзя зафиксировать одно из етих множеств (например как 123...N, 23..N1, 34..N12 итд.) и искать только второе множество, таким образом сокращая количество работы в 2 раза? Или етого условия будет не достаточно?

[Nataly-Mak]

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

Меня лично диагональные решения не интересуют.
Herbert доказал что строго-диагональных решений C^2 x C^2 нет для N=8, 9 и 10. Скорее всего их нет для C>10 тоже. Если я правильно понимаю, не строго диагональные решения это когда используются все 2N-1 диагонали? В таком случае они меня тоже не интересуют потому что их гораздо сложнее искать чем строго диагональные - количество диагоналей увеличивается от N до 2N-1.

А кто-нибудь доказал, что не существует не строго диагональное решение C10N100?
По-моему, никто не доказал.

По поводу строго диагонального решения C10N100 вопрос давным-давно решил svb, как мне помнится.

Для не строго диагонального решения перебор в лоб будет, разумеется, огромным и невыполнимым за реальное время.
Значит, надо придумать эвристический алгоритм.
А это не менее интересно, чем все другие методы поиска решения C10N100.

У меня вот сейчас вообще чудеса какие-то: никак не могу найти не строго диагональные решения C3N9, C4N16, C5N25, C6N36, C7N49, хотя строго диагональные решения для таких C и N существуют и найдены.

Сейчас запустила программу whitefox на поиск решения C6N36; программа работает, но неизвестно, какое решение она найдёт первым - строго или не строго диагональное (эта программа строит и те, и другие и работает до первого найденного решения).

Решения C3N9, C4N16, C5N25 программа выдаёт строго диагональные.
То же самое делает программа svb.

(Кстати, если кто интересуется, svb выложил ссылки на свои результаты на форуме конкурса.)

Как же построить указанные не строго диагональные решения? Неужели они не существуют?

-- Пн сен 10, 2012 07:36:36 --

Окно программы whitefox:



Наблюдаю, как идёт перебор. Идёт он понятно: как только 6 возникает, предыдущая циферка увеличивается на единицу.

Итак, полный перебор в лоб?

Уже запускала программу на поиск решения C6N36, но так и не дождалась результата.
Интересен такой момент: строго диагональное решение C6N36 по программе svb находится мгновенно.
Это легко объясняется: у svb ищутся только строго диагональные решения, а перебор для таких решений в разы меньше, чем для не строго диагональных решений.