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

[Pavlovsky]

Хорошая получается ветка. Интерсный и живой обмен мнениями. Собственно ради такого обсуждения и участвую в конкурсе. Ну не интересно мне сидеть дома и в одиночку, что то ваять. Для меня важен процесс, а не результат!

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

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

У меня получилось именно так.

(Оффтоп)

Строим прямоугольник С^2x(C^2+C) с использованием С цветов по алгоритму из теоремы 4.12. И достраиваем его с использованием C+1 цвета. Причем при достраивании не нужен перебор. Если внимательно посмотреть на исходный прямоугольник, то легко увидеть простой "регулярный" алгоритм достраивания.

[Nataly-Mak]

С ума сойти!!!
Pavlovsky "раскололся"

А я вчера вечером как раз тоже догадалась Ну, вот теоремку одну в статье прочитала, и где-то в подсознании мелькнула идейка

Вот эта теоремка:



Причём эта теоремка совсем в другой статье, не там, где теорема 4.12.

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

Уф! Еле разобралась с картинкой Не та картинка прикреплялась.

[Pavlovsky]

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

С ума сойти!!!Pavlovsky "раскололся"

Herbert Kociemba тоже расколося.
http://infinitesearchspace.dyndns.org/c ... omment-865
Может кто переведет текст?

Цитата:

I struggled for one week to find a 36x36 solution to C=6 until a new idea led to a breakthrough. I needed 6 sets with 6 numbers each, with certain properties. To find these 6 sets (which fortunately existed) I wrote a small C-program outside Mathematica.
Otherwise, indeed all is done within Mathematica. I describe the colors of the square with a function m[x_, y_, p_, d_] . x and y give the position within the square, p is a prime and d the power of the prime.
If C is the number of colors and N the square length I have functions
m1: C=p^d, N= p^(2d)
m2: C=p^d+1, N= p^(2d)+p^d+1
Recent improvements:
m3: C=p^d+1, N= p^(2d)+p^d+2
m4: C=p^d+1, N= p^(2d)+p^d+3, with conflicts at two positions unsolved. Does work for d=1 but not for all d>1, for example not for p=3 and d=2 (10 colors). The conflicts seem to be solvable manually using Ed's program. Example is p=13,d=1 with C=14 and N=185. I did not apply m4 for p>13 yet, because it is unmanageable with Ed's program.
C=15 and C=21 take the form C=p^d + 2. In the moment I just add one row and one column to solutions with C=p^d+1, there surely are better ways.
Well, m4 is quite a loooong line, so it should count as two lines
With two lines defining multiplication and addition of the matrix elements, yes, it about 8 lines of code now.

[Nataly-Mak]

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

Herbert Kociemba тоже расколося.

Ну, что Herbert Kociemba раскололся, меня не удивляет.
А вот вы-то с чего вдруг раскололись?

А вы разве сами не умеете переводить? Вроде вы писали на форуме ПЕН, что читаете по-английски свободно, проблемы у вас с письмом.

[Pavlovsky]

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

А вы разве сами не умеете переводить? Вроде вы писали на форуме ПЕН, что читаете по-английски свободно, проблемы у вас с письмом.

Почему то русские тексты читаю значительно быстрее английских. Если никто быстро не переведет, то переведу сам но позже. Одно дело читать технические тексты. Другое дело сообщения на форумах, где носители языка позволяют себе вольности.

-- Пт июн 22, 2012 09:19:58 --

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

Вот эта теоремка:

Эту теорему можно усилить. Она верна и для С=p^s, где p-простое.

[Nataly-Mak]

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

Строим прямоугольник С^2x(C^2+C) с использованием С цветов по алгоритму из теоремы 4.12. И достраиваем его с использованием C+1 цвета. Причем при достраивании не нужен перебор. Если внимательно посмотреть на исходный прямоугольник, то легко увидеть простой "регулярный" алгоритм достраивания.

Судя по вашей подсказке, достаточно для C простых. О чём как раз и говорит приведённая мной теорема.

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

Догадалась после прочтения этой теоремы так: для C=6, говорят, получается решение N=31x31, то есть 25+6.
А по теореме для C=5 мы имеем прямоугольник 25х30 С-coloring. Значит, его надо просто достроить до прямоугольника 31х31 с использованием 6-го цвета.

Вот, осталось совсем немного:
1. построить прямоугольник 25х30 5-coloring;
2. достроить этот прямоугольник до 31х31 6-coloring.

