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

[Pavlovsky]

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

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

Первый вариант таблицы я опубликовал вчера. Текущая таблица уже сильно отличается.

[Nataly-Mak]

Да, пока некоторая активность конкурсантов наблюдается
Хорошо бы она не снижалась, а возрастала.

[svb]

Пример сопряженного решения для поля GF(4):

    for i:=0 to n-1 do for j:=0 to n-1 do
    if not((i=0)and(j=0)) then
    for k:=0 to n-1 do for l:=0 to n-1 do
      s[i*n+k,j*n+l]:=s[k,p[l,sq[i,j]]];

Здесь $sq$ - таблица умножения, $p$ - таблица сложения. На пример для GF(9) уже страшно смотреть

[svb]

Пусть на множестве $G$ из $C$ элементов заданы две операции $\otimes$ и $\oplus$.
1. Относительно операции $\oplus$ множество $G$ является коммутативной группой.
2. Выполняется соотношение:
$i_1 \otimes j_1 \oplus i_2 \otimes j_2 \ne i_2 \otimes j_1 \oplus i_2 \otimes j_1$ при $\left( {i_1,j_1} \right) \ne \left( {i_2,j_2} \right)$

Вопрос. Возможно ли это для $C=10$ ?

[Pavlovsky]

А что за структура получится? Если взять декартово произведение конечных полей GF(2) и GF(5)?

[Nataly-Mak]

Раскраска 100х100 10-coloring без ошибок, но с дырками:



Заполнение цветами следующее:

NULL - 423
A - 956
B - 958
C - 959
D - 957
E - 959
F - 957
G - 959
H - 956
I - 957
J - 959

Раскраска получена из того квадрата 100х100 10-color с 790 ошибками, который я выложила выше.
Думаю, что количество ячеек с NULL можно уменьшить. У меня один вариант получался со 420 ячейками, заполненными NULL.
Я поздно сообразила, что заполнять символом NULL надо начинать с тех ячеек, которые дают большее количество ошибок. Уже в середине процесса мне вдруг попалась ячейка, которая дала 10 ошибок! Вставив в эту ячейку NULL, я сразу уничтожила 10 ошибок.

Итак, новый тип приближения: сделать раскраску 100х100 со всеми 10 залитыми цветами и с минимальным количеством ячеек, заполненных символом NULL.

Я пока склоняюсь к тому, что решение C10N100 существует.

[dimkadimon]

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

    for i:=0 to n-1 do for j:=0 to n-1 do
    if not((i=0)and(j=0)) then
    for k:=0 to n-1 do for l:=0 to n-1 do
      s[i*n+k,j*n+l]:=s[k,p[l,sq[i,j]]];

Здесь $sq$ - таблица умножения, $p$ - таблица сложения. На пример для GF(9) уже страшно смотреть

Хорошо можно сказать что p[a,b] = (a+b) mod n, a sq[a,b] = (ab) mod n? Еше не очень понимаю рекурсивную формулировку. Получается что s зависит от других найденых s?

[Pavlovsky]

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

Пусть на множестве $G$ из $C$ элементов заданы две операции $\otimes$ и $\oplus$.
1. Относительно операции $\oplus$ множество $G$ является коммутативной группой.
2. Выполняется соотношение:
$i_1 \otimes j_1 \oplus i_2 \otimes j_2 \ne i_2 \otimes j_1 \oplus i_2 \otimes j_1$ при $\left( {i_1,j_1} \right) \ne \left( {i_2,j_2} \right)$

Если нигде не ошибся, то у меня получается проще

Пусть на множестве $G$ из $C$ элементов заданы две операции $\otimes$ и $\oplus$. Это вроде как называется кольцом?!
1. Относительно операции $\oplus$ множество $G$ является коммутативной группой. 0 обозначим нулевой элемент группы.
2. Операция $\otimes$ должна обладать свойством: если $a \ne 0$ и $b \ne c$, тогда $a \otimes$ b \ne a \otimes$ c

Какие операции должны быть коммутативными или ассоциативными надо смотреть.

[svb]

Pavlovsky

Цитата:

Это вроде как называется кольцом?!

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

dimkadimon

Цитата:

Еше не очень понимаю рекурсивную формулировку.

Это не так. Просто у меня был предварительно заполнен квадратик $s[i,j]$ при $i<n$, $j<n$. Особых требований к этому заполнению нет - нет повторов цветов в строках и в столбцах (кажется, такие квадраты называются латинским).

[Pavlovsky]

Где то напутал в своих выкладках. Алгебра мутная наука. В ней нет очевидных вещей. Жизненный опыт мешает.

Quimey Vivas

Отправной точкой пусть будет функция вичисляющая цвет каждой ячейки нашего квадрата.

Цитата:

Take F the finite field with C elements labelled 1,...,C. Represent a point in the grid by a pair of pairs ((i,j),(k,l)) with i,j,k,l in F. Set the colour of the point ((i,j),(k,l)) equal to i*k+j+l (using the arithmetic of F).

Забудем про конечные поля. Возмем некоторую структуру с двумя операциями. И попробуем сформулировать минимально необходимые требования к ее операциям.

Цитата:

Suppose that there is a monochromatic rectangle with opposite vertices ((i,j),(k,l)) and ((a,b),(c,d)), then we must have:

i*k+j+l = i*c+j+d = a*c+b+d = a*k+b+l

Subtracting the second from the first we get:
i(k-c)=d-l

Doing the same with the last two we get:
d-l=a(k-c)

It follows that (i-a)*(c-k)=0 and since F is a field, we conclude i=a or c=k. It is easy to see, using the same idea, that in both cases the two points have to be aligned.

