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

[Nataly-Mak]

Прямоугольник 9х12 3-coloring третий вариант:

12,9,A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,B,C,A,B,C,A,B,C,A,B,C,
A,A,B,C,B,C,A,A,B,C,C,A,B,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,C,A,B,C,A,B,A,B,C,C,A,B,B,C,A,A
,B,C,C,A,B,C,A,B,A,B,C,B,C,A,B,C,A

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

Все прямоугольники, разумеется, правильные, все они 3-coloring. Но я не знаю, какой из них соответствует алгоритму теоремы 4.12.

Может быть, перевод этой теоремы выложите? Всё-таки базовая теорема. А вот помочь с переводом никто не в состоянии почему-то.

Pavlovsky знает английский хорошо, и то просил перевода текста алгоритма с форума конкурса. Говорит, что русский текст как-то быстрее читает, чем английский

А я английский текст совсем никак не читаю

[dimkadimon]

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

Но я не знаю, какой из них соответствует алгоритму теоремы 4.12.

Может быть, перевод этой теоремы выложите? Всё-таки базовая теорема. А вот помочь с переводом никто не в состоянии почему-то.

Pavlovsky знает английский хорошо, и то просил перевода текста алгоритма с форума конкурса. Говорит, что русский текст как-то быстрее читает, чем английский

А я английский текст совсем никак не читаю

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

[Nataly-Mak]

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

Вроде разобрался с алгоритмом построения квадрата C^2xC^2.

А. Множество чисел Х={1...C^2} надо С способами разбить на С групп по С чисел. В соответсвии с леммой 4.11 надо чтобы любые два числа входили только в одну группу.

Б. Строим прямоугольник C^2xC по алгоритму изложенному в лемме 4.11 (часть 1). Прямоугольник будет "strong C-coloring".

В. Строим квадрат C^2xC^2 по алгоритму изложенному в лемме 4.3. В итоге получется искомый квадрат.

Пример. С=2

А. P1={1,2|3,4} P2={1,3|2,4}

Б.
1 1
1 2
2 1
2 2
В.
1 1 2 2
1 2 2 1
2 1 1 2
2 2 1 1
Квадрат построен.

Вот здесь Pavlovsky описал построение по теореме 4.12 квадрата 4х4 2-coloring.
Но для построения этого квадрата он строил прямоугольник 2х4 strong-2-coloring. А вот построение прямоугольника 4х6 2-coloring здесь не показано. Из этого прямоугольника должен получиться квадрат 7х7 3-coloring.

Кстати, я проделала построение квадрата 4х4 2-coloring по изложенному алгоритму, у меня результат получился несколько другой.
Чуть далее Pavlovsky описал процесс получения разбиений.
Так вот, у меня по этому описанию получились такие разбиения для С=2:

1 группа, шаг (1,0): {1,2}, {3,4}
2 группа, шаг (1,1): {1,4}, {3,2}

Первая группа такая же, как у Pavlovsky, вторая другая.

Строю по этим разбиениям прямоугольник 2х4 strong-2-coloring (прямоугольник Б):

1 1
1 2
2 2
2 1

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

И наконец, строю квадрат 4х4 2-coloring (квадрат В):

1-ый вариант:

1 1 2 2
1 2 2 1
2 2 1 1
2 1 1 2

Кстати, красивое диагональное решение. В квадрате, построенном Pavlovsky, диагональность нарушена.

2-ой вариант:

1 2 1 2
1 2 2 1
2 1 2 1
2 1 1 2

здесь используется замена каждого элемента прямоугльника 2х4 2-coloring таким образом:

1={1,2}
2={2,1}

Очевидно, что квадрат 2-го варианта получается из квадрата первого варианта перестановкой столбцов.

По изложенному алгороитму я получила все решения для С простых.

-- Пн июн 25, 2012 07:48:08 --

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

Вы уже наверное несколько недель просите об этом, но Pavlovsky описал и объяснил теорему 4.12 ещё в самом начале.

Вас я прошу только об одном (уже в n-й раз): прекратите делать повторения!!

Я без вас отлично вижу все посты и знаю, кто где что объяснял.
Мне ужасно надоели ваши повторения!
Вы просто засоряете тему этими повторениями.

Пока я писала своё сообщение (в котором как раз и описываю пояснение Pavlovsky), вы уже успели влезть с повторением.

Так как: вы прекратите свои повторения? Или я буду жаловаться на вас модераторам.

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

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 на русский язык. Это не является подсказкой! Вам понятно?

[Zealint]

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

Кстати, вообще говоря, Pavlovsky нарушил правила конкурса. Он не имел права давать вам явную подсказку.

А можно получить ссылку на правила конкурса и на права участников?

[Nataly-Mak]

Цитата:

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

Вот явная подсказка Pavlovsky.

dimkadimon
Вы по-русски хорошо читаете? Здесь о чём написано? О построении прямоугольника С^2x(C^2+C)! А вы мне что объясняете?

Кстати, об этом методе я догадалась сама без подсказок (о чём написано выше; читайте тему!). Но вот реализовать метод у меня пока не получается.
Прямоугольники С^2x(C^2+C) я строю, но строю их не по алгоритму теоремы 4.12.
Как достраивать эти прямоугольники, я не знаю.

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