Однако решение C=6, N=31x31 у меня уже есть.
Мне надо начинать с C=10.

Да, а вот здесь как раз надо усиление теоремы, о котором вы говорили. Это единственный случай, когда k>1 в рассматриваемом алгоритме. Во всех остальных случаях k=1.

[Pavlovsky]

Наталия

(Оффтоп)

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

[Nataly-Mak]

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

Наталия

(Оффтоп)

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

Не собираюсь ничего прятать!
Как будто off нельзя прочитать

-- Пт июн 22, 2012 08:43:13 --

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

Эту теорему можно усилить. Она верна и для С=p^s, где p-простое.

Да, там, кажется, об этом написано:

Цитата:

Have more general theorem.

[Pavlovsky]

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

Вот, осталось совсем немного:1. построить прямоугольник 25х30 5-coloring;2. достроить этот прямоугольник до 31х31 6-coloring.

(Оффтоп)

Одно замечание. 25х30 5-coloring должен быть построен по алгоритму из теоремы 4.12. Не уверен, что любой прямоугольник 25х30 5-coloring можно достроить до прямоугольника 31х31 6-coloring.

[Nataly-Mak]

Pavlovsky
ну зачем же так много подсказок?
Думаю, что dimkadimon уже давно всё понял и ушёл строить решения

-- Пт июн 22, 2012 09:06:01 --

Алексей Чернов не уступает первое место!

1  Alex Chernov 19.942500 06-22-2012 @ 00:40:43

Так держать, Алексей!

Борьба в первой тройке будет, видимо, очень напряжённая.

-- Пт июн 22, 2012 09:19:20 --

Кстати, формулу для решения в алгоритме для C=p^k+1, p - простое число, k>=1
лучше записывать в виде:

(C - 1)^2 + C

Так быстрее можно догадаться.

[Nataly-Mak]

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

Вот, осталось совсем немного:
1. построить прямоугольник 25х30 5-coloring;
2. достроить этот прямоугольник до 31х31 6-coloring.

Увы, ничего мне моя догадка не дала

Посмотрела на теорему 4.12. Мама дорогая! Даже если бы я знала английский, всё равно ничего бы не поняла в её доказательстве. Это доказательство, как я поняла, основано на теории конечных полей, о которой не имею ни малейшего понятия.
При этом теорема сформулирована и доказывается в общем виде, а там вообще дебри непроходимые.
Вижу там и разбиения, о которых вроде бы говорил Pavlovsky в самом начале темы. Но... ничего не могу понять.
Я знаю по описанию Pavlovsky, как построить квадрат 25х25 5-coloring по алгоритму данной теоремы, но совершенно не представляю, как построить прямоугольник 25х30 5-coloring. Где взять ещё 5 столбцов? (это я сама себя спрашиваю )

Нет, не для моего ума эта теорема.

А так вчера обрадовалась, что догадалась Радость была преждевременна.

Pavlovsky
прошу подсказок больше не давать

Надеюсь, что dimkadimon разберётся в алгоритме этой теоремы самостоятельно; он, по крайней мере, знает английский. Ваши подсказки ему больше, наверное, не потребуются. Или уж тогда подсказывайте в личке. Я не хочу читать ваши подсказки и тем более прятать их в тег off.

-- Пт июн 22, 2012 11:23:52 --

Количество конкурсантов приближается к 80.
Появился ещё один россиянин. Не наш форумчанин?

Что-то пока совсем не активен Константин Порозов, я всё жду, когда он начнёт вводить результаты.

У Алексея Чернова новый рекорд!

21 387 149769  Alex Chernov @ 10:23:32 on 06-22-2012 1

Молодец!

[Pavlovsky]

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

Pavlovskyпрошу подсказок больше не давать

Жаль уже хотел подсказать.

[Nataly-Mak]

Бросьте! Ничего вам не жаль.

[Nataly-Mak]

Alexu007
знаете ли вы, что ваше решение C=6, N=20x20 неплохо достраивается в программе Эда?
Не пробовали? Оно у вас нерегулярное и потому легко достраивается.

У меня получилось расширить ваш квадрат 20х20 до квадрата 26х26:

