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

[Nataly-Mak]

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

Класс! Строка для решения С9N81. Получилась симметричная матрица.

Очень красиво симметричная!



Ещё строка для C3N9:

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

Pavlovsky
для кучи не хватает строк для C7N49 и C8N64

Предполагаю, что для C8N64 будет нечто аналогичное матрице для C9N81 - матрица 8х8, возможно, тоже симметричная. Эта строка вполне может состоять из 64 символов.
А может, это будет матрица 8х8 аналогичная матрице 4х4 для C4N16 (несимметричная).

[Pavlovsky]

C=7
1,1,2,1,3,4,5,
6,2,2,5,2,6,4,
7,1,5,5,7,5,1,
4,3,2,7,7,3,7,
2,4,6,5,3,3,6,
3,5,4,1,7,6,6,
1,6,7,4,2,3,1

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

матрица 8х8 аналогичная матрице 4х4

C=8

1,1,2,1,3,4,5,1,
6,7,7,5,7,2,3,1,
7,6,8,8,1,8,5,2,
7,8,6,4,4,7,4,1,
5,8,4,6,3,3,8,3,
7,1,4,3,6,2,2,4,
2,8,7,3,2,6,5,5,
3,5,4,8,2,5,6,1

[Nataly-Mak]

Pavlovsky
идея действительно безумно красивая

Если эта красивая женщина идея вас не обманет, то вы получите-таки решение C10N100.

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

-- Чт июл 12, 2012 22:01:59 --

Кстати, строка для C10N100 вполне может состоять из 100 символов, так я думаю.
То есть будет матрица 10х10, если будет. Но вот какая она будет? Это пока не могу вообразить

Порядок 10 очень коварен. Недаром до сих пор не нашли даже группу из трёх попарно ортогональных ЛК 10-го порядка.

[svb]

Опробовал один переборный алгоритм, возможно связанный каким-то боком с идеями Павловского (но может и не связанный - пока не анализировал). Начало было шустрым, мгновенно получил для маленьких C некоторые таблички, из которых должны были получаться цветные квадраты. Так как алгоритм получения квадратов пока не продуман до конца, то просто попробовал получать их вручную, вроде получилось, хотя некоторые неясности остались. Не стал на них заострять внимание, а просто запустил программку получения табличек. В силу старческого маразма постоянно спотыкался на самых элементарных вещах, которые раньше никогда не делал. Но, все же, первые опыты были проделаны. Например, для C=9 нужная мне таблица была получена за 73 сек. Удивило, что программа сработала для всех меньших C. Но вот она встретилась с C=10
Работает несколько часов и шансы на получение результата почти растаяли. Имеются смутные подозрения, что виновато особое устройство поля GF(9), но тогда не очень понятно, почему для меньших C все сработало. С другой стороны, рост перебора катастрофический, поэтому без дополнительных идей двигаться дальше нельзя. Сейчас отложил компьютер и тупо размышляю

[Nataly-Mak]

Всё осложняется тем, что все варятся в собственном соку. После окончания конкурса можно будет открыть все алгоритмы (правда, опять же не все могут захотеть это сделать, но, по крайней мере, не будем ограничены рамками конкурса).

Сейчас попробовала вручную составить матрицу 10х10 по аналогии с матрицей 8х8. Нет, не получилось.
Могу предположить, что данная аналогия пройдёт для C16N256. Завтра попробую.

Для С10N100... сильные подозрения, что нужная строка символов может не найтись.

[Nataly-Mak]

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

Могу предположить, что данная аналогия пройдёт для C16N256. Завтра попробую.

Попробовала
Дальше не знаю, как двигаться.



Но вполне возможно, что аналогия пройдёт.
Впрочем, возможно и обратное.

-- Пт июл 13, 2012 05:38:34 --

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

Удивило, что программа сработала для всех меньших C.

А ничего удивительного нет.

Для групп попарно ортогональных ЛК, к примеру, ситуация аналогичная.
Для n=3,4,5,7,8,9 существуют полные комплекты попарно ортогоальных ЛК, состоящие из (n-1) квадратов. Для n=6 не существует даже пары ортогональных ЛК (речь идёт о классических ЛК).
А вот для n=10 математики всего мира уже много лет ищут группу из трёх попарно ортогональных ЛК. Пока есть только пары ортогональных ЛК данного порядка.

Pavlovsky приводил ссылку на проект распределённых вычислений по поиску пар ортогональных ЛК 10-го порядка и самое главное - поиска хотя бы трёх попарно ортогональных ЛК данного порядка.
Заглядывала в этот проект. Там пишут примерно следующее (цитирую по памяти):
"Поиск группы из трёх попарно ортогональных ЛК 10-го порядка есть вызов человеческому интеллекту".

