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

[Nataly-Mak]

Снимаю свой вопрос о перекраске раскрасок, а также об изоморфных раскрасках.

[dimkadimon]

Сегодня нашёл очень интересную статистику. Я взял решения C4N18 и проверил сколько будет ошибок если изменить одну клетку. Удивительно, но все 4 решения которые у меня были дали вот такую одинаковую статистику:

ошибки | количество решений
0 0
1 0
2 0
3 72
4 648
5 252

Почему все C4N18 дают одинаковую статистику? Может потому что они построены одинаковым методом? То что нет решений с одной и двумя ошибками плохая новость для метода отжига. Это значит что уменьшать количество ошибок отжигом не всегда гарантирует приближение к полному решению. Ещё получается что можно найти решение даже когда целых 5 ошибок.

А вот результаты для регулярных C5N25 (кстати нерегулярных я ещё не видел):
0 0
1 0
2 0
3 0
4 2500
5 0

[Nataly-Mak]

Наконец-то нарушено положение конкурсантов в десятке сильнейших, Тома вытеснили-таки:

Цитата:

9 Wes Sampson 19.710400 07-07-2012 @ 00:50:31
10 Sigi S 19.673800 08-07-2012 @ 23:12:32
11 Tom Sirgedas 19.638600 06-07-2012 @ 07:11:18
12 Il brigante Pennastorta 19.638600 06-08-2012 @ 16:28:33
13 Vladimir Chirkov 19.638600 07-10-2012 @ 15:04:16
14 Juha Saukkola 19.638600 07-31-2012 @ 11:06:51
15 Yirmy Yasovsky 19.568600 08-07-2012 @ 21:26:33

Немец Sigi S упорно идёт вперёд. Не отстаёт и Yirmy Yasovsky. Не исключено, что скоро он войдёт в группу с количеством баллов 19,6386. А может быть, поднимется и выше.
Россиянин Vladimir Chirkov совсем прекратил игру, почти месяц не обновляет результаты.
Впрочем, это характерно для многих участников. Ещё раз повторю: очень много для конкурса 3 месяца! Многие прекратили участие в июле и вряд ли возобновят активность.

Кто любит быстро бегать 100-метровку, давно её пробежал

[svb]

Nataly-Mak

Цитата:

Кто любит быстро бегать 100-метровку, давно её пробежал

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

[Pavlovsky]

Построим семейство латинских квадратов. Возьмем произвольный ЛК порядка C, назовем его базовым. Циклическим сдвигом цветов, из базового ЛК построим группу ЛК. Пронумеруем ЛК в порядке построения. Базовый ЛК будет под номером 1. Назовем эту группу ЛК унитарными.

Если С=p, где p – простое число. Тогда можно заполнить матрицу размером СxС унитарными ЛК . То есть построить квадрат С^2xC^2.

Алгоритм заполнения матрицы легко угадвыется на примере для С=11.



Легко убедится, что полученный квадрат эквивалентен квадрату построенному из сильноокрашенного прямоугольника, с последующей репликацией по лемме 4.3.

[svb]

Теорема
Пусть $L\left( {k,l} \right)$ - латинский квадрат, $G$ - поле из $c$ элементов с операциями $\otimes$ и $\oplus$, тогда
1. раскраска $R\left( {x,y,k,l} \right) = L\left( {x \otimes y \oplus k,l} \right)$ правильная;
2. раскраска $R\left( {x,y,k,l} \right) = L\left( {k \otimes l \oplus x,y} \right)$ правильная.
Эти две раскраски будем называть сопряженными: $R^* \left( {x,y,k,l} \right) = R\left( {k,l,x,y} \right)$.
Здесь $R$, как обычно, задает цвет точки $\left( {xc + k,yc + l} \right)$, где $x,y,k,l \in \left( {0,...,c - 1} \right)$.

В более общем случае можно рассматривать матрицы $R_ \times \left( {x,y} \right)$ и $R_ + \left( {x,y} \right)$ и раскраски
$\begin{array}{l} R\left( {x,y,k,l} \right) = L\left( {x,R_ + \left( {R_ \times \left( {k,l} \right),y} \right)} \right) \\ R\left( {x,y,k,l} \right) = L\left( {k,R_ + \left( {R_ \times \left( {x,y} \right),l} \right)} \right) \\ \end{array}$

Замечание
Раскраска прямоугольника $\left( {x,lc + y} \right)$ по формуле $R_ + \left( {R_ \times \left( {x,y} \right),l} \right)$ является сильной $c$-окраской.

От матриц $R_ +$ и $R_ \times $, вообще говоря, не требуется, чтобы они задавали поле. Пример, который я приводил выше, был получен путем нахождения перебором матрицы $R_ +$ по заданной матрице $R_ \times $.

