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

[alexBlack]

(Оффтоп)

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

[Nataly-Mak]

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

1) Берем сильноокрашенный прямоугольник (C^2)x(C+1) для С цветов, полученный по известной всем статье.

Например, берём 4-сильный прямоугольник 16х5, $C=4$.

Цитата:

2) Реплицируем по теореме 3.3 до прямоугольника (C^2)x(C+1)^2.

Вы можете по теореме 3.3 реплицировать 4-сильный прямоугольник 16х5 ($C=4$) до прямоугольника 16х25 4-coloring?
Это интересно.
А я могу реплицировать только до прямоугольника 16х20 4-coloring.

-- Ср окт 03, 2012 21:23:47 --

alexBlack
спасибо за показ матриц.
Начинаю проверять. Сначала привела все матрицы к формату матриц Pavlovsky.
Пока с его матрицами не сравнивала.
Взяла матрицу №1, повернула её на 90 градусов по часовой стрелке, затем переставила столбцы; получила матрицу №6. Значит, матрицу №6 уже можно отбросить.
Сейчас проверю другие матрицы на эти преобразования (поворот и перестановка строк/столбцов).

-- Ср окт 03, 2012 21:42:27 --

С точностью до указанный преобразований попарно неизоморфными остались только 5 матриц (№1- №5).
Теперь у alexBlack матриц меньше, чем у Pavlovsky.
Сколько же их на самом деле?

[Nataly-Mak]

Сравнила матрицы alexBlack с матрицами Pavlovsky.
Точного совпадения вообще не нашла, а раньше вроде находила совпадение одной известной тогда матрицы.
Вот ёлки зелёные! Закрутили, завернули матрицы, сам чёрт не разберёт

-- Ср окт 03, 2012 22:56:02 --

Кажется, всё становится понятным.
Беру блоки, построенные по исходному ЛК №1 Pavlovsky:

(Оффтоп)

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

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

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

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

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

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

Заполняю этими блоками базовую матрицу alexBlack №3 (эта матрица приведена в статье). При этом блоки я строю, конечно, по способу Pavlovsky)
И... решение не получается!

[я могла ошибиться в эксперименте; перегрелась уже с этими матрицами ]

Вот так: исходные ЛК у alexBlack и Pavlovsky изоморфны, но это ещё не значит, что будут одинаковы все базовые матрицы, соответсвующие каждому из этих ЛК. Эти базовые матрицы для каждого ЛК нужно искать перебором.

Не забудем главный вывод whitefox: если существует базовая матрица, которую можно заполнить блоками, то эту же базовую матрицу можно заполнить и перестановками (соответствующими этому набору блоков).
Я долго сомневалась в правильности этого вывода, но теперь склоняюсь к тому, что он правильный.

[Nataly-Mak]

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

Поставим оба решения рядом, сравним:



На мой непросвещённый взгляд эти решения неизоморфны.

Вчера задала вопрос об изоморфности этих решений на форуме конкурса.
Вот что ответил Tom Sirgedas:

Цитата:

They're unique. The color counts don't match.
Also, note that for both you can swap rows to get a purely diagonal solution.

Он написал, что из обоих решений можно получить диагональное решение.
Ну, из решения Herbert Kociemba, конечно, можно, потому что оно получено из строго диагонального решения С4N13.
А получила я его так: взяла в строго диагональном решении базовый вектор и начала от него делать "ход конём".
Чтобы получить из своего решения "ход конём" строго диагональное решение C4N13, взяла базовый вектор в решении "ход конём":

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

и от этого базового вектора построила все диагонали.
Так невзначай построила строго диагональное решение C4N13
При этои моё строго диагональное решение не изоморфно решению Herbert Kociemba.

Таким образом, со строго диагональными решениями всё получается: по базовому вектору строго диагональное решение переводится в строгое решение "ход конём" и обратно.
Наверное, точно так же и с не строго диагональными решениями.
Похоже, что эти два вида диагональных решений действительно эквивалентны.
Но мне решения "ход конём" нравятся больше.

-- Чт окт 04, 2012 06:46:37 --

Ещё о базовых матрицах.
Матрица whitefox в точности совпадает с матрицей №1 alexBlack.

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

[whitefox]

Матрица:

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 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5

но не для ЛК №1 Pavlovsky:

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

Именно поэтому она и не изоморфна ни одной из восьми базовых матриц Pavlovsky, соответствующих ЛК №1, хотя эти латинские квадраты и изоморфны.

-- 04 окт 2012, 07:46 --

Теория Pavlovsky нуждается в уточнении.
Внутри класса изоморфных ЛК существуют подклассы, имеющие собственные наборы базовых матриц.

-- 04 окт 2012, 07:56 --

Идея использовать ЛК для представления упорядоченного множества попарно не пересекающихся перестановок красива, но порочна.

В общем случае каждому ЛК соответствуют два таких множества:
1. множество столбцов;
2. множество строк.

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

Нужно рассмотреть классы изоморфизма таких множеств вместо классов изоморфизма ЛК.

[Nataly-Mak]

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

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

