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

[Pavlovsky]

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

Аналогичное имеется и для C=5, N=25x25, и даже для C=6, N=36x36

В квадрате 36х36 36+35=71 диагоналей. Перебрать все варианты цветов диагоналей? Будет 6^71 вариантов. Много.

[svb]

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

В квадрате 36х36 36+35=71 диагоналей. Перебрать все варианты цветов диагоналей? Будет 6^71 вариантов. Много.

А отсечение вариантов? Да и диагоналей можно оставить только 36.

[Pavlovsky]

Читаем статью
http://www.informatik.tu-freiberg.de/pr ... cfcrfg.pdf
Extremely Complex 4-Colored Rectangle-Free Grids:Solution of Open Multiple-Valued Problems

Идея которая зацепила.

На рисунке представлен квадрат 18х18, заполненный 0 и 1.
Во-первых. Единички расставлены так, что запрещенных прямоугольников нет.
Самое главное. При повороте на 90, 180, 270 градусов единички переходят в нули. То есть получается 4-раскрашенный квадрат 18х18!

(Оффтоп)

Идею можно применить для С=4k. Скажем для С=8. Только в этом случае квадрат должен быть заполнен 1 и 2. Остальное нули.

[dimkadimon]

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

Идею можно применить для С=4k. Скажем для С=8. Только в этом случае квадрат должен быть заполнен 1 и 2. Остальное нули.

Нуууу зачем же сразу так все выкладывать... пусть люди сами подумают и догадаются. Например я несколько недель потратил чтобы прийти к такой идеи.

[svb]

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

Нуууу зачем же сразу так все выкладывать... пусть люди сами подумают и догадаются. Например я несколько недель потратил чтобы прийти к такой идеи.

В 60-е годы был миф о промышленном шпионаже, но потом оказалось, что от такого шпионажа толку мало. Так и от этих "подсказок" толку мало. А может это ловушки?

[dimkadimon]

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

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

Нуууу зачем же сразу так все выкладывать... пусть люди сами подумают и догадаются. Например я несколько недель потратил чтобы прийти к такой идеи.

В 60-е годы был миф о промышленном шпионаже, но потом оказалось, что от такого шпионажа толку мало. Так и от этих "подсказок" толку мало. А может это ловушки?

Может и толку мало от етой подсказки, но очень обидно когда ты долго бъешся над одной идеей, а другим она достается бесплатно на тарелочке.

[Pavlovsky]

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

Нуууу зачем же сразу так все выкладывать... пусть люди сами подумают и догадаются

Не надо было обращать внимание на эту статью (шучу). У меня эти статьи уже были помечены как отработанный материал. С вашей наводки я их еще раз перечитал. Есть люди котрорые все понимают с полунамека.
Например

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

Но есть еще алгоритм! Для С=2K с решением С^2-C+1. Его знают 6 человек. Надо еще раз посмотреть статьи.

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

Это алгоритм для С=р^к+1, где р простое число и к>=1.

Мне хватило вашего намека, чтобы быстро придумать этот алгоритм.

[Nataly-Mak]

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

Мне хватило вашего намека, чтобы быстро придумать этот алгоритм.

И любите же вы себя похвалить
И того вам хватило, и этого вам хватило...
А мне вот ничего не хватает Такая уж глупая уродилась

[Ха! А самому dimkadimon своего собственного намёка хватило?]

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

Вот аналогичное "диагональное" решение для C=5, N=17x17:



Предположу, что такие "диагональные" (регулярные ) решения для С=5 существуют и далее: N=18x18, N=19x19, ..., N=25x25.
Решение N=20x20 я уже показала.
svb утверждает, что N=25x25 тоже существует.
А может, и N=26x26 существует? Такое ещё никто не нашёл?

А я бросила совсем думать и часа два играла в программе Эда в достраивание.
Начала с того самого прямоугольника 7х36 6-coloring, который я построила по лемме Макаровой-Беляева. И достроила этот прямоугольник до прямоугольника 21х36 6-coloring.

Решения получается нерегулярные!
Могу высказать такую гипотезу:
нерегулярные решения больше подходят для достраивания, чем регулярные.

Итак, мне осталось пристроить до квадрата 36х36 всего 15 строк. Если в день пристаивать по одной строке, успею до конца конкурса
Если и дальше так же хорошо пойдёт, как эти 14 строк, то можно пристроить.

-- Чт июн 21, 2012 19:58:16 --

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

Например я несколько недель потратил чтобы прийти к такой идеи.

"Несколько недель" - это сколько? Конкурс идёт всего 3 недели

-- Чт июн 21, 2012 20:07:52 --

Наконец-то меня сместили с 13-го места

В первой десятке осталось уже только трое россиян.
Вперёд рвутся германцы, похоже, это их конкурс.

