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

Nataly-Mak · 12.09.2012, 09:21

whitefox
спасибо большое за таблицы сложения и умножения в конечно поле GF(4); по вашим таблицам у меня раскраска C4N16 получилась правильная:

-- Ср сен 12, 2012 10:24:35 --

Herbert Kociemba
вы уверены, что построенные таким образом таблицы сложения и умножения правильные?

Herbert Kociemba в сообщении #617651 писал(а):

The addition table is the usual addition mod 4.

The multiplication table:

. | 0 1 2 3
---------------
0 | 0 0 0 0
1 | 0 3 1 2
2 | 0 1 2 3
3 | 0 2 3 1

У меня с такими таблицами решение C4N16 не получилось, 48 ошибок в решении.

-- Ср сен 12, 2012 10:26:20 --

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

У меня есть 10-strong 90x10 с 74 ошибками...

Вы уже ближе к жар-птице :wink:

Herbert Kociemba · 12.09.2012, 12:32

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

вы уверены, что построенные таким образом таблицы сложения и умножения правильные?

Sorry, the addition table is not just addition mod 4. I hope it is correct now. The identity element concerning addition is 0, the identitiy concerning multiplication is 2.

. | 0 1 2 3
---------------
0 | 0 0 0 0
1 | 0 3 1 2
2 | 0 1 2 3
3 | 0 2 3 1

+|0 1 2 3
-------------
0| 0 1 2 3
1| 1 0 3 2
2| 2 3 0 1
3| 3 2 1 0

Nataly-Mak · 12.09.2012, 13:07

Herbert Kociemba в сообщении #617811 писал(а):

I hope it is correct now.

Да, теперь решение получилось.

Код:

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

Спасибо.

Pavlovsky · 12.09.2012, 14:19

Немного систематизировал группу "алгебраических" алгоритмов.
Начну с алгоритма описанного Quimey Vivas.

Пусть ячейка таблицы C^2xC^2 имеет номер строки и колонки (x,y). Нумерация строк и колонок начинается с нуля. Координаты каждой ячейки запишем 4-мя числами. Тогда x=Kx*C+Lx (Lx<C), y=Ky*C+Ly (Ly<C). Цвет ячейки можно задавать различными способами, формулой вида F(x,y)=i*k+j+l. Операции * и + это операции конечного поля из С элементов. Решения, полученные различными вариантами формулы, будем называть сопряженными.
1) F(x,y)=Kx*Ky+Lx+Ly.
2) F(x,y)=Lx*Ly+Kx+Ky.
3) F(x,y)=Ly*Kx+Ky+Lx.
4) F(x,y)=Lx*Ky+Kx+Ly.

Простейший алгортим, предложенный dimkadimon.

Цитата:

Для C=p, есть совсем простой метод: F(s,u)=floor(s/C)+floor(u/C)+s*u)%C

Естественно входит в эту группу алгоритмов.

Утверждение. Все варианты формул задают эквивалентные квадраты, с точностью до перестановки строк и колонок.

Утверждение. F(x,y)=Lx*Ly+Kx+Ky и F(x,y)=Lx*Ky+Kx+Ly эквивалентны построению сильноокрашенного прямоугольника с последующей репликацией по лемме 4.3.

Утверждение. К сильноокрашенным прямоугольникам, полученным по этим формулам можно добавить еще одну колонку.

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

В этом случае корректные решения можно получать как по формуле F(x,y)=Kx*Ky+Lx+Ly, так и по формуле F(x,y)=Ky*Kx+Lx+Ly.

Естественно метод унитарных наборов ЛК, тоже описывается выше привденными формулами.

Немного отличается подход Сергея Беляева. У него две различные операции сложения.
По Беляеву формула выглядит так: F(x,y)=(Kx*Ky)!(Lx+Ly).
Пока не удалось найти преобразование, демонстрирующее, что одна операция сложения лишняя.

Nataly-Mak · 13.09.2012, 06:28

Продолжаю эксперименты.
Для решения C4N16 в матричном методе меняю местами таблицы сложения и умножения.

Теперь базовая матрица – бывшая таблица сложения:

Код:

Первый исходный блок – бывшая таблица умножения:

Код:

Следующие три блока – в каждой ячейке "плюс один":

Код:

Получилось решение:

(Оффтоп)

По-моему, это не изоморфно раскраске, полученной классическим методом. Сейчас поищу её и покажу.

