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

[Nataly-Mak]

Подскажите, пожалуйста, как копировать подквадраты.

Вот выделила подквадрат 10х10, мне теперь надо его скопировать в другое место, никак не получается.
Вижу кнопку Copy, а как использовать её, не знаю.

[Zealint]

Нажмите кнопку Copy, потом выделите квадрат, в который нужно скопировать и нажмите кнопку Paste.

[Nataly-Mak]

Спасибо. Получилось.

[Zealint]

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

То есть диагональные решения C=16, N=100x100 и C=15, N=100x100 строятся элементарно (по вашей программе). А диагональное решение C=14, N=100x100 пока не нашлось.

Именно так, C=14 до сих пор ищется.

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

Разумно сохранять симметрию относительно главной диагонали большого квадрата, вариантов и так слишком много. Можно рассматривать "сильную диагональность", когда все маленькие квадраты одинаковы в своей диагонали - далеко не факт, что это невозможно, но перебор сильно сокращается. А можно и ослабить это требование - эксперименты покажут.

Сильная диагональность у меня в одном из решений для C=6, 36x36. Точнее, подквадрат 30x30 сильно диагональный, а окаймление Г-образное. Но вот для С=7 перебор уже работает медленно. Попробую дождаться, но мне кажется, что нужно перебирать какие-то особенные перестановки, а не все.

[Nataly-Mak]

Метод подаёт надежды



Интересный момент: удивительно быстро "убиваются" ошибки.

Этим методом могу попробовать составить прямоугольник 100х20 10-coloring. Но 10-coloring недостаточно, надо усилить раскраску в этом прямоугольнике для дальнейшего применения леммы 4.3.

Zealint
а у вас есть такая программа, которая может доработать прямоугольник 10-coloring до более сильной раскраски?
Более сильная - это значит не strong-(10,2)-coloring, как требуется в лемме 4.3, а с менее жёсткими требованиями: могут повторяться не только цвета (1,2) в левых и правых вершинах внутренних прямоугольничков, но и все другие цвета разной чётности.

Если прямоугольник 100х20 с такими свойствами составить удастся, тогда к нему можно применить лемму 4.3 и получить квадрат 100х100 10-coloring.

Дарю идею
Правда, не гарантирую, что она реализуема.

[Zealint]

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

[Nataly-Mak]

Можно попытаться.
Мне так не кажется, что перебор в прямоугольнике 100х20 будет сложнее перебора в квадрате 100х100.

Хочу попробовать составить прямоугольник 100х20 10-coloring в программе Эда.

-- Чт июн 28, 2012 15:20:08 --

Прямоугольник 50х20 10-coloring составился в два счёта:

(Оффтоп)