Уже много конкурсантов имеют более 19 баллов и ещё несколько в зоне 18 баллов с хвостиком, они тоже скоро войдут в зону 19 баллов с хвостиком.
И далее всё будет решать этот самый "хвостик". Для высоких мест "хвостик" должен быть примерно 0,95-0,99.

[Nataly-Mak]

Цитата:

Предположу, что такие "диагональные" (регулярные ) решения для С=5 существуют и далее: N=18x18, N=19x19, ..., N=25x25.
Решение N=20x20 я уже показала.
svb утверждает, что N=25x25 тоже существует.
А может, и N=26x26 существует? Такое ещё никто не нашёл?

Предположение верное
Вот они - диагональные решения для C=5:

1.17×17, five colors:
01033143221100434
10331432211004344
03314322110043441
33143221100434410
31432211004344102
14322110043441020
43221100434410203
32211004344102034
22110043441020343
21100434410203433
11004344102034332
10043441020343322
00434410203433221
04344102034332211
43441020343322112
34410203433221120
44102034332211201

18×18, five colors:
043122334210234010
431223342102340100
312233421023401001
122334210234010011
223342102340100113
233421023401001132
334210234010011324
342102340100113244
421023401001132443
210234010011324434
102340100113244342
023401001132443422
234010011324434220
340100113244342203
401001132443422034
010011324434220343
100113244342203430
001132443422034301

19×19, five colors:
4303002340121224314
3030023401212243144
0300234012122431441
3002340121224314411
0023401212243144110
0234012122431441103
2340121224314411034
3401212243144110340
4012122431441103403
0121224314411034032
1212243144110340323
2122431441103403230
1224314411034032300
2243144110340323002
2431441103403230024
4314411034032300242
3144110340323002423
1441103403230024231
4411034032300242312

20×20, five colors:
02102234401133414324
21022344011334143242
10223440113341432420
02234401133414324201
22344011334143242010
23440113341432420100
34401133414324201002
44011334143242010022
40113341432420100223
01133414324201002230
11334143242010022304
13341432420100223043
33414324201002230431
34143242010022304311
41432420100223043114
14324201002230431140
43242010022304311401
32420100223043114013
24201002230431140131
42010022304311401313

Решения из статьи:
http://bit-player.org/2009/the-17x17-challenge

Наверняка тут есть какая-то закономерность.
Теперь надо построить аналогичные решения N=21x21, 22x22, 23x23, 24x24 и 25x25.

dimkadimon
не это ли ваш четвёртый метод для решения C=5, N=25x25?

И для C=4, N=16x16 тоже есть диагональное решение (из той же статьи):

0010113323220312
0101133232203120
1011332322031200
0113323220312001
1133232203120010
1332322031200101
3323220312001011
3232203120010113
2322031200101133
3220312001011332
2203120010113323
2031200101133232
0312001011332322
3120010113323220
1200101133232203
2001011332322031

Хм... так на что svb намекал? Что и для C=6, N=36x36 есть такое же диагональное решение? Он сказал "аналогичное"... Думаем...

[Vitaly12]

Pavlovsky

Цитата:

При повороте на 90, 180, 270 градусов единички переходят в нули. То есть получается 4-раскрашенный квадрат 18х18!

Поясните, пожалуйста

[Nataly-Mak]

Посмотрела на диагональные решения.
В решении для C=4, N=16x16 банальный циклический сдвиг строк.
Как-то (как ) составили первую строку:

0010113323220312

Дальше поехали, вторая строка:

0101133232203120

Циклический сдвиг в чистом виде!
Третья строка точно таким же сдвигом получается из второй строки:

1011332322031200

И т. д.

Следовательно, здесь поиск решения сводится к поиску только одной первой строки.
Написано ли в статье, как составлять первую строку?
Есть ли математическая идея? Или тут надо действовать тупым перебором и/или случайной генерацией? Скорее всего, первое - есть математическая идея.

Теперь смотрим на диагональные решения для C=5.
Здесь тоже используется сдвиг в строках, но он не совсем циклический, т. к. последее число не "зацикливается".

Например. в решении для C=5, N=17x17.
Первая строка:

01033143221100434

Как составляется эта строка
Вторая строка получается из первой сдвигом, но последнее число не 0, как должно быть в циклическом сдвиге, а 4:

10331432211004344

Почему здесь не циклический сдвиг, мне непонятно. Как определяется последнее число в строке при сдвиге, тоже непонятно.
И так я вижу во всех решениях для C=5.

Интересен мне такой вопрос: вот в этой статье приведены диагональные решения. Решения я вижу без перевода; скопировала, посмотрела на них.
Описывается ли в статье процесс построения решений? Или просто написано: "Вот я построил такие решения?" Если так, это, конечно, очень научно. Как я построил, догадайтесь сами
Ну, для тех, кто всё понимает с полунамёка, годится.

