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

[Nataly-Mak]

Zealint в сообщении #588756 писал(а):

Вчера всю ночь квадраты снились.

Ага, а мне всю ночь снилось достраивание прямоугольников
Подробностей тоже не помню, но вот уже как будто получилось достроить прямоугольник 9х12 3-coloring до квадрата 13х13 4-coloring очень гармонично и надо было это срочно записать, но во сне, увы, записывать не умею

-- Пн июн 25, 2012 09:49:53 --

Цитата:

Получилась слишком оптимистическая картина. По лемме есть возможность построить диагональное решение 10х10 для С=3, 18х18 для С=4, 28х28 для С=5.

svb
не пробовали построение диагонального решения C=5, N=28x28?
У вас по программе это должно быстро получиться (паче чаяния такое решение действительно существует), если для С=6, N=36x36 получилось мгновенно.

Ждём новый рекорд!

[svb]

Nataly-Mak в [url=http://dxdy.ru/post588735.html#p588735 писал(а):

svb
если вы разобрались с теоремой 4.12, скажите, пожалуйста:
какой из выложенных мной трёх вариантов прямоугольника 9х12 3-coloring построен по этой теореме?
Тогда я буду думать над достраиванием правильного варианта.

Если вы про формулировку, то там и переводить нечего - приведены формулы возможных прямоугольников. Доказательство основывается на лемме 4.11 и на существовании полей с числом элементов равным степени простого числа. Нас могут интересовать c=8,9,16. Я не стал разбираться, а попытался найти эти поля - кончилось тем, что для с=16 пришлось писать программку для получения таблиц сложения и умножения элементов поля. Далее написал простенькую программу формирования нужных нам квадратов для получения квадратов $c^2$ (для полей). Собрался было писать программу достраивания перебором, но удалось придумать и реализовать программно получение $c^2+c+1$ - этой ночью. Это дает 19.777562 при текущих рекордах, теперь начинается основное.

-- Пн июн 25, 2012 09:10:16 --

Цитата:

не пробовали построение диагонального решения C=5, N=28x28?

- откуда вы взяли, что это возможно?

[Pavlovsky]

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

откуда вы взяли, что это возможно?

Тут немного пофлеймили, поэтому мои посты затерялись
post588417.html#p588417
post588744.html#p588744

[svb]

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

Тут немного пофлеймили, поэтому мои посты затерялись
post588417.html#p588417
post588744.html#p588744

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

[dimkadimon]

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

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

...но Pavlovsky описал и объяснил теорему 4.12 ещё в самом начале. Эта теорема описывает как строить C^2 x C^2 С-coloring когда С простое число.
Нужно числа от 1 до С^2 разбить на С групп по С чисел и сделать это С раз так что любая пара чисел встречалась не более чем в одной группе.

Вот это мне не надо объяснять!
Построение квадрата C^2xC^2 C-coloring для С простых я давным-давно поняла, все эти квадраты построила и отправила на конкурс.

Теперь речь совсем о другом! О построении прямоугольника С^2+C C-coloring.
Вы хоть вникли в то, о чём я прошу svb???

Вы получили подсказку и радуйтесь. Кстати, вообще говоря, Pavlovsky нарушил правила конкурса. Он не имел права давать вам явную подсказку.
А я не прошу никаких подсказок. Я прошу нормальный перевод теоремы 4.12 на русский язык. Это не является подсказкой! Вам понятно?

Построение прямоугольника С^2+С основано на построении С^2. Если вы поняли как строить С^2 по 4.12 то остался всего лишь один шаг до (С^2+С) х С^2. Если точнее то вам осталось найти ещё одно разбиение...

И пожалуйста не надо жаловаться модератору! Я тут хочу вам помочь. Я повторяюсь потому что на некоторые ваши вопросы уже ответили (может частично), но вы эти ответы не заметили вот и всё.

[svb]

Pavlovsky
Хотя ... можно будет потом посмотреть

[Pavlovsky]

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

Увы, если ломать диагонали - а именно для этого случая я делал перебор - то 25 это максимум

Я рассматриваю все 2n-1 диагонали. Требование расскрашивать ломанные диагонали (полученные циклическим сдвигом) в один цвет, на мой взгляд, слишком надуманое. Разве что перебор сокращается.

[svb]

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

Я рассматриваю все 2n-1 диагонали. Требование расскрашивать ломанные диагонали (полученные циклическим сдвигом) в один цвет, на мой взгляд, слишком надуманое. Разве что перебор сокращается.

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

[Pavlovsky]

А насчет перебора, есть много разных способов. Например проблема 28х28 для С=5. У меня есть раскраска 12 диагоналей одним цветом. Осталось расскрасить оставшиеся 55-12=43 диагонали в 4 цвета. То есть по 11 диагоналей на один цвет (одним цветом 10 диагоналей). Задача вполне реальная. К тому же различных раскрасок диагоналей в один цвет на самом деле не так много. Пусть у нас есть раскраска диагоналей (a1,...ak), где a1,..,ak номера диагоналей. Тогда раскраска (a1+d,...ak+d) тоже корректная. Зеркальное отражение раскраски диагоналей, тоже корректное. Анализ показывает достаточно двух видов раскрасок, которые начинаются (1,2,4,...) и (1,3,4,...) эти раскраски прекрасно вкладываются друг в друга.

[Nataly-Mak]

Цитата:

Построение прямоугольника С^2+С основано на построении С^2. Если вы поняли как строить С^2 по 4.12 то остался всего лишь один шаг до (С^2+С) х С^2. Если точнее то вам осталось найти ещё одно разбиение...

И пожалуйста не надо жаловаться модератору! Я тут хочу вам помочь. Я повторяюсь потому что на некоторые ваши вопросы уже ответили (может частично), но вы эти ответы не заметили вот и всё.

Блин!!!
Я же сказала, что умею строить прямоугольники (С^2+С) х С^2! Привела здесь такие прямоугольники 9х12 3-coloring, 25x30 5-coloring.
Похоже, вы совсем не понимаете по-русски. Я вам уже трижды всё пояснила, а вы опять повторяете то же самое.

Да, я поняла, как строить C^2 по объяснению Pavlovsky.
Это тут уже 5 раз написала!
Вы читать будете мои сообщения???

Какой ещё один шаг мне остался?

Мне остался один шаг - это достраивание прямоугольника (С^2+С) х С^2 С-coloring до квадрата С^2+C+1 (C+1)-coloring.

Вот как делать достраивание - этот один шаг - я не знаю.
Если вы хотите мне помочь (в чём я очень сильно сомневаюсь), тогда дайте ответ на мой вопрос: правильно ли я построила прямоугольники (С^2+С) х С^2!

Что вы мне объясняете, как строить прямоугольники, если я их уже построила?
Ещё раз специально для вас повторяю:
я не знаю, соответствуют ли мои прямоугольники алгоритму теоремы 4.12.

Цитата:

...на некоторые ваши вопросы уже ответили (может частично), но вы эти ответы не заметили вот и всё.

Приведите пример такого ответа, который я не заметила!

-- Пн июн 25, 2012 11:55:10 --

Вот прямоугольник 81х90 9-coloring:



Повторяю вопрос, специально для dimkadimon, а также и для svb, потому что в его посте я не увидела ответ на свой вопрос:

этот прямоугольник соответствует алгоритму теоремы 4.12??

Я легко могу построить и следующие прямоугольники, для С=11 121х132, для С=13 169х182 и т.д.

Но не умею пока эти прямоугольники достраивать до квадратов.

И ещё раз повторюсь (это важно!): Pavlovsky тут делал замечание, что прямоугольники должны быть построены именно по алгоритму теоремы 4.12.
А я их строю по-своему.

-- Пн июн 25, 2012 12:06:07 --

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

Если вы про формулировку, то там и переводить нечего - приведены формулы возможных прямоугольников. Доказательство основывается на лемме 4.11 и на существовании полей с числом элементов равным степени простого числа. Нас могут интересовать c=8,9,16. Я не стал разбираться, а попытался найти эти поля - кончилось тем, что для с=16 пришлось писать программку для получения таблиц сложения и умножения элементов поля.

Как я понимаю, вы не знаете ответ на мой вопрос: соответствуют ли построенные мной прямоугольники C^2x(C^2+C) алгоритму теоремы 4.12.

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

Значит, вы не разбирались в этой теореме и решили задачу по-своему. Правильно понимаю?

Конечно же, меня интересует не формулировка теоремы Что утверждает теорема, я вроде как поняла.
Меня интересует её доказательство, так как именно в доказательстве (как я предполагаю) и есть тот самый алгоритм.

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

-- Пн июн 25, 2012 12:18:49 --

Вот они - джентльмены

6  Tom Sirgedas 19.777600 06-07-2012 @ 07:11:18
7  Il brigante Pennastorta 19.777600 06-08-2012 @ 16:28:33
8  Valery Pavlovsky 19.777600 06-15-2012 @ 11:02:58

Плюс svb.

Интересно, сколько таких джентльменов будет к концу конкурса. Думаю, что немало.

[Pavlovsky]

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

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

Осторожно подсказка удалена!

[Nataly-Mak]

Подсказку не открывала!! Честное слово!
А вы кому подсказываете-то? Надеюсь, что не мне

Вот формулировка теоремы 4.12

Theorem 4.12 
Let p be a prime and s, d ∈ N.
1. Gpds,
pds−1
p−1
is strongly pds−s
-colorable.
2. Gpds,
pds−1
p−1 pds−s is pds−s
-colorable.

Извиняюсь за плохую копию, но лучше не получается.

А это перевод, сделанный в Google

Цитата:

теорема 4.12 Пусть р-простое число, S, D ∈ N. 1. ГФД, PDS-1 Р-1 сильно PDS-х годов -раскрашиваем. 2. ГФД, PDS-1 р-1 PDS-S PDS-х годов -раскрашиваем.

Толковый перевод, не правда ли?
По такому переводу даже будучи семи пядей во лбу понять что-либо абсолютно невозможно.

Но я формулировку теоремы поняла без перевода.

-- Пн июн 25, 2012 12:38:13 --

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

Осторожно подсказка удалена!

Вот и отлично!
Мне не нужны ваши подсказки. Я больше не читаю спрятанных текстов.

[Nataly-Mak]

Диагональное решение C=5, N=26x26



Хи-хи...
Не пугайтесь, решение с ошибками. 206 ошибок.
Взяла диагональное решение C=5, N=20x20 и просто продолжила его до квадрата 26х26.

-- Пн июн 25, 2012 14:45:08 --

Довольно быстро удалось свести количество ошибок к 123 (вручную в программе Эда).
Обратите внимание: диагональность испортилась совсем немного.



Вполне возможно, что диагональное решение C=5, N=26x26 существует.

[Nataly-Mak]

Диагональное решение C=4, N=18x18, 102 ошибки:

[Nataly-Mak]

Решение С=4, N=7x7 "ход конём"



Интересно, для каких C и N существуют решения "ход конём"?
Такие решения очень просто составлять.