A,A,C,C,D,D,B,A,D,F,D,C,C,F,E,E,F,B,C,A,B,B,E,F,E,B,F,E,C,E,F,B,C,F,B,A,A,E,D,E,B,F,C,C,F,E,C,B
,A,A,E,D,A,B,C,A,C,C,F,D,A,E,C,B,E,B,D,F,B,F,D,D,F,E,A,D,E,D,C,A,D,A,B,C,D,E,F,F,E,B,E,D,B,B,D
,C,C,D,F,F,B,A,F,E,E,C,B,C,E,C,F,D,A,C,B,E,D,F,C,D,B,D,E,F,A,B,F,A,A,A,E,E,F,B,A,C,C,C,C,D,B,A,
A,A,E,F,E,D,D,F,D,F,A,F,C,E,F,A,E,D,E,D,A,B,C,E,E,C,D,E,C,B,E,F,A,D,B,A,C,F,B,F,D,A,A,B,B,E,B,F
,D,E,A,A,C,B,C,A,F,C,E,C,E,F,F,D,D,A,E,D,B,E,C,E,F,A,E,D,E,F,C,B,B,A,C,B,F,D,A,D,A,F,C,C,D,C,C
,D,F,A,D,B,C,B,B,B,E,F,A,E,E,F,D,C,E,A,A,E,F,A,F,C,E,A,B,F,C,E,D,B,C,E,A,D,D,D,B,A,A,A,D,C,F,E,
B,A,B,B,C,A,B,F,E,B,B,C,A,F,D,A,A,C,E,B,D,E,F,D,D,C,C,F,F,D,E,F,C,B,A,A,C,C,F,F,A,D,A,B,F,B,C,
E,E,C,D,A,D,E,E,C,F,D,A,A,E,E,D,F,F,D,C,E,B,A,D,F,F,A,E,E,D,A,B,B,F,F,E,A,A,E,E,A,B,A,B,D,F,F,E
,C,C,D,C,B,B,A,C,B,A,D,E,C,D,F,C,A,F,C,A,F,A,D,A,B,F,E,A,E,B,E,C,B,B,D,B,F,C,D,F,E,F,B,E,B,A,A,
D,F,E,B,F,D,D,E,D,A,C,C,F,B,C,B,B,A,D,F,A,F,E,F,E,D,D,B,D,C,A,E,A,C,E,B,A,B,C,F,C,E,D,F,F,C,B,
D,F,A,A,D,E,A,B,C,E,C,F,A,E,E,C,B,D,E,F,D,A,F,B,D,E,B,C,F,E,F,D,F,E,C,C,A,A,D,A,F,B,D,E,D,A,C,
A,F,A,C,E,A,A,B,F,A,F,D,B,A,E,F,B,E,D,C,A,C,B,C,D,C,C,B,B,C,F,D,D,E,A,B,C,D,F,A,D,A,E,E,E,B,F,
D,C,F,E,B,C,B,D,D,A,E,B,C,A,C,F,E,B,C,F,B,C,E,A,F,F,E,E,B,D,D,C,C,B,B,D,F,D,D,F,D,A,C,F,E,F,C,
F,E,F,A,A,A,B,E,D,C,B,E,E,B,D,B,A,C,E,B,C,F,B,F,C,F,D,E,C,A,D,D,A,C,A,D,D,D,D,F,D,B,B,A,E,C,C,
C,F,A,D,F,A,D,B,C,C,E,F,E,F,A

А если написать программу достраивания, можно и больше получить квадрат. В программе Эда ведь исправление ошибок выполняется вручную, а не автоматически.

-- Пт июн 22, 2012 15:29:22 --

Ну, вот, как я и предполагала, dimkadimon в алгоритме разобрался
Какой рывок, с 24-го места сразу на 2-ое!

1  Alex Chernov 19.942500 06-22-2012 @ 10:23:32
2  Dmitry Kamenetsky 19.941100 06-22-2012 @ 15:14:03
3  Herbert Kociemba 19.926600 06-21-2012 @ 03:23:52

dimkadimon
а помните, вы выступали против подсказок? Вам теперь надо объединиться с Павловским в одну команду, как вы, помнится, предлагали тут

[Pavlovsky]

Может кому будет интересно порешать вспомогательную задачу.

В квадрате NxN расставить максимальное количество 1, так чтобы не возникало запрещенных прямоугольников (все вершины которых помечены 1). Особо интересуют квадраты 5х5, 7х7, 9х9.
У меня получилось
Для 5х5 12 единиц
Для 7х7 21 единица
Для 9х9 29 единиц.
Не знаю являются ли эти результаты максимальными?