Для простых С замена базовой матрицы на таблицу сложения проходит вроде всегда (пробовала для С=5, С=7).
Для С=8 пробовала, что-то не получилось, может быть, ошиблась.

Вот нашла классическую раскраску:

Сравните! По-моему, эти две раскраски (данная и показанная чуть выше) не изоморфны.

А есть у меня и ещё одна раскраска C4N16, построенная матричным методом (она выложена выше), я построила её без таблиц сложения и умножения (которых тогда ещё не знала); блоки построила циклическим сдвигом, а базовую матрицу нашла просто подбором в программе Эда.
И эта раскраска тоже, как мне кажется, совсем другая. Впрочем, я не сильна в изоморфизме раскрасок

Чтобы не ходить далеко за третьей раскраской, покажу и её:

(Оффтоп)

Итого 4 решения:

1. построено матричным методом по таблицам сложения и умножения в GF(4);
2. построено матричным методом с заменой базовой матрицы на таблицу сложения;
3. классическое решение:
4. построено матричным методом без таблиц сложения и умножения.

Все 4 решения тут показаны.
Так как насчёт изоморфизма этих 4 решений?

Да, замечу, что два решения, построенные по таблицам сложения и умножения, приведённым whitefox и Herbert Kociemba, очевидно изоморфны.

Nataly-Mak · 13.09.2012, 10:22

Итак, товарищи уважаемые форумчане!
Кто хочет поймать жар-птицу?
Конкурс закончился, но... конкурс продолжается!
Вы можете найти новые рекорды и ввести их в БД конкурса.
Таблицу рекордов, найденных во время официальной части конкурса, я выкладывала выше.

Если вы не смогли по каким-то причинам принять участие в конкурсе, так ещё не поздно.
Подключайтесь!

Сейчас намного проще, так как выложены все алгоритмы, все идеи - реализованные и не реализованные.

Вот dimkadimon уже установил новый рекорд - решение C15N198.

Да, так я начала о жар-птице :roll:

Жар-птица - это решение C10N100.
Многие пытались найти это решение, но пока, увы, безуспешно.

Сейчас есть, по крайней мере, три направления поиска этого решения:

1. не строго диагональное решение;
2. матричный метод;
3. поиск 10-сильной раскраски 90х10.

Ни один из этих методов нельзя отвергнуть окончательно, ибо не доказано, что метод точно не ведёт к искомому результату.

Вот, к примеру, метод 3.
Мной найдены 10 попарно ортогональных прямоугольников 9х10 с "дырками" и с неполной последней строкой.
Полный комплект был показан выше, здесь покажу два первых прямоугольника для наглядности:

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

Поставьте вместо "крестиков" любые числа от 1 до 10 и попарная ортогональность прямоугольников нарушится!

Теперь перед нами задача:
заполнить не только "дырки", но и все остальные ячейки в неполных последних строках числами от 1 до 10 так, чтобы получить комплект из 10 полных (в смысле - заполненных до конца) попарно ортогональных прямоугольников 9х10.

Это всё, что требуется. Если такой комплект попарно ортогональных прямоугольников будет найден, жар-птица уже никуда от нас не денется

Замечу (важно!): разрешается как угодно изменять уже имеющиеся числа в прямоугольниках, разумеется, только на числа от 1 до 10.

-- Чт сен 13, 2012 11:46:13 --

whitefox в сообщении #617148 писал(а):

В частности, если существуют две подгруппы порядка 10 симметрической группы $\mathrm{S_{10}}$ такие, что для любого не единичного элемента $i$ первой подгруппы и любого не единичного элемента $j$ второй подгруппы их коммутатор $iji^{-1}j^{-1}$ является беспорядком, то существует решение C10N100 и легко строится по этим подгруппам.

Это направление №2 - матричный метод, а точнее - его расширение.

whitefox
а можно пожелание? :wink:

Вот у вас есть некая идея. Возможно, идея очень хорошая и эффективная.
(к сожалению, я пока в этой идее ничего не понимаю, возможно, и не "пока", а вообще не пойму)
Как я понимаю, ваша идея есть расширение матричного метода.
А нельзя ли показать работоспособность вашей идеи на конкретном примере, скажем, для С=6.
Мы знаем, что матричный метод для С=6 работает. В таком случае должен работать и ваш метод, который представляет собой расширение матричного метода. Правильно рассуждаю?
Вот и проверьте свою идею на более низком порядке, нежели порядок 10.
Найдите эти самые два множества перестановок порядка 6 с нужными свойствами и покажите их нам, а также построенное с их помощью решение C6N36.