20,50,A,B,C,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,J,B,A,E,I,C,B,G,I,F,E,B,A,F,I,D,C,H,J,G,E,B,E,A,F,J,D
,C,I,A,G,C,F,B,G,B,E,D,I,B,H,D,H,F,A,G,B,E,E,I,C,D,I,G,A,H,B,F,E,J,C,E,C,J,G,A,H,B,F,E,B,F,D,J,H
,A,I,C,G,F,B,E,C,D,B,I,J,I,C,G,G,F,E,E,B,I,A,A,D,H,G,F,H,D,E,B,I,A,B,D,H,G,H,F,F,C,J,A,B,E,I,G,J,I
,E,F,C,A,J,B,E,H,A,I,E,G,D,B,C,C,F,I,G,B,I,E,G,D,B,A,D,J,G,B,J,F,H,E,C,A,D,I,D,H,C,B,F,H,E,D,J,A,
E,H,C,B,G,I,F,E,A,A,B,C,D,E,F,G,H,I,A,J,A,B,C,D,E,F,G,H,I,B,B,F,I,E,C,I,A,A,E,A,J,E,H,C,B,G,I,F,D
,C,F,A,G,J,E,D,I,B,I,B,E,J,F,J,D,C,H,A,G,D,J,G,B,H,B,G,E,J,C,E,H,F,J,G,A,E,D,I,B,E,E,J,H,A,I,C,G,F
,B,D,C,I,H,C,H,B,G,F,A,G,D,E,B,J,A,C,D,H,H,E,B,D,A,I,J,I,C,G,F,H,I,E,F,D,J,A,B,E,J,F,G,C,E,C,I,J,
A,D,H,I,J,J,E,G,D,B,A,C,F,G,I,H,F,F,C,B,J,B,E,D,G,B,J,F,I,E,D,A,D,I,H,C,I,E,G,E,B,J,C,J,H,H,C,C,H,
I,I,E,A,I,D,G,B,A,F,H,E,E,J,B,C,D,E,F,G,B,I,J,A,E,F,G,H,I,J,A,B,C,D,C,B,G,J,F,D,I,B,J,G,F,E,J,C,H,
G,B,D,A,I,D,H,B,H,A,F,E,J,C,I,G,J,E,A,D,I,I,C,F,B,E,J,H,B,I,C,G,F,A,D,I,C,A,E,B,F,J,I,D,G,F,E,A,A,
B,J,D,H,G,C,I,H,D,B,E,C,G,A,J,F,G,D,H,C,B,B,A,E,I,H,J,G,I,F,C,F,G,J,D,A,H,I,E,H,F,B,B,D,F,J,A,B,
H,J,G,D,E,F,I,C,I,A,J,F,I,E,C,B,D,G,B,D,C,I,A,H,F,E,G,J,J,H,C,A,G,J,F,D,B,E,C,A,F,D,J,B,I,G,E,H,A,
F,I,D,C,H,A,G,E,B,D,I,B,G,F,A,C,J,H,E,C,D,G,H,H,H,I,J,A,B,H,I,J,A,B,C,D,E,F,G,D,C,H,A,F,E,J,B,I,
G,I,H,C,F,A,J,E,G,D,B,E,H,C,I,B,G,F,A,D,J,J,C,H,D,G,B,A,F,I,E,F,A,I,C,J,D,H,G,B,E,A,F,D,H,E,I,C,B
,G,J,G,F,B,J,C,A,E,I,H,D,B,A,G,E,H,F,J,D,C,I,H,E,G,D,A,C,B,F,J,I,C,J,B,I,F,H,G,A,E,D,I,J,F,H,E,B,C
,D,G,A,D,E,A,C,J,G,H,I,B,F,J,B,A,G,I,F,D,C,E,H,F,G,F,B,D,A,I,H,J,C,A,I,D,B,H,J,G,E,C,F,G,D,I,G,C,
E,B,J,H,A,B,G,J,E,D,I,A,H,F,C,H,B,E,J,I,D,F,C,A,H,D,E,F,G,H,I,J,A,B,C,C,D,E,F,G,H,I,J,A,B,E,D,I,B
,G,F,A,C,J,H,D,C,H,A,F,E,J,B,I,G,F,I,D,J,C,H,G,B,E,A,E,H,C,I,B,G,F,A,D,J,G,B,J,D,A,E,I,H,C,F,F,A,I
,C,J,D,H,G,B,E,H,G,C,A,D,B,F,J,I,E,G,F,B,J,C,A,E,I,H,D,I,F,H,E,B,D,C,G,A,J,H,E,G,D,A,C,B,F,J,I,J,
A,G,I,F,C,D,E,H,B,I,J,F,H,E,B,C,D,G,A,A,C,B,H,J,G,E,D,F,I,J,B,A,G,I,F,D,C,E,H,B,J,E,C,I,A,H,F,D,G
,A,I,D,B,H,J,G,E,C,F,C,H,A,F,E,J,B,I,G,D,B,G,J,E,D,I,A,H,F,C

[Pavlovsky]

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

Хочу попробовать составить прямоугольник 100х20 10-coloring