-- Ср авг 08, 2012 17:52:22 --

Pavlovsky

Цитата:

Алгоритм заполнения матрицы легко угадывается на примере для С=11.

Для простых $C$, действительно, легко угадывается, но чуть сложнее для степеней простых.

[Nataly-Mak]

Возьмём 3-сильную раскраску 9х4:

1,1,1,1,
2,2,2,1,
3,3,3,1,
1,2,3,2,
2,3,1,2,
3,1,2,2,
1,3,2,3,
2,1,3,3,
3,2,1,3

и добавим к ней один цвет и две строки:

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

Получили 4-сильную раскраску 11х4. Этой раскраске соответствует набор из 4-х попарно ортогональных прямоугольников 3х4, в которых последняя строка неполная:

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

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

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

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

Вопрос:
можно ли найти недостающие элементы прямоугольников с сохранением всех имеющихся элементов и свойства попарной ортогональности?

По-другому этот вопрос звучит так: можно ли к приведённой выше 4-сильной раскраске 11х4 добавить ещё одну строку, не нарушая структуры исходной раскраски?

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

Точно так же выписала сегодня эксперимент с 9-сильной раскраской 81х10 (добавление к этой раскраске двух строк), то есть выписала все 10 попарно ортогональных прямоугольников 9х10, соответствующих 10-сильной раскраске 83х10. В этих прямоугольниках тоже последняя строка неполная (не хватает 7 элементов).

Картина весьма любопытная в этих прямоугольниках вырисовывается.
И аналогичные вопросы возникают. Возможно ли добавление хотя бы ещё одной строки к полученной 10-сильной раскраске 83х10? Тут уж даже не спрашиваю, возможно ли добавить строку без нарушения структуры исходной раскраски. Хотя бы с нарушением добавить!
Добавление одной строки добавит в прямоугольниках в последнюю строку ещё один элемент. Если затем добавить ещё один элемент, это будет эквивалентно добавлению ещё одной строки к 10-сильной раскраске 84х10. Если заполнить прямоугольники полностью, это будет эквивалентно получению 10-сильной раскраски 90х10 (или, что то же, получению решения C10N100).

Итак, найден комплект из 10 попарно ортгональных прямоугольников 9х10, от которого можно плясать.

Аналогичные комплекты попарно ортогональных прямоугольников найдены мной для 12-сильной, 14-сильной, 15-сильной, 18-сильной раскрасок. Не могу одолеть 20-сильную раскраску 363х20. Тут тупик у меня
Построила уже примерно полсотни 19-сильных раскрасок 361х20, ни к одной из них 2 строки не добавляются.

-- Ср авг 08, 2012 20:59:17 --

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

А вот результаты для регулярных C5N25 (кстати нерегулярных я ещё не видел):

svb выкладывал нерегулярное решение C5N25 тут

Моё решение тоже нельзя назвать регулярным. "Регулярность" в нём только от применения репликаций к нерегулярной 5-сильной раскраске.

[svb]

Nataly-Mak

Цитата:

svb выкладывал нерегулярное решение C5N25 тут

Как раз это решение было регулярным, т.к. были просто произведены случайные перестановки строк/столбцов, при которых свойства квадрата не изменяются. Оно просто выглядит нерегулярным.

По поводу матриц $R_ + $ и $R_ \times$. Приведу пример:

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

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

Матрица $R_ \times$ была задана, а $R_ + $ найдена перебором, она даже не является латинским квадратом, но обе раскраски по теореме получаются правильные .

[Nataly-Mak]

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

Простое случайное перемешивание регулярного квадрата:

А, прояснилось, что за "простое случайное перемешивание"
Выглядит нерегулярным, но получено из регулярного.

-- Чт авг 09, 2012 06:59:30 --

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

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

Матрица $R_ \times$ была задана, а $R_ + $ найдена перебором, она даже не является латинским квадратом, но обе раскраски по теореме получаются правильные .

Эта матрица является обобщённым латинским квадратом.
Да и первая матрица у вас не является классическим ЛК, т.к. содержит строку и столбец из одинаковых символов. Это тоже обобщённый ЛК. Классическим ЛК является подквадрат 7х7, содержащийся в этой матрице.

Когда мы составляем С-сильную раскраску из полного комплекта из С+1 попарно ортогональных ЛК порядка С, два из них тоже являются обобщёнными ЛК (квадраты из одинаковых строк и из одинаковых столбцов). Кстати, и классические ЛК - это частный случай обобщённых ЛК.

[Pavlovsky]

svb Хорошие теоремы. Ввиду отсутствия своих идей, в ближайшее время изучу ваши.

Сергей, может напишешь сюда:
http://infinitesearchspace.dyndns.org/c ... ic-squares

