2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 20, 21, 22, 23, 24, 25, 26 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение19.06.2012, 07:58 
Аватара пользователя


20/01/10
766
Нижний Новгород
:-)

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #586714 писал(а):
svb в сообщении #586712 писал(а):
Почему только один? Если любой half-mono rectangle рассматривать по модулю и если при этом не получится одноцветный прямоугольник, то, похоже, алгоритм леммы можно применять.

Ну где то так. Так что формулируем Лемму Макаровой-Беляева-Павловского?! :D

Pavlovsky
не примазывайтесь :D третий - лишний.

-- Вт июн 19, 2012 09:19:50 --

Вот эта троица мне нравится:

1 Alex Chernov 19.932400 06-15-2012 @ 20:53:28
2 Nick Gardner 19.899900 06-14-2012 @ 16:35:43
3 Herbert Kociemba 19.864000 06-19-2012 @ 02:05:52

К "джентельменскому" набору, перечисленному Pavlovsky, они добавили ещё кое-что интересненькое :-)

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #586717 писал(а):
третий - лишний

Ну тогда в качестве гуманитарной помощи.

Лемма. Прямоугольник C-coloring допускает C/k репликацию. Если для любых двух строк выполняется условие. Количество одноцветных ячеек в одной колонке этих строк не больше k. И номера этих цветов дают различные остатки при делении на k.

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


20/01/10
766
Нижний Новгород
Pavlovsky в сообщении #586721 писал(а):
Количество одноцветных ячеек в одной колонке этих строк не больше k. И номера этих цветов дают различные остатки при делении на k.
Если цвета по модулю k различны, то их уже не может быть больше k.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #586717 писал(а):
К "джентельменскому" набору, перечисленному Pavlovsky, они добавили ещё кое-что интересненькое

К гадалке не ходи. Берут некое решение NxN и перебором пытаются добавить строку и колонку. Для себя на первые два месяца конкурса я наложил табу на реализацию переборных алгоритмов. Ищу "регулярные" решения.

-- Вт июн 19, 2012 10:45:34 --

svb в сообщении #586726 писал(а):
Если цвета по модулю k различны, то их уже не может быть больше k.

Вы меня в соавторы не берете так что дальше сами. :D

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


20/01/10
766
Нижний Новгород
Я беру, но за вами строгое доказательство :-)

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


21/02/10
1594
Екатеринбург
svb в сообщении #586729 писал(а):
за вами строгое доказательство

А чего тут доказывать? Берем доказательство леммы 4.3 и переписываем его с минимальными правками.
К тому же в конкурсе программистов строгое доказательство утверждений не требуется. Главное чтобы работало.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #586728 писал(а):
К гадалке не ходи. Берут некое решение NxN и перебором пытаются добавить строку и колонку. Для себя на первые два месяца конкурса я наложил табу на реализацию переборных алгоритмов. Ищу "регулярные" решения.

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

Вашу гуманитарную помощь с чем "кушать" надо: с горчицей, с перцем, с хреном, с аджикой, с кетчупом или с каким другим соусом? :D

-- Вт июн 19, 2012 10:51:09 --

svb
после изобретения новой леммы :-)
хочу попросить вас "перевести" вот этот фрагмент статьи:

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

вижу такие разбиения:

|1|2|3|
|6|5|4|

|1|6|2|
|5|4|3|

|1|5|6|
|4|3|2|

|1|4|5|
|3|2|6|

|1|3|4|
|2|6|5|

Здесь участвуют как раз 6 цветов. Не являются ли эти разбиения ключом к алгоритму для C=6 (а также и для C=10,12,14,18,20)?

Перед этим в статье сформулирована теорема. Вот с неё и надо начать. Что это за теорема?

После формулировки теоремы приводятся эти примеры ( для 2n=6 и ещё для 2n=8, это я не скопировала).

Ничего не могу понять с этими разбиениями :cry:
А сильно подозреваю, что они очень важные.

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


22/03/08

7154
Саратов
Кстати, если мой прямоугольник 7х12

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

не strong-(6,2)-coloring, но зато он strong-(6,3)-coloring!

И к нему опять же можно применить лемму, только теперь должен получиться прямоугольник 7Х24 6-coloring. И он действительно получается:

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

Эхма, какой же мне изобрести прямоугольник, чтобы получить 36х36 6-coloring? :D

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #586739 писал(а):
А сильно подозреваю, что они очень важные.
- аналогично. Давайте начнем.Итак,

Теорема 4.4
Пусть $c \ge 2$, тогда
1. Существует раскраска strong c-coloring прямоугольников $
G_{c + 1,m} 
$, где $\[
m = \left( {\begin{array}{{20}c}
   {c + 1}  \\
   2  \\
\end{array}} \right)
\]
$
2. Существует раскраска c-coloring прямоугольников $
G_{c + 1,m} 
$, где $\[
m = c \left( {\begin{array}{{20}c}
   {c + 1}  \\
   2  \\
\end{array}} \right)
\]
$

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


22/03/08

7154
Саратов
Ага, спасибо.

Это вроде понятно.
Там дальше идёт пример для C=5.

1. Существует раскраска strong 5-coloring прямоугольника G6,15;
2. Существует раскраска 5-coloring прямоугольника G6,75.

Верно?

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


20/01/10
766
Нижний Новгород
Пока никак не пойму, как этот пример строить.

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


22/03/08

7154
Саратов
Ну, если вы не поймёте, я тем более не пойму.
Сейчас глянула, там идёт описание (доказательство), но... перевод, сделайте, пожалуйста, перевод :-(

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #585865 писал(а):
Example 4.6

вижу такие разбиения:

|1|2|3|
|6|5|4|

|1|6|2|
|5|4|3|

|1|5|6|
|4|3|2|

|1|4|5|
|3|2|6|

|1|3|4|
|2|6|5|

Здесь участвуют как раз 6 цветов. Не являются ли эти разбиения ключом к алгоритму для C=6 (а также и для C=10,12,14,18,20)?


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

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


20/01/10
766
Нижний Новгород
Похоже, что рассматриваются колонки с различными вариантами расположения цвета 5 - этих вариантов, конечно, 15. Остальные цвета просто идут по порядку. Как там написано, реальный порядок этих цветов не имеет значения. А дальше идет доказательство правильности раскраски, которому мы искренне верим, т.к. оно нам не очень и нужно в силу своей очевидности :-) .

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 20, 21, 22, 23, 24, 25, 26 ... 130  След.

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



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

Сейчас этот форум просматривают: Mikhail_K


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

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