Как строить strong-(10,2)-coloring прямоугольник как по версии Леммы 4.3, так и усиленные нигде не написано. Надо думать самому. У меня это в планах записано. Но идей у меня много, а я один. Не знаю когда соберусь порыть в этом направлении.

-- Чт июн 28, 2012 16:22:29 --

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

Прямоугольник 50х20 10-coloring составился в два счёта:

Осталось добавить еще 50 строк.

[Nataly-Mak]

Pavlovsky
Думаю, что и прямоугольник 100х20 10-coloring получится.
Но, как я уже сказала, этого мало. Надо прямоугольник дорабатывать до версии леммы Макаровой-Беляева. В этом сложность. Удастся доработать - квадрат 100х100 будет в кармане.

[Zealint]

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

Думаю, что и прямоугольник 100х20 10-coloring получится.

Он строится прямо в голове и без особых усилий. Но только сделать из него подходящий по лемме мне кажется нереально. А строить подходящий с нуля тоже. Несмотря на кажущуюся простоту.

-- Чт июн 28, 2012 17:01:04 --

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

Сильная диагональность у меня в одном из решений для C=6, 36x36. Точнее, подквадрат 30x30 сильно диагональный, а окаймление Г-образное. Но вот для С=7 перебор уже работает медленно. Попробую дождаться, но мне кажется, что нужно перебирать какие-то особенные перестановки, а не все.

Если брать только циклические перестановки, то для C=7 решение строится мгновенно. Зато для C=8 его уже не существует. Пробовал всякие близкие к циклическим перестановки. Тоже безрезультатно.

[Nataly-Mak]

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

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

Думаю, что и прямоугольник 100х20 10-coloring получится.

Он строится прямо в голове и без особых усилий.

Да? А пример можете привести?
И алгоритм, как в голове строится, если, конечно, не жалко

Цитата:

Но только сделать из него подходящий по лемме мне кажется нереально.

Ну, то, что вам кажется, ещё не факт

Кроме того, прямоугольников 100х20 10-coloring можно настроить море. Какой-то вдруг и доработается до подходящего к лемме.
Плюс ко всему: можно и с нуля начать построение именно прямоугольника 100х20, подходящего к лемме! Ничего особо сложного здесь нет, требования к прямоугольнику довольно слабые. И не исключено, что он найдётся и довольно быстро.

Я здесь приводила прямоугольник 50х10 strong 10-coloring из 50 непересекающихся комбинаций.
Тоже вроде сложно построить, однако строится.
До сих пор не знаю ответ на вопрос: является ли количество 50 максимальным для таких непересекающихся перестановок.
Почему только 50? Как доказать, что больше нет?
Например, из чисел 1,2,3,...6 у меня получился набор из 31 непересекающихся комбинаций. Не исключено, что существует и набор из 36 таких комбинаций. Никто полный перебор пока не сделал.

dimkadimon приводил набор из 32 непересекающихся комбинаций чисел 1,2,3,...,10 и утверждал, что искать такие комбинации довольно легко.
Могу предположить, что он нашёл своё решение C=10, N=93x93 именно таким методом (потому что алгоритм для C=p^k+1 он тогда ещё не знал!)

А теперь допустим, что непересекающихся комбинаций из чисел 1,2,3,...,10 существует 100 штук. Тогда квадрат 100х100 10-coloring получается элементарно из этого набора по базовому алгоритму №1.
Так реально или нереально построить прямоугольник 100х10 strong 10-coloring?
Вам как кажется?

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

Сильная диагональность у меня в одном из решений для C=6, 36x36. Точнее, подквадрат 30x30 сильно диагональный, а окаймление Г-образное. Но вот для С=7 перебор уже работает медленно. Попробую дождаться, но мне кажется, что нужно перебирать какие-то особенные перестановки, а не все.

Цитата:

