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

[Nataly-Mak]

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

Я могу за него рассказать.

Так расскажите, если можете
Интересно не то, что у него ещё есть, а как он получил свои результаты, по каким алгоритмам. И так быстро!

[Nataly-Mak]

Появился реальный кандидат в группу третьеклассников:

Цитата:

9 Kendrick Boyd 19.745800 08-20-2012 @ 00:30:32

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

[Zealint]

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

Так расскажите, если можете

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

[Nataly-Mak]

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

Кстати, прислал письмо один товарищ с форума ПЕН. Пишет, что у него алгоритм построения для С простых не такой, как обсуждался в этой теме. Прислал решение C13N169. Я посмотрела его в программе Эда, действительно, совсе не такая раскраска, как у меня.
Предполагаю, что это получено по алгоритму, который недавно Pavlovsky показал: заполнение матрицы унитарными ЛК. Для простых С этот алгоритм легко срабатывает. И для степеней простых тоже срабатывает, хотя посложнее немного.
А вот для других С - увы! То есть какие-то результаты тоже получаются, но они очень низкие.

Впрочем, Pavlovsky писал:

Цитата:

Легко убедится, что полученный квадрат эквивалентен квадрату построенному из сильноокрашенного прямоугольника, с последующей репликацией по лемме 4.3.

Это он приводил пример для С=11. Сейчас посмотрела на построенную им раскраску 121х121; да, она аналогична той, что прислал мне товарищ с ПЕН для С=13.

В общем, эти два метода для С=p^k (k>=1, p - простое) дают эквивалентные результаты. Ничего нового.

[Zealint]

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

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

Это секрет для тех, кто ниже и чуть выше Антона в рейтинге (Антон даже C3N10 и C4N18 пока не засылал). Так что низя... Терпеливо ждём. Тов. Pavlovsky, кстати, давал ссылку на книгу, где обсуждаются проективные плоскости, в том числе дезарговы. Так что можно не ждать, а прочитать решение там.

[Nataly-Mak]

Ещё раз о классах

Просмотрела тему. Боже мой, какими же смешными сейчас кажутся все мои мучения в поисках решений 1,2,3 классов!

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

Буду показывать на простеньком примере, для С=3 (простое число).

Самый первый класс - нулевой.
Надо построить 3-сильную раскраску 9х4.
И тут всё прямо тривиально. Не надо никаких разбиений!
Забыла Холла, забыла его ортогональные таблицы. А ведь это и есть С-сильные прямоугольники!
Берём два ортогональных ЛК 3-го порядка (классичесих), добавляем к ним ещё два квадрата, один из одиниковых строк, второй из одинаковых столбцов. Всё! Больше ничего не надо, никаких разбиений.

1 1 1
2 2 2
3 3 3

1 2 3
2 3 1
3 1 2

1 2 3
3 1 2
2 3 1 

1 2 3
1 2 3
1 2 3

Элементарно составляем из этих попарно ортгональных ЛК 3-сильную раскраску 9х4:

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

выполняем расширение по теореме 4.3 и получаем решение 9х12 3-coloring.

Теперь надо осуществить переход к 4-цветным раскраскам.
Берём исходную 3-сильную раскраску 9х4 и добавляем к ней строку

4 4 4 4

всё, получена 4-сильная раскраска 10х4. Очевидно до смешного

1,1,1,1,
1,2,2,2,
1,3,3,3,
2,2,3,1,
2,3,1,2,
2,1,2,3,
3,3,2,1,
3,1,3,2,
3,2,1,3,
4,4,4,4

Выполняем расширение по теореме 4.3 и получаем раскраску 10х16 4-coloring.
Осталось добавить к этой раскраске 4 строки, тоже элементарно, поскольку исходный прямоугольник у нас 4-сильно окрашенный. В результате готово решение 14х16 4-coloring:

16,14,A,A,A,A,B,B,B,B,C,C,C,C,D,D,D,D,A,B,B,B,B,C,C,C,C,D,D,D,D,A,A,A,A,C,C,C,B,D,D,D,C,A,A
,A,D,B,B,B,B,B,C,A,C,C,D,B,D,D,A,C,A,A,B,D,B,C,A,B,C,D,B,C,D,A,C,D,A,B,D,A,B,A,B,C,C,B,C,D,
D,C,D,A,A,D,A,B,C,C,B,A,D,D,C,B,A,A,D,C,B,B,A,D,C,A,C,B,D,B,D,C,A,C,A,D,B,D,B,A,C,B,A,C,D,C
,B,D,A,D,C,A,B,A,D,B,D,D,D,D,A,A,A,A,B,B,B,B,C,C,C,C,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,B,C,D,
A,B,C,D,A,B,C,D,A,B,C,D,A,C,D,A,B,C,D,A,B,C,D,A,B,C,D,A,B,D,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C

В этом решении содержатся решения 1-го и 2-го классов: 13х13 и 14х14 4-coloring.

Остался третий класс.
К 4-сильной раскраске 10х4 надо добавить ещё одну строку и получить 4-сильную раскраску 11х4.
Вот эта процедура у меня не является очевидной и регулярной. Для больших С я изрядно помучилась с добавлением второй строки.
Ну, для рассматриваемого примера всё просто. Добавляем строку

1 2 3 4

и исправляем возникшие ошибки заменой некоторых элементов в исходной раскраске на цвет 4.

Вот готовая 4-сильная раскраска 11х4:

4,11,A,A,A,A,D,B,B,B,D,C,C,C,B,D,C,A,B,C,A,B,B,A,B,C,C,C,B,A,C,A,C,B,C,B,A,C,D,D,D,D,A,B,C,D

Из этой раскраски получаем решение 3-го класса - 15х15 4-coloring.

Было бы весьма интересно узнать, как выполнять последнюю процедуру - добавление второй строки, скажем, для С=17, по строгой схеме, без привлечения перебора.
То есть мы уже имеем 18-сильную раскраску 290х18 (взяли 17-сильную раскраску 289х18 и добавили к ней строку 18,18,...,18).Теперь надо легко и просто получить 18-сильную раскраску 291х18. Как это сделать легко и просто? У меня это было совсем не легко и не просто. И точно так же долго мучилась с 20-сильной раскраской.

-- Пн авг 20, 2012 14:15:57 --

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

Так что можно не ждать, а прочитать решение там.

Да зачем мне читать какую-то книжку? Мне интересно, как получил решения конкретный человек. При этом мне не нужны сами эти решения, я их уже получила. Просто интересно, как он работал, вот и всё.

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

[Zealint]

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

Да зачем мне читать какую-то книжку? Мне интересно, как получил решения конкретный человек. При этом мне не нужны сами эти решения, я их уже получила. Просто интересно, как он работал, вот и всё.

Для $C+1$ цветов он взял известные проективные плоскости порядка $C^2+C+1$. Удаление одного цвета дает решения для степеней простых чисел. 6-36 у него тоже есть, но он не засылал.

[General]

Завлекла меня-таки Наталия :) Задача, и вправду, очень интересная. Вряд ли смогу полноценно поучаствовать, но в блоге написал, может, ещё кто подключится.

[Nataly-Mak]

General
вы обладаете чудесным умением рассказать о задаче кратко и интересно.
Очень понравился ваш рассказ! Спасибо.

И подключайтесь к участию
Ещё вполне можно успеть ввести результаты. К тому же, их можно вводить и после окончания официальной части конкурса.

-- Пн авг 20, 2012 22:10:44 --

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

Для $C+1$ цветов он взял известные проективные плоскости порядка $C^2+C+1$. Удаление одного цвета дает решения для степеней простых чисел. 6-36 у него тоже есть, но он не засылал.

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

В статье написано, что вопрос существования проективных плоскостей для С=10,15 остаётся открытым, для С=21 уже однозначно не существует.

Можно предположить, что alexBlack нашёл проективную плоскость (или ещё нечто подобное) для С=15,21.

-- Пн авг 20, 2012 22:28:18 --

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

6-36 у него тоже есть, но он не засылал.

Вот опять "у него есть" Как получил?
Здесь рассказли о своих решениях C6N36 svb, Pavlovsky, я давным-давно рассказала.

