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

[Nataly-Mak]

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

С это простое число в степени плюс один. p простое число, а k любая степень. Для p=3 получаем N=3^2+3+1=13.

Ещё раз: у вас написано:
C=p^k+1.
Понятно, что p - простое число. Пусть p=3.
Что здесь k?
Что значит "k любая степень"? Это как?

Вот если k=1, то да, получаем: С=4, N=13.

А если k=2. Это значит: С=3^2+1=10.
Тогда что получаем по вашей формуле для N? В вашей формуле для N вообще нет k. И это неправильно.

[Nataly-Mak]

И вот оно - ещё одно оригинальное решение для С=8. Это диагональное решение С8N57, построенное по алгоритму Герберта.
CDS (57,8,1) 1,2,7,16,23,27,46,56.



Интересно распределение цветов в этом решении, цвет А занимает 456 ячеек, все остальные цвета по 399 ячеек.

Это максимальное диагональное решение для С=8?

[Zealint]

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

Я высказала гипотезу, что 10-сильная раскраска 84х10 не существует.

Вы ничего не путаете? Точно 84?

[Nataly-Mak]

Я ничего не путаю.
Гипотеза выложена в теме с подробным описанием и наглядными примерами (моя попытка построить такую раскраску и соответствующий ей набор из 10 латинских прямоугольников 9х10 с неполной последней строкой и с 20 пустыми ячейками).

У вас есть опровержение гипотезы, то бишь 10-сильная раскраска 84х10?
Просто скажите: да или нет. Раскраску, естественно, покажете после окончания конкурса.

Интересно, что никто ничего не ответил по поводу моей гипотезы на форуме конкурса. Меня не поняли?

[Zealint]

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

У вас есть опровержение гипотезы, то бишь 10-сильная раскраска 84х10?

Не помню уже... Но мне показалось, что я такую строил. Оказалась ненужной.

[Nataly-Mak]

Так показалось или строили?

[Zealint]

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

Так показалось или строили?

Точно строил, но не помню, докуда достроил. Так что ладно... фиг с ней.

[dimkadimon]

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

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

С это простое число в степени плюс один. p простое число, а k любая степень. Для p=3 получаем N=3^2+3+1=13.

Ещё раз: у вас написано:
C=p^k+1.
Понятно, что p - простое число. Пусть p=3.
Что здесь k?
Что значит "k любая степень"? Это как?

Вот если k=1, то да, получаем: С=4, N=13.

А если k=2. Это значит: С=3^2+1=10.
Тогда что получаем по вашей формуле для N? В вашей формуле для N вообще нет k. И это неправильно.

N=C^2-C+1 = (p^k+1)^2-(p^k+1)+1

[Nataly-Mak]

Теперь правильно.
И это решения 1-го класса:

C=6, N=31
C=10, N=91

и т.д.

---

Очень давно, когда занималась пандиагональными магическими квадратами, один коллега признался, что не понимает разломанные диагонали.
Поместила в Википедию свою примитивную картинку, интерпретирующую разломанные диагонали. Картинка там прижилась

Нечто аналогичное мы видим в диагональных решениях с правильным циклическим сдвигом:



Это решение C3N7, построенное по алгоритму Герберта, подробно описал построение dimkadimon чуть выше.

Удивительно! У Герберта решение полностью определяется CDS; в данном случае это (1,2,4), то есть расположение только первого цвета А в первой строке.

[Nataly-Mak]

Ещё одно решение, построено по алгоритму Герберта, C4N13.
CDS (1,2,4,10).



Для сравнения покажу своё диагональное решение C4N13 с неправильным циклическим сдвигом:

[Nataly-Mak]

А это диагональное решение из Интернета C4N16, правильный циклический сдвиг:



Тут можно сделать проще алгоритм, чем поиск характеристической строки длиной 16
Что-то аналогичное CDS...

По алгоритму Герберта строятся диагональные решения C5N21, C6N31. А как просто построить диагональные решения C5N25, C6N36?

Ещё раз подчеркну: речь идёт о диагональных решениях с правильным циклическим сдвигом.

Соответственно для С=3, по алгоритму Герберта строится диагональное решение C3N7 (показано выше), а svb привёл диагональное решение C3N9:

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

-- Вс авг 26, 2012 08:20:19 --

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

По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1, точно не знаю какой ето класс. Немного изменив метод можно получить и лучше, например C5N25 и C6N36.

Вы уже знаете, как модифицировать метод Герберта?
Очень интересно! Будем ждать рассказ об этом.

Хотя... вы уже кое-что рассказали:

Цитата:

Зато обнаружил что можно немного уменьшить требования CDS - можно искать цепочки где каждая разница встречается 0 или 1 раз. То есть какие то разницы вообще не встречаются. В этом случае, правда, для других цветов надо находить отдельные цепочки (которые отличны) от первой. Таким образом я теперь очень быстро могу находить диагональные решения C5N25 и C6N36, а вот для C>=10 никакого прогресса.

Но я пока ничего не поняла

[Nataly-Mak]

Начала вышивать крестиком диагональное решение C10N91
Алгоритм Герберта.
CDS (91,10,1)
1,3,7,8,19,22,32,55,64,72

Получится?

[Herbert Kociemba]

Алгоритм Герберта.
CDS (91,10,1)
1,3,7,8,19,22,32,55,64,72

Получится?

This function gives the color of cell a[x][y],1<=x,y<=91 for C10N91:

int color(int x, int y){

char cds[] = {1,3,7,8,19,22,32,55,64,72};
for (int i=0;i<10;i++)
for (int j=0;j<10;j++)
if ((91+x+y+cds[j]-cds[i])%91==1) return j+1;
}

The colors of the diagonal from lower left to upper right can be choosen arbitrarily.

[Nataly-Mak]

Herbert Kociemba
как я понимаю, вы написали программу построения решения C10N91.
Спасибо!

К сожалению, не понимаю этот язык программирования
Я тоже немного автоматизировала процесс построения; у меня программка на языке QBASIC.

Мне интересен вопрос построения диагональных решений C^2xC^2.
Есть ли у вас идеи?
Как, например, быстро построить решения C4N16, C5N25 и т.д.?

[dimkadimon]

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

Вы уже знаете, как модифицировать метод Герберта?
Очень интересно! Будем ждать рассказ об этом.

Хотя... вы уже кое-что рассказали:

Цитата:

Зато обнаружил что можно немного уменьшить требования CDS - можно искать цепочки где каждая разница встречается 0 или 1 раз. То есть какие то разницы вообще не встречаются. В этом случае, правда, для других цветов надо находить отдельные цепочки (которые отличны) от первой. Таким образом я теперь очень быстро могу находить диагональные решения C5N25 и C6N36, а вот для C>=10 никакого прогресса.

Но я пока ничего не поняла

Суть в том что вместо одной CDS можно использовать несколько разных CDS. Причем можно использовать CDS в которой не все разницы от 1 до v-1, а только некоторые - главное чтобы все разницы были разными.