2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 71, 72, 73, 74, 75, 76, 77 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение24.07.2012, 11:48 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #598560 писал(а):
Nataly-Mak в сообщении #598556 писал(а):
возможно, что у меня совсем не такой алгоритм


Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные) пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14. Применяя методику дважды получаем 15 сильноокрашенный прямоугольник (169+2К)х14.


Ух ты - я совсем по другому делал. Из 13-strong 169х14 получил 14-coloring 169х182, а из этого получил 14-coloring 183х183. Ваш метод мне больше нравится.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #598560 писал(а):
Nataly-Mak в сообщении #598556 писал(а):
возможно, что у меня совсем не такой алгоритм


Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14.

Вот именно! 13-сильную раскраску 169х14 имеют все. А вот от неё уже все по-разному пляшут :-)

Nataly-Mak в сообщении #598556 писал(а):
во 2-ом классах.

Цитата:
Дык это , пусть на одну строку, уже лучше F(15)=F(14)+1.

Не поняла.
Ещё раз:
первый класс: C14N183, C15N184
второй класс: C14N184, C15N185

Это у меня. А у вас как?

В третьем классе у меня нерегулярное C14N185, от него C15N186.

-- Вт июл 24, 2012 13:04:32 --

dimkadimon в сообщении #598571 писал(а):
Ух ты - я совсем по другому делал. Из 13-strong 169х14 получил 14-coloring 169х182, а из этого получил 14-coloring 183х183. Ваш метод мне больше нравится.

А я по-третьему делала :-)
Вот и получается, что у всех свой алгоритм.

У меня из 13-strong 169х14 получается 169х196 14-coloring.
И соответственно: из любого прямоугольника C^2x(C+1) strong С-coloring (C=p^k, p - простое, k>=1) получается прямоугольник
C^2x(C+1)^2 (C+1)-coloring.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #598576 писал(а):
первый класс: C14N183, C15N184
второй класс: C14N184, C15N185


второй класс: C14N184, C15N186
третий класс: C14N185, C15N188

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


22/03/08

7154
Саратов
Ага, теперь поняла.
Значит, во втором классе мой результат для С=15 можно чуть улучшить.

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

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


20/01/10
766
Нижний Новгород
Nataly-Mak
Цитата:
Он вот, кстати, до сих пор не вступает в игру :-)
Как вы думаете, почему?
Смотрю и думаю, думаю и смотрю :-) Иногда отвлекаюсь на facebook и др., когда наступает полный тупик.

Pavlovsky
Цитата:
Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные) пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14. Применяя методику дважды получаем 15 сильноокрашенный прямоугольник (169+2К)х14.
Вот до сильной окрашенности так и не добрался :-(, пока ни разу не воспользовался.

Имеются совершенно тривиальные идеи, которые, наверняка, обдумывали большинство участников. Переход от $C$ к $C+1$ требует достройки $2C+1$ строк. Первое $C$ получается достаточно быстро и самыми различными способами - так или иначе требуется некоторое перекрашивание основного квадрата, явно неполноценное, но где же взять полноценное :-) . Рассматривание базовых квадратов дает картинку из $C^2$ маленьких квадратиков $C \times C$, которые путем перестановки строк легко превращаются в маленькие квадратики $(C-1)\times (C-1)$ - это, вроде, дает шанс на реализацию подхода с достраиванием, но шанс ли это?

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

Любопытны пары решений, которые внешне совершенно различные, но фактически основаны на одном методе. Эти "сопряженные" решения представляют интерес, но мало что дают ... пока?

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


22/03/08

7154
Саратов
svb в сообщении #598600 писал(а):
Цитата:
Полагаю у всех алгоритм одинаковый (в т.ч у лидеров). Берем 13 сильноокрашенный прямоугольник 169х14. И путем различных манипуляций (вот тут действительно у всех методы разные) пытаемся получить 14 сильноокрашенный прямоугольник (169+К)х14. Применяя методику дважды получаем 15 сильноокрашенный прямоугольник (169+2К)х14.

