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

[svb]

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

Так красивее.

Возможно. А 100x100 получится?

[Zealint]

Обождите, а обычные диагональные квадраты уже не нравятся?

[svb]

Zealint в сообщении #589857 писал(а):

Обождите, а обычные диагональные квадраты уже не нравятся?

Для больших C у чисто диагональных квадратов шансов осуществить перебор практически нет. Г-образные конструкции дают нам конечные поля, но у нас нет полей для C отличных от степеней простых чисел. Требование же, быть полем, слишком сильное для нашей задачи. Чем его заменить? Другой вариант умножения?

[Zealint]

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

Возможно. А 100x100 получится?

100x100 в 16 цветов получается раскрасит мгновенно. В 15 уже почти минуту приходится ждать, а в 14 уже совсем долго, пока жду.

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

Другой вариант умножения?

Может вместо таблицы умножения выбрать какие-то хитрые перестановки? Я так сделал для C=5, 25x25. Среди всех перестановок там я брал только циклические.

[svb]

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

[Zealint]

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

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

Ничего не понял...
Для C=4 вручную что пробовали?
Диагональность внутри маленьких квадратов - это и есть предложенные мной выше циклические сдвиги (внутри CxC подквадратов).

Наверное, задачу можно переформулировать так: отыскать C^2 перестановок чисел от 1 до C так, чтобы, расположив единицы в маленьких квадратах в соответствии с этими перестановками, не было запрещенных прямоугольников во всем большом квадрате. Но что-то для 10 я конца этого перебора не дождался. Небольшой хитрый трюк может позволить уменьшить число необходимых перестановок до (C-1)^2, а может быть до (C-2)^2, но это мне уже не очевидно.

[svb]

Zealint в сообщении #589874 писал(а):

Для C=4 вручную что пробовали?

Квадрат 16x16 я привел чуть выше.

Цитата:

Диагональность внутри маленьких квадратов - это и есть предложенные мной выше циклические сдвиги (внутри CxC подквадратов).

Конечно

Цитата:

Наверное, задачу можно переформулировать так: отыскать C^2 перестановок чисел от 1 до C так, чтобы, расположив единицы в маленьких квадратах в соответствии с этими перестановками, не было запрещенных прямоугольников во всем большом квадрате. Но что-то для 10 я конца этого перебора не дождался. Небольшой хитрый трюк может позволить уменьшить число необходимых перестановок до (C-1)^2, а может быть до (C-2)^2, но это мне уже не очевидно.

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

[Nataly-Mak]

Zealint в сообщении #589867 писал(а):

100x100 в 16 цветов получается раскрасит мгновенно. В 15 уже почти минуту приходится ждать, а в 14 уже совсем долго, пока жду.

Не поняла...
Вы о какой-то специальной раскраске говорите?

Вот квадрат 100х100, раскрашенный в 11 цветов:

[Nataly-Mak]

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

Продолжение диагональной темы:

(Оффтоп)

A,A,A,A,B,B,B,B,C,C,C,C,D,D,D,D,
A,B,C,D,B,C,D,A,C,D,B,A,D,B,C,A,
A,C,D,B,B,D,A,C,C,B,A,D,D,C,A,B,
A,D,B,C,B,A,C,D,C,A,D,B,D,A,B,C,
B,B,B,B,C,C,C,C,D,D,D,D,A,A,A,A,
B,C,D,A,C,A,B,D,D,B,C,A,A,B,C,D,
B,D,A,C,C,B,D,A,D,C,A,B,A,C,D,B,
B,A,C,D,C,D,A,B,D,A,B,C,A,D,B,C,
C,C,C,C,D,D,D,D,A,A,A,A,B,B,B,B,
C,D,B,A,D,B,C,A,A,B,C,D,B,C,A,D,
C,B,A,D,D,C,A,B,A,C,D,B,B,A,D,C,
C,A,D,B,D,A,B,C,A,D,B,C,B,D,C,A,
D,D,D,D,A,A,A,A,B,B,B,B,C,C,C,C,
D,B,C,A,A,B,C,D,B,C,A,D,C,D,B,A,
D,C,A,B,A,C,D,B,B,A,D,C,C,B,A,D,
D,A,B,C,A,D,B,C,B,D,C,A,C,A,D,B

Посмотрела на аналогичное решение C=5, N=25x25 (кстати, построено методом, описанным Pavlovsky в самом начле темы - теорема 4.12 для С простых).
В этом решении все подквадраты 5х5 по одной диагонали (главной или разломанной) одинаково раскрашены. Красиво получается!
Итак, для С простых такие решения строятся элементарно.
А для степеней простых?

Тут svb привёл подобное решение для C=4.
В этом решении уже не все подквадраты 4х4 по одной диагонали одинаково раскрашены. А есть ли решении с одинаковой раскраской всех подквадратов?

[Zealint]

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