-- Пт июн 22, 2012 04:53:35 --

Кстати, о птичках... то бишь о намёках

Когда я выложила диагональное решение для C=4:

Цитата:

И замечательное, очень гармоничное решение C=4, N=16x16.
Решение нашла в Интернете, к сожалению, не записала ссылку.
Это уж точно регулярное решение, всё супер регулярно.

Pavlovsky "намекнул":

Цитата:

В книге Картеси описывается такой метод построения квадратов. Эксперементировал с этим методом построения. Увы хороших результатов этот метод не дает.

Когда я выложила диагональное решение для C=5:

Цитата:

Решение C=5, N=20x20, не максимальное, но очень изящное.
Тоже интернетовское.
Наверное, регулярное.

svb "намекнул":

Цитата:

Аналогичное имеется и для C=5, N=25x25, и даже для C=6, N=36x36

Вот такие намёки

Коллеги явно друг другу противоречат. Ибо решение C=6, N=36x36 относится к "хорошим" решениям, а Pavlovsky утверждает, что среди диагональных решений не стоит искать "хорошие" решения, их там нет.

Кстати, ссылку на статью, где приведены все эти решения, теперь нашла, она приведена выше.

Могу предположить, что Pavlovsky не знал о существовании диагонального решения для C=6, N=36x36.
А красивое должно быть решение, если оно существует, как утверждает svb.

Но как же для этого решения найти первую строку? Неужели перебором? Нет, должна быть какая-то идея. И как потом делать сдвиг?

Ну, это я уже сама себя спрашиваю, пусть коллеги не беспокоятся

-- Пт июн 22, 2012 05:08:31 --

И ещё один весьма интересный "намёк":

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

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

Здесь написано, что способ, которым получено решение для 6 цветов, "захлебнулся" на больших числах. Захлебнуться, по-моему, может только перебор. Математическая идея не может захлебнуться

[dimkadimon]

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

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

Это алгоритм для С=р^к+1, где р простое число и к>=1.

Мне хватило вашего намека, чтобы быстро придумать этот алгоритм.

Забавно получилось. Мой намёк помог вам, но не помог мне. Увы я не такой догадливый. Значит всё таки решение для C=p^k+1 находится через решение C=p^k?

[Nataly-Mak]

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

Забавно получилось. Мой намёк помог вам, но не помог мне. Увы я не такой догадливый.

Действительно, очень забавно

Цитата:

Значит всё таки решение для C=p^k+1 находится через решение C=p^k?

Подсказку просите? Или намёк?

Тут весьма туманные дают намёки и даже противоречивые; пример таких намёков я привела выше. По мне, уж лучше никаких не надо намёков, чем такие, которые ведут в тёмный лес.

[dimkadimon]

Vitaly12 в сообщении #587747 писал(а):

Pavlovsky

Цитата:

При повороте на 90, 180, 270 градусов единички переходят в нули. То есть получается 4-раскрашенный квадрат 18х18!

Поясните, пожалуйста

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

1а 2а 3а 1б
3г 4а 4б 2б
2г 4г 4в 3б
1г 3в 2в 1в

Для первого цвета надо поставить один в одной клетке из (1а, 1б, 1в, 1г), одной клетке из (2а, 2б, 2в, 2г), (3а, 3б, 3в, 3г) и (4а, 4б, 4в, 4г), а все остальные нули.

[Nataly-Mak]

Vitaly12 в сообщении #587747 писал(а):

Pavlovsky

Цитата:

При повороте на 90, 180, 270 градусов единички переходят в нули. То есть получается 4-раскрашенный квадрат 18х18!

Поясните, пожалуйста

Всё просто! Крутите исходный квадрат 18х18, и при первом повороте в те ячейки, где окажутся единички, запишите число 2, при втором повороте в ячейки, где окажутся единички, запишите число 3.
Только крутить надо так: сначала поворачивайте на 90 градусов, а потом на 270 (на 180 не надо поворачивать).
Я думаю, что поворачивать можно как по часовой стрелке, так и против. Я поворачивала по часовой стрелке.

Результат такой получился у меня - С=4, N=18x18:

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

Кстати, решение С=4, N=18x18 есть готовое в Интернете.

Да, и схему такую - квадрат 18х18, заполненный нулями и единичками, вроде видела ещё в какой-то статье.

Пока я писала ответ, уже ответили. Ну, пусть и моё объяснение будет.

-- Пт июн 22, 2012 07:14:44 --

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

Если взять решение с единичками и повернуть его на 90 градусов то получится решение для второго цвета, повернуть ещё на 90 и получится для третьего цвета, ещё на 90 и получится для четвертого цвета. Все 4 цвета не пересекаются.

А я всего два раза поворачивала. Ведь нули и единички в квадрате уже стоят, осталось поставить двойки (первый поворот) и тройки (второй поворот).