1) Берем сильноокрашенный прямоугольник (C^2)x(C+1) для С цветов, полученный по известной всем статье.

Например, берём 4-сильный прямоугольник 16х5, $C=4$.

Цитата:

2) Реплицируем по теореме 3.3 до прямоугольника (C^2)x(C+1)^2.

Вы можете по теореме 3.3 реплицировать 4-сильный прямоугольник 16х5 ($C=4$) до прямоугольника 16х25 4-coloring?
Это интересно.
А я могу реплицировать только до прямоугольника 16х20 4-coloring.

Размышляю...
Наверное, тут имелось в виду: "Реплицируем по теореме 3.3 до прямоугольника (C^2)x(C+1)^2" 5-coloring? Ну, это можно, если смотреть на исходный 4-сильный прямоугльник 16х5 как на 5-сильный.
Так, сейчас пойду реплицирую

[Pavlovsky]

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

Теория Pavlovsky нуждается в уточнении.Внутри класса изоморфных ЛК существуют подклассы, имеющие собственные наборы базовых матриц.

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

Пусть у нас есть набор C перестановок, сведенных в ЛК CxC. И есть базовая матрица MxK. Такая что если в каждую ячейку подставить перестановку с соответствующим номером, то получится сльноокрашенный прямоугольник CMxK.
1) Поменяем в исходном ЛК две строки местами. Это эквивалентно, что в сильноокрашенном прямоугольнике мы поменяли местами M пар строк. Понятно что свойство сильноокрашенности останется неизменным.
2) Поменяем в исходном ЛК местами пару колонок (пусть колонки i и j). Это эквивалентно, тому что мы изменили нумерацию наших перестановок. Тогда если в базовой матрице поменять число i на j и наоборот. Мы получим тот же сильноокрашенный прямоугольник.
3) Сделаем в исходном ЛК замену символов. Если ту же операцию сделать и в сильноокрашенном прямоугольнике CMxK, то опять же свойство сильноокрашенности не изменится.

Если в исходном ЛК поменять местами строки, то вид базисных матриц не изменится.
Если в исходном ЛК сделать замену символов, то вид базисных матриц не изменится.
А вот если в исходном ЛК поменять местами колонки, то это равносильно изменению нумерации Перестановок (ЛК) в наборе. В этом случае вид базисных матриц изменися.
Пусть мы переставили колонки в исходном ЛК так:
(1,2,3,4,...)
(a1,a2,a3,...)
Тогда это преобразовние мы должны применить и к числам в ячейках базисной матрицы.

Вывод. У двух изоморфных (изотопных) исходных ЛК, базисные матрицы могут быть различными. Но существует взаимнооднозначное соответсвие переводящее одни в другие.

-- Чт окт 04, 2012 12:33:04 --

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

Размышляю...

Наталия вы не над тем размышляете. Может коряво, я изложил простой алгоритм первого класса.

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

Наверное, тут имелось в виду: "Реплицируем по теореме 3.3 до прямоугольника (C^2)x(C+1)^2" 5-coloring?

Естественно

Цитата:

до прямоугольника (C^2)x(C+1)^2" (C+1)-coloring

Цель моего поста в другом. Показать, что диагонльные решения по теореме Зингера эквиваелнтны алгоритмам добавления одного цвета к решениям С=p^s, полученным алгоритмами алгебраического типа.
Надо бы конечно взять диагональное решение по теореме Зингера для С+1 и выделить в нем сильноокрашенный прямоугольник C^2x(C+1) для C цветов. Но делать скорее всего это не буду. Ибо разочаровался в теореме Зингера.

[whitefox]

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

А вот если в исходном ЛК поменять местами колонки, то это равносильно изменению нумерации Перестановок (ЛК) в наборе.

То есть к изоморфным преобразованиям, допустимым для базовых матриц, нужно добавить ещё и произвольную перестановку номеров, так как Перестановки в наборе (столбцы/строки ЛК) могут быть упорядочены любым способом.

В общем случае для базовой матрицы перестановок допустимы следующие преобразования, переводящие одну базовую матрицу в другую:
1. перестановка строк;
2. перестановка столбцов;
3. умножение справа всех перестановок одной строки на одну и туже перестановку;
4. умножение слева всех перестановок одного столбца на одну и туже перестановку;
5. транспозиция;
6. перестановка номеров.

[Nataly-Mak]

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

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

Перестановка символов
(0,1,2,3,4,5)
(4,2,1,5,3,0)
Плюс нормализация
Получим:

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

Pavlovsky
вот так вы преобразовали исходный ЛК alexBlack в ваш исходный ЛК №1.
В этом преобразовании есть и перестановка символов, и перестановка строк, и перестановка столбцов.
Покажите теперь, какое преобразование надо применить к базовой матрице alexBlack №1 (или что то же - к базовой матрице whitefox), чтобы она стала пригодной для заполнения блоками, полученными из вашего исходного ЛК (другими словами: чтобы при заполнении этой матрицы данными блоками получилось правильное решение).
Такое преобразование должно существовать, если вы утверждаете, что между этими матрицами существует взаимнооднозначное соответствие.

---