Вдруг у человека есть ценная информация, но нет повода ее опубликовать.

[Nataly-Mak]

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

Сергей, может напишешь сюда:
http://infinitesearchspace.dyndns.org/c ... ic-squares

Вдруг у человека есть ценная информация, но нет повода ее опубликовать.

Да, я тоже хотела это предложить.

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

[Nataly-Mak]

Выкладываю набор из 10 попарно ортогональных прямоугольников 9х10, соответствующий 10-сильной раскраске 83х10:

(Оффтоп)

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

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

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

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

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

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

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

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

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

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

Весьма любопытные прямоугольнички

Попарную ортогональность проверила по программе; правда, не для всех прямоугольников, только взаимную ортогональность всех следующих с первым и со вторым прямоугольником.

Обратите внимание на предпоследние и последние элементы (в последней строке) в прямоугольниках. Они соответствуют двум добавленным строкам в раскраске:

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

Понятно, что таких наборов существует очень много. Даже у меня их, как минимум, три.
Представленный набор соответствует раскраске 83х10, полученной из стандартной 9-сильной раскраски 81х10.
А есть ещё 10-сильная раскраска 83х10, полученная из 85-символьной строки Pavlovsky. И этой раскраске соответствует совсем другой набор из 10 попарно ортогональных прямоугольников 9х10 с неполной последней строкой.

Ну, и теперь простенькая задачка:

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

А ежели удалось бы заполнить эти прямоугольники полностью, это дало бы решение C10N100. Жар-птица!

И ещё такая простенькая задачка (для двоечницы в третьем классе ):

составить аналогичный набор из 20 попарно ортогональных прямоугольников 19х20 (с неполной последней строкой; не хватает 17 элементов), что будет соответствовать 20-сильной раскраске 363х20, которую я никак не могу получить

Первый прямоугольник 19х20 в этом наборе я бы составила так:

1 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12
12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13
13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14
14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16
16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17
17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18
18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19
19 1 20

Это по аналогии с первым прямоугольником 9х10.
Можно ещё в каждом 19х20 прямоугольнике записать два последних элемента в последней строке, это тоже по аналогии.
А вот дальше, увы, аналогия не катит

С добавлением двух строк к 9-сильной раскраске 81х10 метод отжига справляется в два счёта, а вот добавить две строки к 19-сильной раскраске 361х20, увы, не удаётся.

Добавляем одну строку 20,20,20,...,20, получаем 20-сильную раскраску 362х20. Этой раскраске соответствует набор из 20 попрарно ортогональных прямоугольников 19х20 с неполной последней строкой (не хватает 18 элементов). Теперь задача совсем простая: добавить в последнюю строку этих прямоугольников ещё один элемент. Даже знаем уже, как эти элементы добавить: 1,2,3,...,20. Так, замечательно. Но при добавлении этих элементов нарушится ортогональность прямоугольников. Вот теперь её надо восстановить. В этом вся сложность задачи! Восстанавливать ортогональность надо путём замены элементов внутри исходных прямоугольников на элемент 20.

Эх, если бы прямоугольников было не так много и были бы они не такие большие...
Программа нужна хорошая. Увы, я совсем разучилась программировать. Запутываюсь в циклах

[svb]

Pavlovsky

Цитата:

svb Хорошие теоремы.

Обычная попытка обобщения давно известных результатов. Вот сегодня под утро во сне вдруг лезет мысль: "А ведь про латинский квадрат $L\left( {x,y} \right)$ ты забыл, что это слишком сильное требование - достаточно потребовать, чтобы используемый индекс пробегая от $0$ до $c-1$ давал бы все значения от $0$ до $c-1$". И сразу за этой мысль о сильной $c$-окраске прямоугольника $\left( {x,lc + y} \right) $ вида $R_ + \left( {R_ \times \left( {x,y} \right),l} \right)$. Перемешивание цветов в любом маленьком квадратике не меняет "сильность".

Но , проснувшись, до меня доходит, что, если в маленьком квадратике имеется Г-обрамление, то цвет этого обрамления требует более аккуратного обращения

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

Перебор для $C=10$ проходит достаточно быстро, но результат отрицательный. Получается, что для полей можно находить самые разнообразные матрицы $R$, но все эти обобщения мало подходят для других случаев.

-- Чт авг 09, 2012 09:04:02 --

Nataly-Mak

Цитата:

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

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

[Nataly-Mak]

Да, на форуме вы можете писать, это понятно. Но вот ввести полученные результаты в БД не сможете, не являясь участником конкурса.

[svb]

Nataly-Mak

Цитата:

Да, на форуме вы можете писать, это понятно. Но вот ввести полученные результаты в БД не сможете, не являясь участником конкурса.

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

Вот получу C10N100 или, хотя бы, C21N400 - обязательно введу данные