Вам уже понятно, о чём я прошу? Или всё ещё нет?
Если вы по-русски плохо понимаете, хотя бы поменьше делайте цитат. Я по-русски понимаю очень хорошо и мне не нужны ваши цитаты.

-- Пн июн 25, 2012 08:30:54 --

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

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

Кстати, вообще говоря, Pavlovsky нарушил правила конкурса. Он не имел права давать вам явную подсказку.

А можно получить ссылку на правила конкурса и на права участников?

Это вы кому вопрос задаёте?

У нас тут есть один из организаторов конкурса - dimkadimon.
Он, наверное, может ответить на этот вопрос.

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

[Pavlovsky]

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

Решим вспомогательную задачу.Расставим в характеристической строке, квадрата NxN максимально возможное количество символов 1, так чтобы выполнялись условия выше приведенной теоремы для пометки 1. Обозначим это максимально возможное количство единиц F(N).

Лемма о существовании диагонального решения.Диагональное решение G(С,N) не существует, если F(N)<(2N-1)/C

Написал програмульку по вычислению F(N).
N F(N)
9 6
10 7
11 7
16 8
17 9
18 9
25 11
26 11
27 12
28 12

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

Сегодня утром встали трамваи пришлось на работу идти пешком. Во время пешей прогулки пришла такая бредовая идея.

Диагональное решение фактически выглядит так. Через квадрат проводим пучок параллельных прямых. Далее раскрашиваются эти прямые. Но ведь через квадрат не обязательно проводить прямые под углом 45 градусов(диагонали). Можно проводить пучок параллельных прямых под любым углом! Например прямые с соотношением 1:2. Что это дает непонятно.

[Nataly-Mak]

Кстати, вот что здесь писал dimkadimon:

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

Ещё мне кажется что не совсем справедливо обсуждать задачу, а соревноваться по отдельности. Тоесть обсуждать можно и Neil совсем не против, но наверное тогда надо зарегистрировать команду под общим именем. Как вы думаете?

Теперь ему следует зарегистрировать под общим именем команду "dimkadimon - Pavlovsky"

[Pavlovsky]

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

Вот явная подсказка Pavlovsky.

Наталия вы чего добиваетесь? Чтобы я снялся с конкурса? Легко!

[Nataly-Mak]

Ха-ха-ха!
Я добиваюсь, чтобы вас с 8-го места переместили на 2-ое (в одну команду с dimkadimon)!

Да, а процитировала вашу подсказку совсем с другой целью (если вы не поняли, поясняю): объясняла dimkadimon, о чём говорится в этой подсказке.

Кстати, а зачем вы просили прятать подсказку в тег off?
Легко сниметесь с конкурса, а чего тогда бояться?
Я вот ничего не боюсь и всё выкладываю открытым текстом (например, выложила готовое решение С=6, N=31х31).
Потому что сняться с конкурса действительно могу легко!

[Zealint]

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

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

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

Кстати, вообще говоря, Pavlovsky нарушил правила конкурса. Он не имел права давать вам явную подсказку.

А можно получить ссылку на правила конкурса и на права участников?

Это вы кому вопрос задаёте?

У нас тут есть один из организаторов конкурса - dimkadimon.
Он, наверное, может ответить на этот вопрос.

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

А тогда откуда Вы взяли, что здесь такие же правила?

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

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

Я добиваюсь, чтобы вас с 5-го места переместили на 2-ое (в одну команду с dimkadimon)!

Почему с 5-го?

[Nataly-Mak]

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

А тогда откуда Вы взяли, что здесь такие же правила?

1. Нил писал мне в личной переписке, что он является преемником Зиммерманна. Зиммерманн уже сам не в состоянии проводить эти конкурсы и попросил Нила продолжить это дело.
2. См. цитату из сообщения dimkadimon.

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

Я добиваюсь, чтобы вас с 5-го места переместили на 2-ое (в одну команду с dimkadimon)!

Цитата:

Почему с 5-го?

Разве это так важно: с 5-го, с 8-го?
Ну, просто я не помню точно, на каком Pavlovsky месте.
Сейчас пойду посмотрю. Может быть, на 8-ом? Пока исправила 5 на 8

Да, правильно, на 8-ом. Ещё раз повторю: это совсем не существенно - 5-ое, 8-ое, 10-ое... Речь не о том.

[Pavlovsky]

Эх россияне, почто грызетесь аки волки. (с) М.Ломоносов

[Nataly-Mak]

Pavlovsky
это вы о чём? Вас кто-то загрыз во время пешей прогулки?

[Zealint]

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

Эх россияне, почто грызетесь аки волки. (с) М.Ломоносов

Мы не грызёмся : )
Я просто не знал, что существуют правила (нигде об этом не написано), попросил ссылку. Теперь все понятно.

-- Пн июн 25, 2012 08:21:42 --

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

[Pavlovsky]

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

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

Ночью надо спать. А вот решать задачки в уме, скажем в общественном транспорте, интересное занятие и время бежит быстро.