[заодно и идея ваша, может быть, станет более понятной для ёжиков

]

При исследовании методов построения магических квадратов я всегда начинала с маленьких порядков, чтобы убедиться в работоспособности метода. А уже потом начинала строить МК больших порядков, что ведь гораздо сложнее.

-- Чт сен 13, 2012 12:11:22 --

К примеру, демонстрирую работоспособность идеи №3 для С=6.

Это 6-сильно раскрашенный прямоугольник 30х6:

(Оффтоп)

Код:

А это 6 попарно ортогональных прямоугольников 5х6, соответствующих этой 6-сильной раскраске:

(Оффтоп)

Код:

Разумеется, из того, что метод работает для С=6, не следует автоматически, что он работает и для С=10.

Nataly-Mak · 13.09.2012, 11:31

Но! Метод работает для С=10 частично, а именно: найдена 10-сильная раскраска 83х10, которой соответствует полный комплект из 10 попарно ортогональных прямоугольников 9х10 с неполной последней строкой (присутствуют только три элемента).
И такой 10-сильный прямоугольник найден не один, их найдено много.
А вот на 10-сильной раскраске 84х10 всё застопорилось! То ли она не существует, то ли найти её мы пока ещё не умеем.
В идеале нам нужна 10-сильная раскраска 90х10 (для получения решения C10N100).

Ещё раз напомню файл, в котором приведены материалы по данной идее:
http://www.natalimak1.narod.ru/ORT9X10.doc

-- Чт сен 13, 2012 13:13:01 --

Цитата:

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

Код:

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

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

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

Это весьма интересный пример!
Я уже отмечала, что в данном примере задана базовая матрица Rx, а вот матрица, определяющая, как строить исходные блоки (R+), была найдена перебором.
В самом первом своём примере по данному методу Pavlovsky показал нам поиск базовой матрицы, если известны исходные блоки (он строил их циклическим сдвигом).
Здесь есть над чем подумать!

Что проще: искать базовую матрицу по заданным исходным блокам или, может, наоборот: искать исходные блоки по заданной базовой матрице?

Давайте зададим базовую матрицу Rx по аналогии с примером svb:

Код:

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

А теперь будем искать исходные блоки (10 штук), которыми потом заполним эту базовую матрицу. Матрица R+ в примере svb - это свёртка блоков, то есть каждая строка этой матрицы полностью определяет один из блоков позицией цвета 0 в строках этого блока.
Разрешимая ли задача? А почему нет?

Nataly-Mak · 13.09.2012, 12:43

Мне очень нравится ЛК Лямзина:

Красивый, уникальный ЛК! Диагональная симметрия.

Попробовать взять этот ЛК в качестве блока №1. А дальше в каждой ячейке плюс 1, например. Получить 10 блоков и искать для них базовую матрицу.

Nataly-Mak · 13.09.2012, 14:42

Даю два набора блоков.
Первый набор, когда блок №1 - ЛК Лямзина, а дальше блоки получаются прибавлением в каждой ячейке предыдущего блока единицы.

(Оффтоп)

Код:

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

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

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

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

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

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

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

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

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

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

А теперь смотрим на ЛК Лямзина как на свёртку блоков. Получаем второй набор блоков:

(Оффтоп)

Код:

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

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

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

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

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

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

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

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

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

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

В обоих наборах блоки являются классическими латинскими квадратами, весьма строго и красиво составленными, как и исходный классический ЛК Лямзина.

Ну, а теперь вперёд! Ищем для каждого из этих наборов блоков базовую матрицу :wink:

Для получения решения C10N100 нам нужна базовая матрица 9х9.

Nataly-Mak · 13.09.2012, 16:35

Беру второй набор блоков и начинаю заполнять базовую матрицу 9х9 (которой у меня пока нет) прямо в программе Эда.
Вот что получается:

(Оффтоп)

Дальше не экспериментирую, но... кто сказал, что это невозможно сделать??

Чтобы было понятнее: заполнена такая часть базовой матрицы 9x9:

Код:

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

Первая строка и первый столбец в базовой матрице у нас всегда состоят из единиц. Вторая строка и второй столбец выбраны наобум.
Остаётся подматрица 7х7. И жар-птица совсем близко :wink:

