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

[Pavlovsky]

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

А сколько должно быть двоек? Так же?

1 и 2 вместе должно быть не меньше 2*135,2 и так далее.

-- Вс июл 08, 2012 17:15:50 --

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

Пока не поняла.Это как? В квадрате 4х4 можете показать такую расстановку единичек, что двойки уже не войдут?

Для начала надо определьтся во сколько цветов вы хотите выкрасить ваш квадрат 4х4. От этого (по формуле N*N/C) зависит сколько 1, 2 надо расставить.

-- Вс июл 08, 2012 17:21:12 --

Например мы хотим расскрасить квадрат 4х4 в два цвета. 4*4/2=8

1 1 x x
x 1 1 x
x x 1 1
1 x x 1

Мы расставили 8 единичек все хорошо. Нам повезло есть возможность вставить и 8 двоек.

1 1 x 1
x 1 1 x
x x 1 1
х x x 1

А вот в этом случае 8 двоек уже не вставишь.

-- Вс июл 08, 2012 17:24:58 --

1 1 x х
1 х 1 1
x 1 1 х
х 1 x 1

А вот так втолкнули аж 9 единичек. Значит двоек нам надо втолкнуть всего 7.

-- Вс июл 08, 2012 17:29:05 --

Такой доход использовали немцы. Квадрат 18х18 они собирали из квдратиков 6х6. А квдраты 6х6 они строили подобным образом.

[Nataly-Mak]

Спасибо. Теперь всё понятно.

-- Вс июл 08, 2012 17:02:00 --

Идея смешанного достраивания

Я писала об этой идее, но вряд ли кто-нибудь обратил на неё внимание.

Немного истории. Идея смешанного достраивания сослужила мне хорошую службу в построении пандиагональных квадратов из простых чисел по алгоритму Россера. Кто в теме, тот знает. Там надо сначала построить примитивный квадрат из простых чисел. Этот квадрат тоже можно строить методом достраивания. Однако чистое достраивание (то есть заполнение квадрата только простыми числами) у меня шло очень туго. Тогда я применила смешанное достраивание, то есть разрешила не простые числа, начиная с некоторой строки и некоторого столбца. Строила таким обазом очень большую прямоугольную матрицу, потом делала из неё выборку матрицы, состоящей только из простых чисел. На этом форуме обсуждалась и задача, как автоматизировать выборку.
Et Cetera сделал для этой процедуры отличную программу.

Показываю примитивный пример смешанного достраивания в задаче по раскраске.
Есть квадрат 8х8, раскрашенный в 3 цвета, в нём 3 ошибки:

8,8,A,A,C,B,C,B,A,C,C,C,A,B,B,A,A,B,B,C,A,A,B,C,C,C,B,B,C,A,B,A,C,A,A,B,B,C,A,A,C,B,C,C,C,A,A
,B,A,B,B,A,B,B,C,A,C,A,C,B,A,C,C,B,B,A

Удаляем первый столбец (слева) и четвёртую строку (сверху); получаем квадрат 7х7, раскрашенный в 3 цвета уже без ошибок:

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

Не знаю, может ли что-то дать эта идея, но попробовать можно.

-- Вс июл 08, 2012 17:23:34 --

Pavlovsky
мне пример с 9 единичками очень понравился.

Итак, вы утверждаете, что для квадрата 4х4, раскрашенного в 2 цвета, количество единичек не должно быть меньше 8.

А если так расставить единички:

x x 1 1
x 1 x x
1 x x 1
1 x 1 x

Здесь ведь только 7 единичек. Однако расстановка годится. Дальше вставляем 9 двоек и всё ОК!

[Pavlovsky]

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

[Nataly-Mak]

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

Следовательно, и в квадрате 26х26 в начальной расстановке единичек может быть меньше 135. Или нет?

А что-то у меня на конкурсе не открывается страница рейтинга участников.
Там появился новый участник - Виктор Димитриев, и вот на нём что-то сбойнуло.

[Nataly-Mak]

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

Такой подход использовали немцы. Квадрат 18х18 они собирали из квдратиков 6х6. А квдраты 6х6 они строили подобным образом.

Да, похоже на то.

Вот посмотрите на правый верхний подквадрат 6х6 в интернетовском решении C4N18:



Если считать единичками цвет А, то единичек всего 7 штук. Если далее цвет В считать двойками, двоек 11 штук. А вот вместе единичек и двоек как раз 18 штук.

Да, но как они добились того, что все полученные подквадраты 6х6, собранные в квадрат 18х18, не дают ошибок?

Ну, вот и имеем идею алгоритма для построения решения С5N26: строить 4 подквадрата 13х13 по методу немцев. Всё-таки квадраты 13х13 строить легче, чем целый квадрат 26х26. Только надо ещё выяснить, как правильно строить подквадраты, чтобы они потом хорошо собрались в квадрат 26х26.