Вполне возможно, что и решение С10N100 такой же крепкий орешек.

Опять же: есть или нет - вот в чём вопрос
Может быть, мы ищем то, чего не существует в природе?

Вот группу из трёх попарно ортогональных ЛК 10-го порядка никак не могут найти. А она существует? Кто-нибудь доказал её существование?
Интересный вопрос!
Вот у Эйлера была гипотеза, что ОЛК не существуют для всех порядков n=4k+2, k=1,2,3,...
Для n=6 гипотеза оказалась верной (кстати, дказывали это перебором; два математика, братья, просто выписали все возможные ЛК 6-го порядка и обнаружили, что ортогональных среди них не имеется; по крайней мере, так пишет М. Гарднер в своей книге "Математические досуги"; за что купила, за то и продаю ).

Для следующих n гипотеза не подтвердилась.
Но ведь это была всего лишь гипотеза, Эйлер её не доказал.

[Pavlovsky]

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

Если эта красивая женщина идея вас не обманет, то вы получите-таки решение C10N100.

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

Алгоритм №2 нашел строку длиной 85! Осталось совсем немного. C10N100 жду со дня на день.

[Nataly-Mak]

Ох, обманет вас эта красивая идея!

А строки длиной 85 мало? Обязательно надо строку длины 90?

[Pavlovsky]

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

А строки длиной 85 мало?

Проверил, мало. Получилось решение всего С10N89.

-- Пт июл 13, 2012 09:10:38 --

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

Сейчас попробовала вручную составить матрицу 10х10 по аналогии с матрицей 8х8.

Наверно, в качестве аналога, надо брать 6х6.

-- Пт июл 13, 2012 09:37:28 --

Для С=10, хочу опробовать такой шаблон. В нем надо заполнить всего 44 ячейки.

(Оффтоп)

-- Пт июл 13, 2012 09:44:57 --

На форуме конкурса Tom Sirgedas создал тему Monochromatic Squares N > C^2
http://infinitesearchspace.dyndns.org/c ... uares-n-c2
В частности привел доказательство невозможности построения C5N28. Доказательство надо проверять.

[Nataly-Mak]

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

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

А строки длиной 85 мало?

Проверил, мало. Получилось решение всего С10N89.

Решения диагональные по этому алгоритму получаются?

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

Сейчас попробовала вручную составить матрицу 10х10 по аналогии с матрицей 8х8.

Цитата:

Наверно, в качестве аналога, надо брать 6х6.

Да, я тоже так подумала после того, как проверила по аналогии с матрицей 8х8.
Но боюсь, что и аналогия с 6х6 не прокатит

-- Пт июл 13, 2012 08:49:46 --

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

В частности привел доказательство невозможности построения C5N28. Доказательство надо проверять.

Вот с этого и надо начинать! Решение можно 10 лет искать и не найти, ежели оно вообще не существует.

[Pavlovsky]

Tom Sirgedas доказывает, что в квадрате 28х28 нельзя расставить 157 единичек(28x28/5 = 156.8).

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

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

Надо попробовать, может и зря думаю...

[Nataly-Mak]

Мы тут уже рассмотрели одно из решений C5N26 с пустой ячейкой. В этом решении все цвета занимают ровно 135 ячеек. И ни шагу вперёд сделать невозможно, по крайней мере, в данном решении.

Однако, как я поняла, тому товарищу удалось расставить один цвет в квадрате 26х26.

[Pavlovsky]

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

Но боюсь, что и аналогия с 6х6 не прокатит

Ранее я показал все строки для С=4-9. Заметьте все строки длиной C^2. Кроме С=6, где длина 31. Это максимум. Ведь алгоритм у меня полного перебора. С=6 отличается от других чисел, оно единственное не p^s. Логично выдвинуть гипотезу, что С=10 ,будет вести себя аналогично С=6. Скорее всего строку 100 мы не получим. Но получить строку длины 91 реально. И этого должно хватить для построения С10N100. Получу строку 90,91 там будет видно. Например напильник у меня примитивный, можно его усовершенствовать.

[Nataly-Mak]

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

Скорее всего строку 100 мы не получим. Но получить строку длины 91 реально.

Опять же это только предположение?

Я вот, к примеру, считаю, что реально получить прямоугольник 100х20, удовлетворяющий нашей с svb лемме. Однако доказать это не могу. Пока только практически получила прямоугольник 81х20 с такими свойствами. Сколько можно добавить строк к этому прямоугольнику, не нарушая его свойств? И можно ли добавить вообще хоть одну строку?

[whitefox]

Пост удалён автором.