2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 89, 90, 91, 92, 93, 94, 95 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение19.08.2012, 21:44 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Zealint в сообщении #607678 писал(а):
Я могу за него рассказать.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 05:27 
Заблокирован
Аватара пользователя


22/03/08

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

Цитата:
9 Kendrick Boyd 19.745800 08-20-2012 @ 00:30:32


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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 08:09 


26/01/10
959
Nataly-Mak в сообщении #607746 писал(а):
Так расскажите, если можете :D

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 09:30 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 12:40 


26/01/10
959
Nataly-Mak в сообщении #607915 писал(а):
Ну, те результаты, что он выложил, уже почти ни для кого не являются секретом, это ведь, по-моему, не выше первого класса результаты.
Так что мог бы и рассказать, как он получил эти результаты.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 13:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ещё раз о классах

Просмотрела тему. Боже мой, какими же смешными сейчас кажутся все мои мучения в поисках решений 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. Очевидно до смешного :D

Код:
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 писал(а):
Так что можно не ждать, а прочитать решение там.

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 14:52 


26/01/10
959
Nataly-Mak в сообщении #608022 писал(а):
Да зачем мне читать какую-то книжку? Мне интересно, как получил решения конкретный человек. При этом мне не нужны сами эти решения, я их уже получила. Просто интересно, как он работал, вот и всё.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 18:58 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 21:04 
Заблокирован
Аватара пользователя


22/03/08

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

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

-- Пн авг 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 у него тоже есть, но он не засылал.

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.08.2012, 22:17 
Аватара пользователя


20/01/10
766
Нижний Новгород
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-х цветной закраски уже достаточно.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.08.2012, 05:28 
Заблокирован
Аватара пользователя


22/03/08

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

Ждём :wink:

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.08.2012, 07:20 


26/01/10
959
Nataly-Mak в сообщении #608310 писал(а):
Вот опять "у него есть" :D Как получил?

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.08.2012, 07:48 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.08.2012, 08:20 


26/01/10
959
Nataly-Mak писал(а):
Да, и если вы с Антоном в контакте, пригласите его в тему, пусть он сам нам рассказывает :D
Информация от первого лица всегда более солидна.

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

Nataly-Mak в сообщении #608445 писал(а):
В статье утверждается следующее ...

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.08.2012, 08:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Zealint в сообщении #608448 писал(а):
Nataly-Mak писал(а):
Да, и если вы с Антоном в контакте, пригласите его в тему, пусть он сам нам рассказывает :D
Информация от первого лица всегда более солидна.

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

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

Nataly-Mak в сообщении #608445 писал(а):
В статье утверждается следующее ...

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 89, 90, 91, 92, 93, 94, 95 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group