Кстати, это было так давно, когда я ещё даже не знала, что к раскраске, полученной из С-сильного прямоугольника расширением, элементарно можно добавить С строк.
Нашла 6-сильную раскраску 30х6 и даже 31х6, выполнила расширение, получила решение 31х36 6-coloring. Дальше начались мучения Достраивала до квадрата 36х36 в программе Эда вручную! А всё тривиально: приписать 6 строк и решение готово. Можно было выполнять расширение прямоугольника 30х6, этого вполне достаточно, к полученной раскраске 30х36 приписываем 6 строк и всё готово.

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

[svb]

Nataly-Mak

Цитата:

Можно предположить, что alexBlack нашёл проективную плоскость (или ещё нечто подобное) для С=15,21.

Эти два случая очень интересны. В рамках достраивания должен получаться результат $c(c+1)+c+2$, т.е. для $c=19$ должен быть результат 401. Одна единичка за alexBlack

-- Пн авг 20, 2012 22:52:18 --

Кстати, немного продолжу. Если закрывать дырки базовой конфигурации, то 2 новых цвета позволяют сразу получить закраску конфигурации 4x4, что дает результат $c(c+1)+6$, после простейших вывертов можно задействовать 3 цвета для закраски дыр конфигурации 5x5, что дает результат $c(c+1)+7$, но хотелось бы использовать хотя бы 9x9 или 10x10, что дало бы $c(c+1)+12$. 4-х цветная закраска позволяет закрасить 18x18, или $c(c+1)+20$ для $c=19$. Для $c=13$ 4-х цветной закраски уже достаточно.

Я ничего не могу до окончания конкурса говорить о базовой конфигурации Времени катастрофически не хватает, почка еще разболелась , но моим мозгам конкурс явно пошел на пользу.

[Nataly-Mak]

К тайному алгоритму alexBlack прибавился тайный алгоритм svb.

Ждём

[Zealint]

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

Вот опять "у него есть" Как получил?

Построил проективную плоскость. Скорее всего почти такую же, как Pavlovsky, когда ссылался на ту книжку.

[Nataly-Mak]

В статье утверждается следующее:

Цитата:

Остается невыясненным (1983) вопрос, для каких значений псуществует П. п. Р(2, п). Доказано существование конечной П. п., порядок к-рой есть степень простого числа (см. [4]). Доказано также (см. [5]) отсутствие П. п. Р(2, п).для широкого класса чисел: если п сравнимо с 1 или 2 по модулю 4 и если в разложении этого числа на простые множители встречается в нечетной степени хотя бы одно простое число, сравнимое с 3 по модулю 4, то Р(2, п).не существует; таковы, напр., n=6, 14, 21, 22, .... Вопрос относительно n=10, 12, 15, 18, ... остается открытым.

Если я правильно понимаю, здесь говорится о несуществовании проективной плоскости для n=6. Хотя... здесь говорится о какой-то проективной плоскости Р(2,п) (?)

Да, и если вы с Антоном в контакте, пригласите его в тему, пусть он сам нам рассказывает
Информация от первого лица всегда более солидна.

[Zealint]

Nataly-Mak писал(а):

Да, и если вы с Антоном в контакте, пригласите его в тему, пусть он сам нам рассказывает
Информация от первого лица всегда более солидна.

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

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

В статье утверждается следующее ...

Наверное, не стоит путать конечную ПП и классическую ПП.

[Nataly-Mak]

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

Nataly-Mak писал(а):

Да, и если вы с Антоном в контакте, пригласите его в тему, пусть он сам нам рассказывает
Информация от первого лица всегда более солидна.

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

Я ничего не думаю. Нет для этого данных у меня, чтобы думать
Ну, вот что нет времени послать решения, в это совсем не верю. Для этого надо максимум 10 минут времени (для 10-15 решений). К тому же, как вы утверждаете, он активно работает над дезарговыми плоскостями. Значит, время у него всё-таки есть.

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

В статье утверждается следующее ...

Цитата:

Наверное, не стоит путать конечную ПП и классическую ПП.

Согласна. Я в этом ещё не разобралась как следует.
Так значит, Антон построил некую проективную плоскость для n=6.
Так и запишем

Вообще я не удовлетворена вашими рассказами. Да и как вы можете подробно рассказать то, что делал другой человек? Это непонятно.
Раз добавить больше нечего, закроем вопрос.