2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 36, 37, 38, 39, 40, 41, 42 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 19:50 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky в сообщении #589852 писал(а):
Так красивее.
Возможно. А 100x100 получится? :-)

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 19:54 


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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 20:12 
Аватара пользователя


20/01/10
766
Нижний Новгород
Zealint в сообщении #589857 писал(а):
Обождите, а обычные диагональные квадраты уже не нравятся?
Для больших C у чисто диагональных квадратов шансов осуществить перебор практически нет. Г-образные конструкции дают нам конечные поля, но у нас нет полей для C отличных от степеней простых чисел. Требование же, быть полем, слишком сильное для нашей задачи. Чем его заменить? Другой вариант умножения?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 20:17 


26/01/10
959
svb в сообщении #589855 писал(а):
Возможно. А 100x100 получится? :-)

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

svb в сообщении #589865 писал(а):
Другой вариант умножения?

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 20:25 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 20:33 


26/01/10
959
svb в сообщении #589870 писал(а):
Для C=4 я попробовал вручную - один квадрат выпал из моих требований, но эти требования можно ослабить и оставить только диагональность внутри маленьких квадратов. Для C=6 можно попробовать перебор - если получится, то можно переходить к C=10.

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 20:51 
Аватара пользователя


20/01/10
766
Нижний Новгород
Zealint в сообщении #589874 писал(а):
Для C=4 вручную что пробовали?
Квадрат 16x16 я привел чуть выше.
Цитата:
Диагональность внутри маленьких квадратов - это и есть предложенные мной выше циклические сдвиги (внутри CxC подквадратов).
Конечно
Цитата:
Наверное, задачу можно переформулировать так: отыскать C^2 перестановок чисел от 1 до C так, чтобы, расположив единицы в маленьких квадратах в соответствии с этими перестановками, не было запрещенных прямоугольников во всем большом квадрате. Но что-то для 10 я конца этого перебора не дождался. Небольшой хитрый трюк может позволить уменьшить число необходимых перестановок до (C-1)^2, а может быть до (C-2)^2, но это мне уже не очевидно.
Разумно сохранять симметрию относительно главной диагонали большого квадрата, вариантов и так слишком много. Можно рассматривать "сильную диагональность", когда все маленькие квадраты одинаковы в своей диагонали - далеко не факт, что это невозможно, но перебор сильно сокращается. А можно и ослабить это требование - эксперименты покажут.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.06.2012, 21:39 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Zealint в сообщении #589867 писал(а):
100x100 в 16 цветов получается раскрасит мгновенно. В 15 уже почти минуту приходится ждать, а в 14 уже совсем долго, пока жду.

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

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

Изображение

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 05:18 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 по одной диагонали одинаково раскрашены. А есть ли решении с одинаковой раскраской всех подквадратов?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 05:58 


26/01/10
959
Nataly-Mak в сообщении #589895 писал(а):
Не поняла...
Вы о какой-то специальной раскраске говорите?

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 06:17 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #589855 писал(а):
Возможно. А 100x100 получится?

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 06:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот аналогичное решение 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 пока не нашлось.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 06:48 
Аватара пользователя


21/02/10
1594
Екатеринбург
Изображение

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 06:53 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

Изображение

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение28.06.2012, 07:14 
Аватара пользователя


21/02/10
1594
Екатеринбург
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 писал(а):
Очень захотелось вышить крестиком эту мозаику и повесить на стену


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 36, 37, 38, 39, 40, 41, 42 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Dmitriy40


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group