Если брать только циклические перестановки, то для C=7 решение строится мгновенно. Зато для C=8 его уже не существует. Пробовал всякие близкие к циклическим перестановки. Тоже безрезультатно.

Если я правильно понимаю, "сильная диагональность" - это когда все подквадраты СхС в одной диагонали одинаково окрашены. Правильно понимаю?

Тогда "сильная диагональность" для С простых получается элементарно без всякого перебора (строится по теореме 4.12).
А вот для С=4 я такого решения не знаю. Ни в решении svb, ни в решении, приведённом мной, сильной диагональности нет.

Возникает такая гипотеза: решений с сильной диагональностью для С, являющихся степенью простых, не существует.

-- Чт июн 28, 2012 21:04:39 --

Вот решение для C=3 N=9x9 с сильной диагональностью, построенное по теореме 4.12 (было выложено здесь давно):



Аналогичные решения элементарно строятся для любого простого С.
Выше приведена мозаика - аналогичное решение для C=11, N=121x121.

Кто покажет решение с сильной диагональностью для С=4?
Предполагаю, что такого решения не существует.

Извиняюсь, если неправильно поняла термин "сильная диагональность". Может, под этим совсем другое имеется в виду.

[Zealint]

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

Да? А пример можете привести?
И алгоритм, как в голове строится, если, конечно, не жалко

Не жалко. Первый столбец 100x10 состоит из диагональной раскраски, а второй - из вертикальной. Типа такого (в уменьшенном виде):

6,9,A,B,C,A,B,C,C,A,B,A,B,C,B,C,A,A,B,C,
A,B,C,C,A,B,C,A,B,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,B,C,A,B,C,A,B,C,A

Цитата:

Ну, то, что вам кажется, ещё не факт

Конечно не факт, я ж и не спорю. Там же написано "мне кажется".

Цитата:

Вам как кажется?

Мне кажется нереально : )

Цитата:

Если я правильно понимаю, "сильная диагональность" - это когда все подквадраты СхС в одной диагонали одинаково окрашены. Правильно понимаю?

Правильно. Только у меня две сильных диагональности. Одна - та, что вы описали. А другая - когда 1x1 окаймление из CxC квадратов выполнено в виде Г-крюка. При этом в нашем последнем контексте каждый из CxC подвадратов получается из одной перестановки, тогда как это вовсе необязательно.

Цитата:

А вот для С=4 я такого решения не знаю. Ни в решении svb, ни в решении, приведённом мной, сильной диагональности нет.

Элементарно. Есть же чисто диагональная раскраска для С=3,4,5,6. Она одновременно является и сильно диагональной, но не из перестановок.

Есть и из перестановок:

(16x16, C=4, Сильно диагональное перестановочное решение)

A,D,C,B,D,C,B,A,D,A,B,C,B,A,D,C,
B,A,D,C,A,D,C,B,A,B,C,D,C,B,A,D,
C,B,A,D,B,A,D,C,B,C,D,A,D,C,B,A,
D,C,B,A,C,B,A,D,C,D,A,B,A,D,C,B,
D,C,B,A,D,A,B,C,B,A,D,C,C,B,A,D,
A,D,C,B,A,B,C,D,C,B,A,D,D,C,B,A,
B,A,D,C,B,C,D,A,D,C,B,A,A,D,C,B,
C,B,A,D,C,D,A,B,A,D,C,B,B,A,D,C,
D,A,B,C,B,A,D,C,C,B,A,D,B,A,D,C,
A,B,C,D,C,B,A,D,D,C,B,A,C,B,A,D,
B,C,D,A,D,C,B,A,A,D,C,B,D,C,B,A,
C,D,A,B,A,D,C,B,B,A,D,C,A,D,C,B,
B,A,D,C,C,B,A,D,B,A,D,C,B,C,D,A,
C,B,A,D,D,C,B,A,C,B,A,D,C,D,A,B,
D,C,B,A,A,D,C,B,D,C,B,A,D,A,B,C,
A,D,C,B,B,A,D,C,A,D,C,B,A,B,C,D

