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

[dimkadimon]

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

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

Тут я пробовал все возможные ходы. Значит все r, c, и k. Чтобы все было равномерно я выбирал случайный порядок для расмотра ходов.

А вот здесь нет.
Ячейки я выбирал тоже случайно, но только из числа содержащих ошибки, причём вероятность выбора была пропорциональна числу ошибок. И уже для выбранной ячейки проверял все цвета.

Фактически я тоже самое делал, потому что я не менял клетки в которых нет ошибок. А вот с пропорциональностью вы хорошо придумали.

[whitefox]

Все 10 базовых матриц, приведённых alexBlack, изоморфны.

Например, возьмём матрицу №1:

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

И выполним над ней следующие изоморфные преобразования:
1. ко всем элементам второй строки прибавим по модулю 6 число 5;
2. ко всем элементам третьей строки прибавим по модулю 6 число 4;
3. ко всем элементам четвёртой строки прибавим по модулю 6 число 3;
4. ко всем элементам пятой строки прибавим по модулю 6 число 1.
(вместо 0 используем 6)

Получим:

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

Переместим первый столбец на последнее место:

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

Получили матрицу №7.

Аналогично и для остальных матриц.

[Nataly-Mak]

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

Все 10 базовых матриц, приведённых alexBlack, изоморфны.

Интересный вывод.
Я сократила количество базовых матриц alexBlack вдвое, а вы сократили ещё в 5 раз. В результате осталась всего одна базовая матрица

[whitefox]

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

Интересный вывод.
Я сократила количество базовых матриц alexBlack вдвое, а вы сократили ещё в 5 раз. В результате осталась всего одна базовая матрица

Возможно, что и базовые матрицы Pavlovsky тоже изоморфны.

[whitefox]

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

Возможно, что и базовые матрицы Pavlovsky тоже изоморфны.

Так и есть все базовые матрицы Pavlovsky для ЛК №1 изоморфны.

Например, возьмём матрицу №1:

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

И выполним над ней следующие изоморфные преобразования:
1. все элементы второй строки умножим справа на перестановку №5 (5 6 2 1 3 4);
2. все элементы третьей строки умножим справа на перестановку №4 (4 3 5 6 1 2);
3. все элементы четвёртой строки умножим справа на перестановку №2 (2 1 4 3 6 5);
4. все элементы пятой строки умножим справа на перестановку №3 (3 4 6 5 2 1).

Получим:

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

Нормализуем:

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

Получили матрицу №5.

Аналогично и для остальных матриц.

[Nataly-Mak]

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

Так и есть все базовые матрицы Pavlovsky для ЛК №1 изоморфны.

Наверное, оба автора совсем не рассматривали изоморфизм базовых матриц.

Впрочем, изоморфизм (базовых матриц да и самих решений) в обсуждении задачи, по-моему, очень слабое место.
Изоморфизм решений для меня всегда был интересным и важным вопросом. Однако я в нём так и не разобралась. А вот Tom Sirgedas и Roland Postle хорошо знают, как определять изоморфны ли раскраски.
dimkadimon тоже это знает, но только теоретически.

Когда я составляла базу данных диагональных решений, изоморфность двух решений определяла полу-интуитивно
Пока никто не прислал мне замечание, что я поместила в БД два изоморфных решения, хотя это не исключено.
Правда, БД смотрели, насколько мне известно, всего 2 человека.

[whitefox]

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

Когда я составляла базу данных диагональных решений, изоморфность двух решений определяла полу-интуитивно

Для нестрого диагональных решений критерий изоморфности простой: два нестрого диагональных решения изоморфны тогда и только тогда, когда их канонические базовые вектора равны.
http://dxdy.ru/post621749.html#p621749

[Nataly-Mak]

А это два строго диагональных решения C3N8:



Изоморфны ли эти решения? Я думаю, что изоморфны.

whitefox
я знаю, что вы просматривали БД не строго диагональных решений в процессе её создания. А окончательный вариант БД вы смотрели? Есть ли там изоморфные решения?
Много раз меня интуиция подвела?

-- Пт окт 05, 2012 23:00:43 --

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

Для нестрого диагональных решений критерий изоморфности простой: два нестрого диагональных решения изоморфны тогда и только тогда, когда их канонические базовые вектора равны.
http://dxdy.ru/post621749.html#p621749

А для строго диагональных решений этот критерий не годится?

-- Пт окт 05, 2012 23:36:36 --

Выкладываю вторую часть книги "Monochromatic Squares или Математическая раскраска":
http://narod.ru/disk/62073950001.269e0b ... 2.rar.html

Здесь:
Глава 5. Метод использования ортогональных латинских квадратов
Глава 6. Расширение области применения теоремы 3.3

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

Мне пришло письмо в ЛС, автор пишет, что книга понятна только тем, кто участвовал в обсуждении задачи. Так ли это?
Он считает, что книгу надо писать так, чтобы не приходилось идти, скажем, в статью [1] за подробностями (это главная статья, которую участники темы хорошо знают). Да, я не поместила ссылки на статьи, виновата. Но это, разумеется, будет сделано в конце книги. К тому же ссылка на статью [1] есть на главной странице конкурса, а на эту страницу я указала ссылку во Введении.