Эти преобразования должны быть правильными в нашей структуре. Так какими свойствами должны обладать операции * и +??

[svb]

dimkadimon

Цитата:

Хорошо можно сказать что p[a,b] = (a+b) mod n, a sq[a,b] = (ab) mod n?

для простых n это проходит, но уже для n=4 необходимо брать:

0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

[Pavlovsky]

Начну с элементарных вещей

Цитата:

i*k+j+l = i*c+j+d => i*k+l = i*c+d

Сокращение элемента это как называется в алгебре?

Цитата:

d-l

Должна существовать операция обратная операции сложения?!

Цитата:

i*(k-c)

Вынос за скобки это дистирибутивность??

-- Сб июл 28, 2012 15:03:33 --

Цитата:

(i-a)*(c-k)=0 and since F is a field, we conclude i=a or c=k.

Получается, что к операции умножения предъявляется жесткое условие.

Если a,b <>0, то a*b<>0. Боюсь, что такую таблицу умножения для С<>p^s не придумать.

[Nataly-Mak]

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

Думаю, что количество ячеек с NULL можно уменьшить. У меня один вариант получался со 420 ячейками, заполненными NULL.

Повторила процедуру хотя делаю эту вручную в программе Эда, но интересно.
Действительно, удалось уменьшить количество ячеек, заполненных символом NULL.
Вот распределение цветов в новой раскраске:

NULL - 391
A - 961
B - 960
C - 960
D - 960
E - 961
F - 961
G - 961
H - 961
I - 962
J - 962

Интересно, что цвета распределились очень равномерно.

У кого-нибудь есть лучшие приближения к решению C10N100?

Как уже сказала, приближения у меня двух типов:

1. залито всё, но в раскраске n-ое количество ошибок;
у меня это приближение содержит 790 ошибок

2. залиты все 10 цветов, но с дырками (дырки - ячейки, заполненные символом NULL);
у меня в этой раскраске 391 дырок.

Возможен ещё третий тип приближений. Это когда залито несколько цветов, причём залитые цвета не дают ошибок.
Приближение такого типа привёл Roland Postle на форуме конкурса для решения C5N26.
В его решении залиты 4 цвета, причём очень хорошо залиты: каждый цвет занимает 137 ячеек, и нет ни одной ошибки (это решение выложено выше).

У меня нет приближения такого типа для решения C10N100. Думаю, что построить его непросто. Даже заполнить квадрат 100х100 1000 единичками, чтобы они не давали ошибок, сложно. Я за это даже и не берусь.

[svb]

Pavlovsky
Вы следуете статье, в моей программе я выбрал аналогичный, но несколько иной вариант

    for i:=0 to n-1 do for j:=0 to n-1 do
    if not((i=0)and(j=0)) then
    for k:=0 to n-1 do for l:=0 to n-1 do
      s[i*n+k,j*n+l]:=p[s[k,l],p[i,(n-j)mod n]];

$s[i,j]$ при $i<n,j<n$ предварительно заполнен таблицей умножения. Дело в том, что в этом варианте не очень видна "свобода" (вместо $(n-j)\mod n$ можно выбрать,например, $j$), которая выступает в сопряженном варианте, повторю:

    for i:=0 to n-1 do for j:=0 to n-1 do
    if not((i=0)and(j=0)) then
    for k:=0 to n-1 do for l:=0 to n-1 do
      s[i*n+k,j*n+l]:=s[k,p[l,sq[i,j]]];

здесь выбор верхнего левого квадратика достаточно свободен (латинский квадрат).
Далее цепочка рассуждений:

 i1,j1,k1,l1     i1,j2,k1,l2
 i2,j1,k2,l1     i2,j2,k2,l2

 s[k1,p[l1,sq[i1,j1]]]    s[k1,p[l2,sq[i1,j2]]]
 s[k2,p[l1,sq[i2,j1]]]    s[k2,p[l2,sq[i2,j2]]]
если p[l1,sq[i1,j1]]=p[l2,sq[i1,j2]], то p[l1,sq[i2,j1]]<>p[l2,sq[i2,j2]]
т.е. можно положить
 p[l1,sq[i1,j1]]+p[l2,sq[i2,j2]]-p[l1,sq[i2,j1]]-p[l2,sq[i2,j2]]<>0
т.к. p-операция сложения, то есть ассоциативность и получаем:
 p[sq[i1,j1],sq[i2,j2]]]-p[sq[i2,j1],sq[i2,j2]]<>0

т.е. мы использовали ассоциативность и коммутативность сложения, а требование к умножению только одно.
Меня смущает одна вещь. При $C=6$ удается использовать только часть таблицы "умножения", а далее использовать Г-достраивание.

[Nataly-Mak]

Над регулярным решением C10N100 я тоже думала, давно уже.
Искала непересекающиеся комбинации чисел 1,2,3,...,10. Мне помогли в поиске таких комбинаций на другом форуме. Но нашли их почему-то только 50 штук.
Я так и не знаю, является ли это максимальным количеством для таких комбинаций.
Ну, понятно, что найденный набор непересекающихся комбинаций дал мне фактически 10-сильную раскраску 50х10. Из неё я получила очень гармоничный прямоугольник 50х100 10-coloring.
Всё это я уже рассказывала.
(но как я понимаю, тут мало кто интересуется чужими идеями, все сами с усами )
И прямоугольник 50х100 (ровно половина квадрата 100х100) я уже показывала.
Однако тогда ещё я не знала, что можно к этому прямоугольнику приписать ещё 10 строк.
Сейчас приписала, получился прямоугольник 60х100.
Выкладываю этот прямоугольник:



Очень красивое регулярное решение, жалко, что всего 60 строк.