Реплицировала 4-сильный прямоугольник 16х5 до прямоугольника 16х25 5-coloring, добавила 5 строк, получила решение 21х25 5-coloring.



Что дальше? Понятно, что в этом решении содержится решение C5N21. Это решение будет эквивалентно строго диагональному решению, получаемому по CDS? Очень интересно. И как же из одного получить другое?
Вообще очень хотелось бы, чтобы вы свои теории сопровождали конкретными примерами.
На конкретном примере всё становится более-менее понятным, если пример хорошо согласуется с теорией.

-- Чт окт 04, 2012 11:45:16 --

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

Цель моего поста в другом. Показать, что диагонльные решения по теореме Зингера эквиваелнтны алгоритмам добавления одного цвета к решениям С=p^s, полученным алгоритмами алгебраического типа.
Надо бы конечно взять диагональное решение по теореме Зингера для С+1 и выделить в нем сильноокрашенный прямоугольник C^2x(C+1) для C цветов. Но делать скорее всего это не буду. Ибо разочаровался в теореме Зингера.

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

Вот строго диагональное решение C5N21, построенное по CDS (Herbert Kociemba):



Как выделить из этого решения 4-сильный прямоугльник или 5-сильный прямоугольник?
Как это решение связано с показанным выше решением, полученным классическим способом?

[Pavlovsky]

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

То есть к изоморфным преобразованиям, допустимым для базовых матриц, нужно добавить ещё и произвольную перестановку номеров, так как Перестановки в наборе (столбцы/строки ЛК) могут быть упорядочены любым способом.

Делать надо осторожно. Ведь у двух изоморфных ЛК наборы матриц различны! Ваши преобразования ищут изоморфные матрицы для некоторого конкретного ЛК. А произвольная перестановка номеров задает соответствие между наборами матриц разлиных изоморфных ЛК. То есть после пеоизвольной перестановки номеров мы можем получить матрицу которая не годится для конкретного исходного ЛК (она годится для его изморфного брата).

[whitefox]

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

То есть после пеоизвольно перестановки номеров мы можем получить матрицу которая не годится для конкретного исходного ЛК (она годится для его изморфного брата).

Но это-то нам как раз и нужно.

[Pavlovsky]

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

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

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

В этом преобразовании есть и перестановка символов, и перестановка строк, и перестановка столбцов.

Думаете такое преобразование найти легко? Будет время поищу. А может и не буду искать.

-- Чт окт 04, 2012 13:09:50 --

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

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

В книге Холл Комбинаторика глава 12.3 показан пример как из решения C5N21, полученного по теореме Зингера, выделить набор ортогональных ЛК 4х4.

[Nataly-Mak]

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

Думаете такое преобразование найти легко? Будет время поищу. А может и не буду искать.

Но вы ведь знаете как его искать! Переставьте номера в базовой матрице в соответствии с тем, как вы переставили столбцы в ЛК - вот и все дела
А если это преобразование найти трудно, возникает большое сомнение в его существовании.

-- Чт окт 04, 2012 12:13:45 --

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

В книге Холл Комбинаторика глава 12.3 показан пример как из решения C5N21, полученного по теореме Зингера, выделить набор ортогональных ЛК 4х4.

Ага, то есть Холл в своей книге уже всё доказал?
А вы здесь писали, что работаете над этим доказательством. Я думала, что у вас своё доказательство, потому и просила его показать на конкретном примере.

[whitefox]

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

Делать надо осторожно. Ведь у двух изоморфных ЛК наборы матриц различны! Ваши преобразования ищут изоморфные матрицы для некоторого конкретного ЛК. А произвольная перестановка номеров задает соответствие между наборами матриц разлиных изоморфных ЛК.

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

В общем случае для базовой матрицы перестановок допустимы следующие преобразования, переводящие одну базовую матрицу в другую:
1. перестановка строк;
2. перестановка столбцов;
3. умножение справа всех перестановок одной строки на одну и туже перестановку;
4. умножение слева всех перестановок одного столбца на одну и туже перестановку;
5. транспозиция;
6. перестановка номеров.

Преобразования 1, 2, 5 оставляют исходное множество Перестановок (ЛК) без изменения.
Если это исходное множество Перестановок является группой (как в случае ЛК №1 alexBlack и ЛК №1 Pavlovsky), то преобразования 3, 4 также не изменяют это множество (ЛК), когда множитель тоже принадлежит этой группе.
Преобразование 6 не изменяет это множество, а только переупорядочивает его.

-- 04 окт 2012, 11:22 --

Кажется alexBlack не рассматривал латинские квадраты.
Под ЛК №1 alexBlack я имел ввиду:

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

[Pavlovsky]

Холл. Комбинаторика
Теорема 12.3.3. Если дана блок-схема D* с параметрами Ь = n^2 + n, v = n^2, г=n+1, k = n, Lymda=1,
то мы можем присоединить к ней, причем единственным способом, еще один блок с n + 1 новыми элементами и добавить один из новых элементов к каждому из данных первоначально блоков так, чтобы получилась симметричная схема D с параметрами v = Ь = n^2 + n + 1, r = k = n + 1, Lymda = 1.