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

[Nataly-Mak]

Цитата:

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

Квадрат NxN надо раскрасить в С цветов так, чтобы ни в одном прямоугольнике (квадратике), находящемся внутри этого квадрата, все 4 вершины не были одного цвета.

Вы тему-то читате? Или только сейчас заглянули на последнюю страницу и сразу всё захотели понять
Я ведь приводила картинки-раскраски, решение для C=3, N=81x81. Поглядите хотя бы на эти картинки, на них, по-моему, всё вполне доходчиво.

Кстати, по поводу рэндома...
Вот у меня попытка составить набор непересекающихся комбинаций для N=10 потерпела полных крах, мне удалось найти только 19 неперескающихся комбинаций.

Теперь действуем так: генерируем очень много произвольных комбинаций из чисел 1,2,3,...,10 с помощью рэндома, скажем, штук 1000. И начинаем затем выбирать непересекающиеся. Как вы думаете, много наберём? Я думаю, что не очень.

Можно так: сгенерировали первую комбинацию, записали её в набор; генерируем вторую, сразу проверяем годится или не годится - сравнением с первой комбинацией; если годится, записывае эту комбинацию в набор, не годится - отбрасываем, генерируем следующую комбинацию и т.д.
Если так покрутить программу сутки, много найдётся непересекающихся комбинаций?

А вдруг их больше 19 вообще не существует

[Alexu007]

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

Квадрат NxN надо раскрасить в С цветов так, чтобы ни в одном прямоугольнике (квадратике), находящемся внутри этого квадрата, все 4 вершины не были одного цвета.

Спасибо, это как раз то, что я не понял.

Цитата:

Вы тему-то читате? Или только сейчас заглянули на последнюю страницу и сразу всё захотели понять
Я ведь приводила картинки-раскраски, решение для C=3, N=81x81. Поглядите хотя бы на эти картинки, на них, по-моему, всё вполне доходчиво.

Доходчиво, если знать предыдущее правило. Очевидно, что чем меньше С, тем сложнее построить большой квадрат. Честно говоря, интуитивно не верится, что для С = 3 возможно N = 81, но и нет оснований не доверять вам. Я правильно понял - внутри квадрата (прямоугольника) не должно быть ни одного прямоугольника с одинаковыми вершинами?

Цитата:

Кстати, по поводу рэндома...
Вот у меня попытка составить набор непересекающихся комбинаций для N=10 потерпела полных крах, мне удалось найти только 19 неперескающихся комбинаций.

Теперь действуем так: генерируем очень много произвольных комбинаций из чисел 1,2,3,...,10 с помощью рэндома, скажем, штук 1000. И начинаем затем выбирать непересекающиеся. Как вы думаете, много наберём? Я думаю, что не очень.

Немного поконкретнее пожалуйста. Что понимается под словом "непересекающиеся"? Из чисел 0 - 9 можно составить большое количество разных 10-значных цифр, в которых не повторяется ни одна из цифр, но это не является обязательным условием конкурса, ведь так?

Цитата:

Можно так: сгенерировали первую комбинацию, записали её в набор; генерируем вторую, сразу проверяем годится или не годится - сравнением с первой комбинацией; если годится, записывае эту комбинацию в набор, не годится - отбрасываем, генерируем следующую комбинацию и т.д.
Если так покрутить программу сутки, много найдётся непересекающихся комбинаций?

А вдруг их больше 19 вообще не существует

Пробовать надо, для начала нужно написать функцию, вычисляющую "правильность" полученных квадратов.

[Nataly-Mak]

Alexu007 в сообщении #583750 писал(а):

Честно говоря, интуитивно не верится, что для С = 3 возможно N = 81, но и нет оснований не доверять вам. Я правильно понял - внутри квадрата (прямоугольника) не должно быть ни одного прямоугольника с одинаковыми вершинами?

N=81 как раз возможно, невозможно N=81x81, как у меня написано
Ну, здесь и ёжику понятно, что я просто машинально написала N=81x81.
Конечно, N=81!

[здесь под N понимается не сторона квадрата, а количество очков в решении, квадрат здесь, понятно, 9х9]

На картинки-то можно посмотртеть с решением C=3, N=81? Зачем здесь что-то интуитивно понимать, когда есть наглядный пример...

Ну, вот, видите, я вас ещё больше запутала Больше ничего не буду объяснять.