Выложила вторую часть в формате doc (в этом формате намного лучше качество картинок).

dimkadimon
если файл у вас опять не откроется, сообщите. Я тогда выложу и в формате pdf.
Как всегда, прошу присылать замечания. Ценные замечания постараюсь учесть.

Сейчас меня вытащили на ПЕН, там в одной теме ссылаются на наши (с alexBlack и svb) работы по маршрутам коня. Заглянула, автору ЛС ответила. Заодно заглянула в свою тему "Играют все!"
Там в гордом одиночестве работает svb
Если кто интересуется задачей, загляните в эту тему. Он выложил там новую статью.
Данную тему он игнорирует. Что ж, игнор иногда вещь полезная (для обеих сторон!)

[Nataly-Mak]

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

Для нестрого диагональных решений критерий изоморфности простой: два нестрого диагональных решения изоморфны тогда и только тогда, когда их канонические базовые вектора равны.

Вот два не строго диагональных решения C4N8:



whitefox
в вашем решении базовый вектор канонический.

Решение Herbert Kociemba я получила модификацией его строго диагонального решения C5N21 путём удаления строк и столбцов. Поэтому в решении нестандартное обозначение цветов, но это легко исправить, заменив цвет 5 (Е, розовый) на цвет 1 (А, голубой). Далее ещё раз сделала замену цветов: 2 -> 1, 1 -> 2.
У меня получился такой базовый вектор в этом решении:

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

Как преобразовать этот базовый вектор к каноническому виду? Что-то не соображу

Добавлено

Кажется, получилось. Сделала сначала замену цветов: 2 -> 3, 3 -> 2, а потом замену цветов: 3 -> 4, 4 -> 3.

Получила такой вектор:

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

Это канонический вектор?
Значит, приведённые решения неизморфные?

Это решение Herbert Kociemba с преобразованным базовым вектором (ещё изменила направление диагоналей):

[Nataly-Mak]

Красивая раскраска?



Построена ходом коня на основе строго диагонального решения C3N9 (Herbert Kociemba).

Пусть метод не даёт рекордов, плюс ему за красоту.
Сейчас построю аналогичное решение C8N26 на основе своего строго диагонального решения C4N13.
Вот:



И ещё хочу шедевр dimkadimon C5N25 (диагональное строго "ход конём") так же сделать. Получится 10-цветная раскраска всего 50х50, но... красиво.

[Nataly-Mak]

Вот последняя раскраска - C10N50 (из решения dimkadimon)



-- Сб окт 06, 2012 07:48:25 --

Herbert Kociemba в сообщении #610748 писал(а):

Diagonal solutions exist for C4N16, C5N25, C6N36 and C7N49, but *not* for C8N64, C9N81, C11N121 and presumably not for any C>11.

Здесь речь идёт о строго диагональных решениях.
Итак, утверждается, что строго диагональных решений C8N64, C9N81, C11N121 не существует. Дальше было сказано, что строго диагональное решение C10N100 тоже не существует.
А что можно сказать о строго диагональных решениях C12N144 и C15N225?

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

[Nataly-Mak]

Решение C12N24 не строго "ход конём", сама не знаю, как умудрилась построить
За основу взято решение C12N12 не строго "ход конём", это решение расположено в левом верхнем квадранте 12x12.
Нельзя ли как-нибудь исхитриться аналогично построить решение C12N144

[whitefox]

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

Изоморфны ли эти решения? Я думаю, что изоморфны.

Верно, они изоморфны.
Примените ко второй раскраске перестановку цветов 3 1 2, и Вы получите первую.

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

whitefox
я знаю, что вы просматривали БД не строго диагональных решений в процессе её создания. А окончательный вариант БД вы смотрели? Есть ли там изоморфные решения?
Много раз меня интуиция подвела?

Извините, ещё не смотрел.

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

А для строго диагональных решений этот критерий не годится?

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

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

Как преобразовать этот базовый вектор к каноническому виду? Что-то не соображу

Выпишем из базового вектора первые появления всех чисел в том порядке, в котором они идут в базовом векторе:

1 3 4 2

Получили перестановку чисел от 1 до 4.
Применим перестановку цветов 1 4 2 3 (обратную к полученной) к исходному базовому вектору, получим канонический базовый вектор:

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

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

Это канонический вектор?
Значит, приведённые решения неизморфные?

Да, и да.

[Nataly-Mak]

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

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

Изоморфны ли эти решения? Я думаю, что изоморфны.

Верно, они изоморфны.
Примените ко второй раскраске перестановку цветов 3 1 2, и Вы получите первую.

Да, действительно, просто; могла бы и сама догадаться
Как-то плохо у меня с перестановками получается, могу только по порядку делать замены цветов друг на друга.

Цитата:

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

И как? На простеньком примере можете показать?

Спасибо за разъяснения, что-то начинает проясняться с изоморфностью диагональных решений

[whitefox]

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

Как-то плохо у меня с перестановками получается, могу только по порядку делать замены цветов друг на друга.

По известной теореме любую перестановку можно представить в виде произведения транспозиций. В частности, перестановка 3 1 2 равна последовательному выполнению замен:
1<->3, 1<->2.

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

И как? На простеньком примере можете показать?

Покажу, но чуть позже. Сейчас занят.