Но, похоже, ловить её никто не желает

Nataly-Mak · 13.09.2012, 18:31

Чтобы вскм было понятно, откуда возьмутся ещё 10 строк и 10 столбцов, покажу обрамление:

(Оффтоп)

Теперь почти готов квадрат 100х100, осталась самая малость

Напомню: alexBlack в своей статье утверждает, что полным перебором для С=10 найдена максимальная базовая матрица 8х8.
Но! Как я поняла (если неправильно поняла, пусть alexBlack поправит), он сделал полный перебор для блоков, которые строятся циклическим сдвигом.
Значит ли это, что не существует базовой матрицы 9х9 ни для каких других блоков :?:

Nataly-Mak · 14.09.2012, 07:52

Цитата:

In the attachment you see incomplete solution C5N26.
This is a strictly diagonal solution.
I can not find the solution.
Maybe it does not exist?

Not strictly diagonal C5N26 solution can be built?
Such a decision broken diagonals are colored in two colors.
For example, you can see in the attachment is not strictly diagonal solution C5N23.

Does anyone know a solution to this problem?

Это написала на форуме конкурса.
Перевод нужен?

dimkadimon
очень давно вы писали, что построить диагональное решение C5N26 у вас не получилось.
Не могли бы вы подробнее рассказать, что значит "не получилось"?
Вы сделали полный перебор? Уверены, что не существует никакого диагонального решения C5N26 (строго и не строго)?

О несуществовании строго диагонального решения C5N26 вроде писал svb.

-- Пт сен 14, 2012 09:20:10 --

Вот нашла сообщение svb:

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

Увы, если ломать диагонали - а именно для этого случая я делал перебор - то 25 это максимум. Если же их не ломать, то ситуация с перебором, боюсь, выскочит за пределы возможного :-(

Да, перебор для N=26 будет большим.
Может быть, как-то оптимизировать?
Или разбить программу на части по переменной внешнего цикла.

Nataly-Mak · 14.09.2012, 11:07

Вот нашла и сообщение dimkadimon:

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

Наконец нашёл диагональное решение 36х36 для 6 цветов. Красивое решение, но к сожалению совершенно не помогает найти 37х37. Так же не получилось найти диагональное решение 26х26 для 5 цветов, хотя 25х25 нахожу за минуту. Возможно диагональные решения не существуют для 17х17, 26х26 и 37х37. Сейчас попробую найти 49х49 для 7 цветов.

Программа whitefox выдаёт строго диагональное решение C5N25 мгновенно (доля секунды!).

А существует ли не строго диагональное решение C5N25?
Программа работает до первого найденного решения.

Программа svb выдаёт все строго диагональные решения, а не строго диагональные опять же не ищет.

Herbert Kociemba · 14.09.2012, 15:52

Strictly diagonal solutions for CXN (X^2+1) cannot exist.
At least one color must be a difference set of size X+1. All differences have to be different mod (X^2+1). But in a difference set of size X+1 there are (X+1)*X differences, which is more than X^2+1. So some differences are the same.

Nataly-Mak · 15.09.2012, 03:59

Herbert Kociemba в сообщении #618700 писал(а):

Strictly diagonal solutions for CXN (X^2+1) cannot exist.

Спасибо за разъяснения.
Я интуитивно предполагала, что строго диагональных решений для $N=C^2+1$ не существует.

А что вы можете сказать по поводу не строго диагональных решений:

1. для $N=C^2$ ;
2. для $N>C^2$ .

Я не могу найти не строго диагональные решения C3N9, C4N16, C5N25 и т.д.
Так же пока ничего не могу выяснить о существовании не строго диагонального решения C5N26.

Это не строго диагональное решение C2N4:

-- Сб сен 15, 2012 05:22:35 --

Вчера заглянула на форум ПЕН.
Нашла вот это сообщение svb:

Цитата:

Конкурс Monochromatic Squares закончился, но вопросы остались. Здесь приведены некоторые интересные пути, которые хотелось бы пройти до конца.

(Оффтоп)

Уважаемый Сергей! Понимаете, какая фишка: на форуме ПЕН без меня некому поддерживать "трёп" (по вашему меткому выражению :-)

).
И потому тема о конкурсе постепенно заглохла. Так что, прекращайте ходить в обиженных и пишите здесь, если вам действительно интересна задача и вы хотите продолжить её решение.

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

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