-- Вт июн 12, 2012 14:17:34 --

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

Показываю два решения C=3, N=81, полученные по двум разным алгоритмам:



По гармонии раскраски второе решение мне нравится гораздо больше

Первое решение построено по алгоритму, который описал Pavlovsky. Второе решение - по алгоритму, описанному мной (ссылку на статью приводила выше), построение решения по этому алгоритму здесь показано.

Вот этот пост вы смотрели?
Тут вроде как правильно написано: C=3, N=81.

[Alexu007]

C = 3, N = 9x9 - вот так всё понятно без разночтений. Или речь идёт только о квадратах (а для прямоугольника N = 81 может быть и 27х3).

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

[Nataly-Mak]

В конкурсной задаче речь идёт только о квадратах! Поэтому никаких разночтений быть не может. Прямоугольники на конкурсе не рассматриваются.
N=81 может означать только квадрат 9х9.

[Nataly-Mak]

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

Интереcная лемма мне попалась при просмотре статей:

Если Gn,m strong-c-colorable, то Gn,cm strong-c-colorable.

Виновата, наврала в цитате.
Gn,cm будет не strong-c-colorable, а c-colorable.

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

Картинка из статьи

А по какой схеме из Gn,m strong-c-colorable получают Gn,cm c-colorable?

Я строила так:
в прямоугольнике 4х6 strong-3-colorable , который приведён в качестве примера в статье, выполнила замену

1={1,2,3}
2={2,3,1}
3={3,1,2}

Вот что у меня получилось (сверху прямоугольник 4х6 strong-3-colorable, внизу прямоугольник 4х18 3-colorable):



Кажется, поняла схему, по которой в примере построен прямоугольник 4х18 3-colorable.
Первый прямоугольник 4х6 - исходный, при заполнении второго прямоугольника 4х6 в исходном прямоугольнике делают замены:

B -> G
G -> R
R -> B

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

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

Таким образом, например, построение квадрата 36х36 6-colorable можно выполнить, найдя прямоугольник 36х6 strong-6-colorable. Такой прямоугольник и дадут, например, 36 непересекающихся комбинаций из чисел 1,2,3,4,5,6.
Вот только найти набор из 36 непересекающихся комбинаций мне не удалось (нашла только набор из 31 комбинации). Существует ли такой набор? Вопрос для меня очень интересный!

Вообще эту лемму можно считать одним из базовых алгоритмов решения конкурсной задачи. Под этот алгоритм подходит и построение для С - простых чисел, и построение для С, являющихся степенью простых чисел, и для всех других С, для которых возможно построить Gn,m strong-C-colorable.
Именно по этому алгоритму я построила решение C=6, N=31x31.

[Nataly-Mak]

А между тем алгоритм построения решения C=6, N=36x36 "раскололи" уже 8 человек.

6 36 1296  Alex Chernov @ 23:02:26 on 05-31-2012 8

Если этот алгоритм является открытием Алексея Чернова (он первым получил это решение), то довольно несложным открытием, доступным многим.

Вполне возможно, что сработает этот метод:

Цитата:

Таким образом, например, построение квадрата 36х36 6-colorable можно выполнить, найдя прямоугольник 36х6 strong-6-colorable.

[Alexu007]

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

Таким образом, например, построение квадрата 36х36 6-colorable можно выполнить, найдя прямоугольник 36х6 strong-6-colorable. Такой прямоугольник и дадут, например, 36 непересекающихся комбинаций из чисел 1,2,3,4,5,6.
Вот только найти набор из 36 непересекающихся комбинаций мне не удалось (нашла только набор из 31 комбинации). Существует ли такой набор? Вопрос для меня очень интересный!

[Nataly-Mak]

Эти комбинации не являются непересекающимися.
Сразу вижу пересечение - пара (4,1) вот в этих комбинациях:

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

Комбинации из чисел 0,1,2,3,4,5 надо располагать в строках, а не в столбцах, как у вас.
Прямоугольник 36х6 - это прямоугольник, в котором 36 строк и 6 столбцов, в каждой строке прямоугольника записана комбинация из чисел 0,1,2,3,4,5.

Я выше выкладывала прямоугольник 30х6 strong-6-colorable, посмотрите хоть на него, какой он из себя

[Nataly-Mak]

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

Берём прямоугольник 16х8 stpong-8-colorable:

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