-- Вс июл 08, 2012 22:03:32 --

Два подквадрата 13х13 5-coloring уже построила они прекрасно уживаются в квадрате 26х26:



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

А куда народ подевался? Все, наверное, усиленно думают над задачей, а я только думать мешаю

[svb]

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

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

Следовательно, и в квадрате 26х26 в начальной расстановке единичек может быть меньше 135. Или нет?

Или нет. При договоренности такой перенумеровки, что 1 не меньше любого другого цвета. В вашем примере вы имеете возможность так перенумеровать, что 1 будет 9.

[Nataly-Mak]

svb в сообщении #593673 писал(а):

В вашем примере вы имеете возможность так перенумеровать, что 1 будет 9.

Это и ёжику понятно
Я же написала: "Перенумеровать - да".

Тогда не будем обозначать цвета числами.
Будем просто говорить: расставляем первый цвет, он должен занимать не менее N^2/C ячеек.
Далее расставляем второй цвет; два первых цвета вместе должны занимать не менее 2*N^2/C ячеек.
Ну, или же сразу договоримся о договорённости

Вчера попробовала расставить первый цвет в квадрате 26х26. При простейшей диагональной раскраске закрасились всего 130 ячеек.
Наверное, не так просто это сделать.
Это притом, что я ещё ничего не проверяла, как там будет добавляться второй цвет.

Pavlovsky
Может, зря вы думаете, что можете расставить первый цвет даже в квадрате 28х28. Попробуйте-ка!

[Pavlovsky]

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

Следовательно, и в квадрате 26х26 в начальной расстановке единичек может быть меньше 135. Или нет?

Обзначим K(i) количество чисел i в решении.
Будем искать решение для которого верно K(1)>=K(2)>=K(3)... Очевидно, что при таком допущении мы ничего не теряем. Если решение существует оно будет найдено.

-- Пн июл 09, 2012 09:20:16 --

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

1 и 2 вместе должно быть не меньше 2*135,2 и так далее.

Немного попутал. Должно быть так:
K(1)>=N*N/C
K(2)>=M1/(C-1), где M1 количество свободных ячеек после заполнения квадрата единичками.
K(3)>=M2/(C-2), где M2 количество свободных ячеек после заполнения квадрата единичками и двойками.
и так далее.

[Nataly-Mak]

Методом тыка - первый цвет в квадрате 26х26:



Как уже говорила, простейшая диагональная раскраска заполняет 130 ячеек. Мало!

-- Пн июл 09, 2012 08:25:20 --

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

Немного попутал. Должно быть так:
K(1)>=N*N/C
K(2)>=M1/(C-1), где M1 количество свободных ячеек после заполнения квадрата единичками.
K(3)>=M2/(C-2), где M2 количество свободных ячеек после заполнения квадрата единичками и двойками.
и так далее.

Имеется в виду целая часть выражений, если не делится нацело?

[Pavlovsky]

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

Как уже говроила, простейшая диагональная раскраска заполняет 130 ячеек. Мало!

Как видите алгоритм работает! Пока не найдете решение с 136 единичками или более, двигаться дальше нет смысла.

[Nataly-Mak]

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

Как видите алгоритм работает! Пока не найдете решение с 136 единичками или более, двигаться дальше нет смысла.

Пока ничего не вижу

[Pavlovsky]

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

Имеется в виду целая часть выражений, если не делится нацело?Например, для С5N26K(1)>=135или K(1)>=136?

Зачем целая часть? Естественно K(i) целое. Но ведь неравенство K(1)>=135,2 решаемо в целых числах. K(1)=136,137 и так далее.

[Nataly-Mak]

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

[Pavlovsky]

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

Ну, вот и имеем идею алгоритма для построения решения С5N26: строить 4 подквадрата 13х13 по методу немцев. Всё-таки квадраты 13х13 строить легче, чем целый квадрат 26х26.

Квадрат 13х13 слишком большой. Лучше искать решение 28х28. Его можно строить из квдаратов 7х7.

[Nataly-Mak]

А вы поняли, как надо эти подквадраты 7х7 строить? Я пока не поняла.

Вот для C3N9 всё очень просто:



С ходу заполнила цветом А 27 ячеек; далее цветом В тоже 27 ячеек. И осталось заполнить цветом С.

Подквадраты 7х7 надо раскрашивать в 5 цветов.
Получается, K(1)>=9,8, то есть не меньше 10 единичек надо в этот подквадрат впихнуть.
Но даже если удастся построить первый подквадрат 7х7 (а это, скорее всего, удастся), как строить следующий, чтобы он не вступал в конфликт с первым подквадратом?

Ах! А цвет С и не вписывается в оставшиеся 27 ячеек
Не так всё просто, оказывается.

Вспомнила, диагональное решение C3N9 приводил svb.
Посмотрела, каждый цвет в этом решении занимает 27 ячеек.