Не поняла...
Вы о какой-то специальной раскраске говорите?

Говорю о чисто диагональной.

[Pavlovsky]

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

Возможно. А 100x100 получится?

Твоя подсказка натолкнула на некоторые идеи. Надо пробовать.

[Nataly-Mak]

Вот аналогичное решение C=4, N=16x16, построенное по теореме 4.12:



В этом решении в каждой диагонали по два одинаково раскрашенных подквадрата 4х4.
Аналогичное решение можно построить для всех C, являющихся степенью простого числа.

Наверное, подобного решения с одинаково раскрашенными подквадратами 4х4 на каждой диагонали не существует

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

16,16,A,A,A,A,B,B,B,B,C,C,C,C,D,D,D,D,A,D,C,B,B,A,D,C,C,B,A,D,D,C,B,A,A,B,D,C,B,C,A,D,C,D,B
,A,D,A,C,B,A,C,B,D,B,D,C,A,C,A,D,B,D,B,A,C,B,B,B,B,C,C,C,C,D,D,D,D,A,A,A,A,B,C,D,A,C,D,A,B,
D,A,B,C,A,B,C,D,B,A,C,D,C,B,D,A,D,C,A,B,A,D,B,C,B,D,A,C,C,A,B,D,D,B,C,A,A,C,D,B,C,C,C,C,D,D
,D,D,A,A,A,A,B,B,B,B,C,B,A,D,D,C,B,A,A,D,C,B,B,A,D,C,C,D,B,A,D,A,C,B,A,B,D,C,B,C,A,D,C,A,D,
B,D,B,A,C,A,C,B,D,B,D,C,A,D,D,D,D,A,A,A,A,B,B,B,B,C,C,C,C,D,A,B,C,A,B,C,D,B,C,D,A,C,D,A,B,D
,C,A,B,A,D,B,C,B,A,C,D,C,B,D,A,D,B,C,A,A,C,D,B,B,D,A,C,C,A,B,D

-- Чт июн 28, 2012 07:36:43 --

Zealint в сообщении #589945 писал(а):

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

Не поняла...
Вы о какой-то специальной раскраске говорите?

Говорю о чисто диагональной.

Ага...
То есть диагональные решения C=16, N=100x100 и C=15, N=100x100 строятся элементарно (по вашей программе). А диагональное решение C=14, N=100x100 пока не нашлось.

[Pavlovsky]

Г-образные решения не менее красивые диагональных.

[Nataly-Mak]

Может быть, сама логика построения красивая (я её не знаю).
Но особой красоты на картинке не вижу.
То, что показал svb, гармоничнее.

Обалденно красивая мозаика в аналогичном решении C=11, N=121x121.
Все подквадраты 11х11 на каждой диагонали одинаково раскрашены.

-- Чт июн 28, 2012 08:10:32 --

Не удержусь, покажу



Очень захотелось вышить крестиком эту мозаику и повесить на стену

Как когда-то вышивали ковёр Паркера по найденной им первой паре ортогональных ЛК 10-го порядка. Красивый ковёр! Я его в какой-то статье показывала.

[Pavlovsky]

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

Может быть, сама логика построения красивая (я её не знаю).Но особой красоты на картинке не вижу.То, что показал svb, гармоничнее.

Квадрат, который я показал, это квадрат Сергея. Просто переставлены строки и столбцы, чтобы был виден Г-крюк.
Квадрат обладает замечательными свойствами. Латинский квадрат 4х4 в верхнем левом углу определяет цветовую гамму латинских квадратов 3х3, находящихся под Г-крюком. Получается 4 ЛК по 4 штуки с одинаковой цветовой гаммой. Забавно. В решении 2 из 4-х групп представлены одним квадратом. А оставшиеся две группы представлены двумя видами ЛК полученных циклическим сдвигом.

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

Г-образные конструкции дают нам конечные поля, но у нас нет полей для C отличных от степеней простых чисел.

Примерно так я получил решение 36х36 для С=6. После ряда допущений, мне осталось перебором заполнить квадрат 4х4, обладающий специальными свойствами, 5-ю различными символами. Для С<=7 мне это удалось. Увы для С>7 такое построение оказалось невозможным. Почему? Не знаю. Может подсказка Сергея поможет продвинуться дальше.

-- Чт июн 28, 2012 09:19:39 --

alexBlack в сообщении #589166 писал(а):

По крайней мере для одного вида решений для простых C очевидно, что при добавлении одного цвета можно увеличить размер на (C+1). Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу.

Что то процедура С+1+1 уж очень не очевидна. Второй день бьюсь, подвижки есть, результата нет.

-- Чт июн 28, 2012 09:44:59 --

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

Очень захотелось вышить крестиком эту мозаику и повесить на стену

Мозаика действительно забавная. Явно видны круги различных радиусов. Интересно их обосновать с точки зрения математики.