Прямоугольник составлен из непересекающихся комбинаций чисел 1,2,3,4,5,6,7,8.
Это часть прямоугольника 64х8 stpong-8-colorable.

Из данного прямоугольника по лемме можно получить прямоугольник 16х64 8-colorable. Не буду показывать такой большой прямоугольник, покажу только квадрат 16х16 8-colorable.

Заполняла второй прямоугольник 16х8, делая замены в исходном прямоугольнике, как в статье:

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 6
6 -> 7
7 -> 8
8 -> 1

Попросту говоря, все элементы прямоугольника увеличиваются на 1, число 9 берётся по модулю 8, то есть заменяется на 1. Вот и вся схема. Очень просто!

В результате получился такой квадрат 16х16 8-colorable:

2,1,2,3,4,5,6,7,3,2,3,4,5,6,7,8,
2,2,1,4,3,6,5,8,3,3,2,5,4,7,6,1,
2,3,4,1,2,7,8,5,3,4,5,2,3,8,1,6,
2,4,3,2,1,8,7,6,3,5,4,3,2,1,8,7,
2,5,6,7,8,1,2,3,3,6,7,8,1,2,3,4,
2,6,5,8,7,2,1,4,3,7,6,1,8,3,2,5,
2,7,8,5,6,3,4,1,3,8,1,6,7,4,5,2,
2,8,7,6,5,4,3,2,3,1,8,7,6,5,4,3,
3,1,3,5,7,4,2,8,4,2,4,6,8,5,3,1,
3,2,4,6,8,3,1,7,4,3,5,7,1,4,2,8,
3,3,1,7,5,2,4,6,4,4,2,8,6,3,5,7,
3,4,2,8,6,1,3,5,4,5,3,1,7,2,4,6,
3,5,7,1,3,8,6,4,4,6,8,2,4,1,7,5,
3,6,8,2,4,7,5,3,4,7,1,3,5,8,6,4,
3,7,5,3,1,6,8,2,4,8,6,4,2,7,1,3,
3,8,6,4,2,5,7,1,4,1,7,5,3,6,8,2

-- Ср июн 13, 2012 21:37:27 --

Россияне, похоже, ушли в отпуск

1  Alex Chernov 19.890300 06-08-2012 @ 17:45:54
2  Nick Gardner 19.864000 06-10-2012 @ 23:18:05
3  Tom Sirgedas 19.842900 06-07-2012 @ 07:11:18
4  Il brigante Pennastorta 19.842900 06-08-2012 @ 16:28:33
5  Herbert Kociemba 19.704300 06-12-2012 @ 21:32:02
6  Artem Karavaev 19.584400 06-05-2012 @ 09:50:07
7  Valery Pavlovsky 19.584400 06-05-2012 @ 23:19:08
8  Michael van Fondern 19.406400 06-13-2012 @ 09:48:02
9  Jarek Wroblewski 19.184500 06-04-2012 @ 08:14:00
10  Anton Voropaev 19.184500 06-04-2012 @ 15:38:59

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

Только Алексей Чернов пока удерживает позицию, и то положение его весьма шаткое, отставание конкурсанта со 2-го места меньше 3 соток, а там очень близки и результаты конкурсантов с 3-го и 4-го мест.

Как верно заметил Pavlovsky, лафа кончилась
Всё, что можно было получить, не напрягаясь, многие получат или уже получили.

[Nataly-Mak]

В теме "Уникальные перестановки" выложила набор из 20 перестановок чисел 1,2,3,...,10, который получила из двух известных ортогональных латинских квадратов 10-го порядка
(Diagonal Latin Squares, J.W. Brown и другие, 1992 г.)

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

Вот этот набор:

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

Вчера попробовала применить к этому прямоугольнику 20х10 указанную выше лемму, будучи уверена в том, что он strong-10-colorable.
Построила квадрат 20х20, скормила его программе Эда и... обнаружила, что в квадрате полно ошибок, то есть он не получился 10-colorable.

Долго искала ошибку, думала, что ошиблась при замене чисел. Но нет, тут ошибку не нашла. Тогда стала искать ошибку в исходном прямоугольнике 20х10, и здесь её сразу же обнаружила: повторяющаяся пара чисел (4,2), строки 1-ая и 13-ая сверху. Может быть, и ещё есть пересечения, дальше не смотрела, нет смысла; достаточно одного пересечения, чтобы лемма не применилась.

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