Цитата:
Вот до сильной окрашенности так и не добрался :-(, пока ни разу не воспользовался.

Это ещё раз подтверждает, что алгоритмы у всех разные.
Я тоже не строила прямоугольник (169+К)х14 strong 14-coloring в первом и втором классах.

Только в третьем классе начала использовать С-сильные раскраски.
Сначала это у меня получилось с 83х10 10-сильной раскраской, потом перешла к 123х12 12-сильной... Но это уже совсем другая опера :D

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


22/03/08

7154
Саратов
Хорошо мы тут расписали, как находить решения в классах :D

dimkadimon стал третьим конкурсантом, нашедшим решение C10N94.

Pavlovsky
а вы чего отстаёте в четвёртом классе? :wink:

У меня тоже 10-сильная раскраска 84х10 никак не получается :-(
5 ошибок никак не убиваются.

-- Вт июл 24, 2012 19:39:20 --

Положение в группе лидеров мне уже не нравится

Цитата:
1 Artem Karavaev 19.974300 07-11-2012 @ 17:37:19
2 Nick Gardner 19.947100 07-24-2012 @ 16:06:24
3 Alex Chernov 19.941800 07-07-2012 @ 20:56:57
4 Herbert Kociemba 19.926300 07-07-2012 @ 14:29:57

Nick Gardner очень активно продвигается вперёд.
Herbert Kociemba тоже сильный противник.

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

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


22/03/08

7154
Саратов
Любопытный сопутствующий результат - 6 попарно ортогональных обобщённых латинских квадратов 6-го порядка; правда, в них не хватает по 5 чисел:

(Оффтоп)

Код:
1 1 1 1 1 1
2 2 2 2 2 x
3 3 3 3 3 x
4 4 4 4 4 x
5 5 5 5 5 x
6 6 6 6 6 x

2 3 4 5 6 1
1 3 4 5 6 x
1 2 4 5 6 x
1 2 3 5 6 x
1 2 3 4 6 x
1 2 3 4 5 x

3 1 2 4 5 6
1 2 3 5 6 x
2 4 5 6 1 x
5 6 3 2 4 x
3 1 4 6 2 x
4 5 6 1 3 x

4 1 2 3 5 6
2 3 5 6 4 x
5 6 4 1 3 x
3 2 6 4 1 x
1 5 2 3 6 x
4 1 5 6 2 x

5 1 2 3 4 6
3 4 6 5 1 x
5 1 3 2 6 x
1 4 2 6 5 x
4 2 6 5 3 x
2 6 3 4 1 x

6 1 2 3 4 5
4 5 1 2 3 x
3 4 5 6 2 x
6 1 3 4 5 x
2 5 6 4 1 x
1 3 2 6 5 x

Получить 6 таких полных ЛК (без пробелов) невозможно.

Я очень мало в своё время занималась обобщёнными ЛК; статья есть им посвящённая, но в ней очень мало информации, несколько примеров, найденных в чужих статьях, ничего оригинального.
Может быть, после конкурса вернусь к этой статье.

Кстати, приведённый результат перекликается со строкой Pavlovsky для С=6.
Из его строки я получила аналогичный набор попарно ортогональных обобщённых ЛК.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #598868 писал(а):
Может быть, после конкурса вернусь к этой статье.


Надо еще латинскими прямоугольниками заняться! :-)

-- Ср июл 25, 2012 08:30:11 --

svb

Появился ваш единомышленник по конечным полям.
http://infinitesearchspace.dyndns.org/c ... ic-squares
Algebraic approach to monochromatic squares

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #598970 писал(а):
Появился ваш единомышленник по конечным полям.

Ага, у этого единомышленника пока те же самые вопросы без ответов :wink: :

Цитата:
• Есть ли подобный подход в других случаях (C = 6,10, ...)?
• Есть еще один алгебраической структуры, связанные с этой проблемой? Я пытался использовать некоторые группы действий для построения сетей, но я не могу разобраться.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #598970 писал(а):
Надо еще латинскими прямоугольниками заняться! :-)

А представленные мной неполные ЛК 6-го порядка и есть в сущности попарно ортогональные прямоугольники. Отбросьте в моих квадратах последний столбец и получите прямоугольники 6х5.

Получен также весьма интересный набор из 6 попарно ортогональных прямоугольников 5х6.
Это тоже неполные ЛК 6-го порядка, в которых не заполнена последняя строка.
Интересно, что два из этих ЛК обобщённые, а 4 остальных классические.

Наконец, получен набор из 10 попарно ортогональных прямоугольников 5х10.
Любопытные прямоугольнички :-)
Они проедставляют ровно половинки ЛК 10-го порядка. При этом два первых ЛК обобщённые, остальные 8 классические.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #598983 писал(а):
При этом два первых ЛК обобщённые, остальные 8 классические.

Если взять два обобщенных ЛК вида
11111
22222
......
и
123..
123..
....

То все остальные ортогональные ЛК обязаны быть классическими ЛК.

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


22/03/08

7154
Саратов
Ага, так утверждает Холл в своей книге "Комбинаторика" :-)

Кстати, весьма полезная книга. Я её просматривала на английском языке. А недавно узнала, что книга ещё в 1970 г. переведена на русский язык.
Вот ссылка на русское издание книги:
http://flyonmap.com/b/3d1p1m1m_2u._2s1p ... _1970.djvu

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


20/01/10
766
Нижний Новгород
Nataly-Mak
Цитата:
Ага, у этого единомышленника пока те же самые вопросы без ответов :wink: :
Одно из обобщений дало решения для $C=6$, но споткнулось об $C=10$ :-( и это было странно.

Цитата:
Кстати, весьма полезная книга.
Павловский от нее отказался, когда я предложил список.

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


21/02/10
1594
Екатеринбург
svb в сообщении #599020 писал(а):
Павловский от нее отказался, когда я предложил список.


Кто не знает книгу Холла "Комбинаторика"?! Естественно она у меня есть.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 71, 72, 73, 74, 75, 76, 77 ... 130  След.

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



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

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


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

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