-- Чт июн 28, 2012 20:52:58 --

А вот для 36x36 перестановочного сильно диагонального решения нет, зато есть сильно диагональное решение с окаймлением из 6x1 полоски в виде ступенек (Г-образное). Для 49x49 и 64x64 тоже такое есть (недавно нашел). Для 81x81 перебор работает долго...

[Nataly-Mak]

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

Элементарно. Есть же чисто диагональная раскраска для С=3,4,5,6. Она одновременно является и сильно диагональной, но не из перестановок.

Ничего не поняла.
Меня не интересуют чисто диагональные решения. Я спрашиваю о решениях того вида, как показал svb для C=4, N=16x16.

Цитата:

Есть и из перестановок:

(16x16, C=4, Сильно диагональное перестановочное решение)

A,D,C,B,D,C,B,A,D,A,B,C,B,A,D,C,
B,A,D,C,A,D,C,B,A,B,C,D,C,B,A,D,
C,B,A,D,B,A,D,C,B,C,D,A,D,C,B,A,
D,C,B,A,C,B,A,D,C,D,A,B,A,D,C,B,
D,C,B,A,D,A,B,C,B,A,D,C,C,B,A,D,
A,D,C,B,A,B,C,D,C,B,A,D,D,C,B,A,
B,A,D,C,B,C,D,A,D,C,B,A,A,D,C,B,
C,B,A,D,C,D,A,B,A,D,C,B,B,A,D,C,
D,A,B,C,B,A,D,C,C,B,A,D,B,A,D,C,
A,B,C,D,C,B,A,D,D,C,B,A,C,B,A,D,
B,C,D,A,D,C,B,A,A,D,C,B,D,C,B,A,
C,D,A,B,A,D,C,B,B,A,D,C,A,D,C,B,
B,A,D,C,C,B,A,D,B,A,D,C,B,C,D,A,
C,B,A,D,D,C,B,A,C,B,A,D,C,D,A,B,
D,C,B,A,A,D,C,B,D,C,B,A,D,A,B,C,
A,D,C,B,B,A,D,C,A,D,C,B,A,B,C,D

И в этом решении ничего не поняла. Покажите его, пожалуйста, в том виде, как показано у svb (и следом у меня).
В вашем решении не вижу вообще ничего "диагонального".

Значит, у вас ещё какое-то другое понимание "сильной диагональности", не то, о котором писал svb.

[Zealint]

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

Значит, у вас ещё какое-то другое понимание "сильной диагональности", не то, о котором писал svb.

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

когда все маленькие квадраты одинаковы в своей диагонали

В моем решении все побочные диагонали состоят из одинаковых CxC квадратов. То есть именно то, что Вы написали:

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

это когда все подквадраты СхС в одной диагонали одинаково окрашены

[Nataly-Mak]

Кое-что диагональное в вашем решении увидела, когда выделила подквадраты 4х4
Однако сильной диагональности пока не вижу.
Сейчас картинку покажу.

-- Чт июн 28, 2012 22:06:34 --

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

В моем решении все побочные диагонали состоят из одинаковых CxC квадратов. То есть именно то, что Вы написали:

Нет, по-моему не так.
Картинку сейчас покажу. Может, я спрсонья что-то не так вижу

-- Чт июн 28, 2012 22:11:26 --

Вот картинка вашего решения:



Например, разломанная диагональ, содержащая выделенный подквадрат 4х4 (видно выделение? в верхнем ряду второй подквадрат считая слева), содержит не все одинаково окрашенные подквадраты 4х4.

Или вы под побочной диагональю имеете в виду только два подквадрата 4х4?
А я имею в виду полностью разломанную диагональ, состоящую из 4-х подквадратов.
Для С простых имеем именно такую сильную диагональность.