Такие вот странные ортогональные ЛК 10-го порядка.
Возникло желание посмотреть на ортогональные ЛК 12-го порядка. Дают ли они уникальные перестановки?

[Nataly-Mak]

Не всё так плохо оказалось с ортогональными ЛК 10-го порядка.
Взяла пару ОЛК Паркера - это самая первая найденная пара ОЛК 10-го порядка.
С этими ЛК всё получилось. Выписала из них столбцы, они дали набор из 20 уникальных перестановок. Добавила к ним комбинации из одинаковых чисел и получила прямоугольник 30х10 strong-10-colorable:

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

Применив к этому прямоугольнику указанную выше лемму, можно получить прямоугольник 30х100 10-colorable. Я ограничилась квадратом 30х30:

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

Такое вот простенькое решение для C=10, всего N=30x30.
Ну, решение C=10, N=82x82, как я уже отмечала, элементарно получается из решения C=9, N=81x81.
Конечно, весьма интересно узнать, как строится решение C=10, N=91x91 по известному алгоритму, но известный алгоритм мне пока неизвестен

А на конкурсе найдено уже решение C=10, N=93x93. Тоже очень интересное решение.

[Zealint]

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

Как верно заметил Pavlovsky, лафа кончилась
Всё, что можно было получить, не напрягаясь, многие получат или уже получили.

Дело не только в лафе. Сейчас июнь, многие студенты сдают сессию, а преподаватели принимают экзамены и дают последние установки студентам, защищающим бакалаврские работы и магистерские диссертации. У меня, например, много студентов в этом году. А конкурс ещё два с половиной месяца никуда не убежит. Вообще, июнь у многих занятой месяц. А может правда кто в деревню уехал, без компа...

[Nataly-Mak]

Решила посмотреть на ортогональные ЛК 12-го порядка.
В моей статье построена группа из 5 попарно ортогональных ЛК 12-го порядка (по описанию в одной из книг).
Очень хорошая оказалась группа! Кажется, эти ОЛК дают группу из 60 уникальных перестановок.

Пока проверила только перестановки из первых двух квадратов.
Вот группа из 24 уникальных перестановок чисел 1,2,3,...,12:

1,2,3,4,5,6,7,8,9,10,11,12,
2,3,4,5,6,1,8,9,10,11,12,7,
3,4,5,6,1,2,9,10,11,12,7,8,
4,5,6,1,2,3,10,11,12,7,8,9,
5,6,1,2,3,4,11,12,7,8,9,10,
6,1,2,3,4,5,12,7,8,9,10,11,
7,8,9,10,11,12,1,2,3,4,5,6,
8,9,10,11,12,7,2,3,4,5,6,1,
9,10,11,12,7,8,3,4,5,6,1,2,
10,11,12,7,8,9,4,5,6,1,2,3,
11,12,7,8,9,10,5,6,1,2,3,4,
12,7,8,9,10,11,6,1,2,3,4,5,
1,7,9,3,8,2,10,12,5,11,6,4,
2,8,10,4,9,3,11,7,6,12,1,5,
3,9,11,5,10,4,12,8,1,7,2,6,
4,10,12,6,11,5,7,9,2,8,3,1,
5,11,7,1,12,6,8,10,3,9,4,2,
6,12,8,2,7,1,9,11,4,10,5,3,
7,1,3,9,2,8,4,6,11,5,12,10,
8,2,4,10,3,9,5,1,12,6,7,11,
9,3,5,11,4,10,6,2,7,1,8,12,
10,4,6,12,5,11,1,3,8,2,9,7,
11,5,1,7,6,12,2,4,9,3,10,8,
12,6,2,8,1,7,3,5,10,4,11,9

При этом перестановки выписывала по строкам ЛК.
Имеем прямоугольник 24х12 strong-12-colorable.
По лемме из него можно получить прямоугольник 24х144 12-colorable.
Я ограничилась квадратом 24х24:

1,2,3,4,5,6,7,8,9,10,11,12,2,3,4,5,6,7,8,9,10,11,12,1,
2,3,4,5,6,1,8,9,10,11,12,7,3,4,5,6,7,2,9,10,11,12,1,8,
3,4,5,6,1,2,9,10,11,12,7,8,4,5,6,7,2,3,10,11,12,1,8,9,
4,5,6,1,2,3,10,11,12,7,8,9,5,6,7,2,3,4,11,12,1,8,9,10,
5,6,1,2,3,4,11,12,7,8,9,10,6,7,2,3,4,5,12,1,8,9,10,11,
6,1,2,3,4,5,12,7,8,9,10,11,7,2,3,4,5,6,1,8,9,10,11,12,
7,8,9,10,11,12,1,2,3,4,5,6,8,9,10,11,12,1,2,3,4,5,6,7,
8,9,10,11,12,7,2,3,4,5,6,1,9,10,11,12,1,8,3,4,5,6,7,2,
9,10,11,12,7,8,3,4,5,6,1,2,10,11,12,1,8,9,4,5,6,7,2,3,
10,11,12,7,8,9,4,5,6,1,2,3,11,12,1,8,9,10,5,6,7,2,3,4,
11,12,7,8,9,10,5,6,1,2,3,4,12,1,8,9,10,11,6,7,2,3,4,5,
12,7,8,9,10,11,6,1,2,3,4,5,1,8,9,10,11,12,7,2,3,4,5,6,
1,7,9,3,8,2,10,12,5,11,6,4,2,8,10,4,9,3,11,1,6,12,7,5,
2,8,10,4,9,3,11,7,6,12,1,5,3,9,11,5,10,4,12,8,7,1,2,6,
3,9,11,5,10,4,12,8,1,7,2,6,4,10,12,6,11,5,1,9,2,8,3,7,
4,10,12,6,11,5,7,9,2,8,3,1,5,11,1,7,12,6,8,10,3,9,4,2,
5,11,7,1,12,6,8,10,3,9,4,2,6,12,8,2,1,7,9,11,4,10,5,3,
6,12,8,2,7,1,9,11,4,10,5,3,7,1,9,3,8,2,10,12,5,11,6,4,
7,1,3,9,2,8,4,6,11,5,12,10,8,2,4,10,3,9,5,7,12,6,1,11,
8,2,4,10,3,9,5,1,12,6,7,11,9,3,5,11,4,10,6,2,1,7,8,12,
9,3,5,11,4,10,6,2,7,1,8,12,10,4,6,12,5,11,7,3,8,2,9,1,
10,4,6,12,5,11,1,3,8,2,9,7,11,5,7,1,6,12,2,4,9,3,10,8,
11,5,1,7,6,12,2,4,9,3,10,8,12,6,2,8,7,1,3,5,10,4,11,9,
12,6,2,8,1,7,3,5,10,4,11,9,1,7,3,9,2,8,4,6,11,5,12,10

Проверила квадрат в программе Эда, всё нормально, квадрат 12-colorable.

Теперь рассуждаем: если из всех 5 попарно ортогональных ЛК получим набор из 60 уникальных перестановок, тогда добавим к этому набору 12 комбинаций из одинаковых чисел и получим прямоугольник 72х12 strong-12-colorable. Далее применяем к этому прямоугольнику лемму и получаем очень неплохой прямоугольник 72х144 12-colorable.
Ну, готовое решение тут пока будет: C=12, N=72x72.
Дальше надо пытаться применять алгоритм достраивания. Ничего пока не могу сказать об эффективности этого алгоритма в данном примере.

Однако, не исключено, что с этими ЛК ещё какой-нибудь финт можно проделать (без всякого достраивания). Тут надо крепко подумать. Уж очень хороший прямоугольник получается - 72х144, ровно половина квадрата 144х144.

А какая максимальная MOLS 12-го порядка известна на сегодня? Кто в курсе событий с ортогональными ЛК? Может быть, уже нашли группу из 10 попарно ортогональных ЛК? И все эти ЛК так же хороши, как те 5 ЛК, о которых я рассказала?
Тогда с построением решения C=12, N=132x132 вообще делать нечего

Да, кто владеет информацией, тот владеет миром (с).

Построение группы MOLS 12-го порядка я выполняла по описанию в книге М. Холл, "Комбинаторика", М.: Мир, 1970.
Цитата из этой книги:

Цитата:

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

Но это было написано так давно, более 40 лет назад!

[Nataly-Mak]

Интересную нашла страницу:
http://zealint.ru/monochromatic-squares-com.html

Zealint
а что же вы форум dxdy.ru проигнорировали в своём сообщении?

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

И ещё весьма любопытная страница:
http://www.recmath.org/contest/Squares/ ... sults.html

Какие-то monochromatic squares уже на конкурсе Зиммерманна строились