2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение12.07.2012, 18:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #594694 писал(а):
Класс! Строка для решения С9N81. Получилась симметричная матрица.

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

Изображение

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

Код:
1,1,2,
1,3,3,
2,3,1

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

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

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


21/02/10
1594
Екатеринбург
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

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


22/03/08

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

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

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

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

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

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

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


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

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


22/03/08

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

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

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

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #594791 писал(а):
Могу предположить, что данная аналогия пройдёт для C16N256. Завтра попробую.

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

Изображение

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

-- Пт июл 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 такой же крепкий орешек.

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

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

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #594765 писал(а):
Если эта красивая женщина идея вас не обманет, то вы получите-таки решение C10N100.

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


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

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


22/03/08

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

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

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


21/02/10
1594
Екатеринбург
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. Доказательство надо проверять.

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


22/03/08

7154
Саратов
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 лет искать и не найти, ежели оно вообще не существует.

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


21/02/10
1594
Екатеринбург
Tom Sirgedas доказывает, что в квадрате 28х28 нельзя расставить 157 единичек(28x28/5 = 156.8).
Nataly-Mak в сообщении #593675 писал(а):
Pavlovsky
Может, зря вы думаете, что можете расставить первый цвет даже в квадрате 28х28. Попробуйте-ка!

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

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


22/03/08

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

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #594813 писал(а):
Но боюсь, что и аналогия с 6х6 не прокатит


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

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #594828 писал(а):
Скорее всего строку 100 мы не получим. Но получить строку длины 91 реально.

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

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

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


19/12/10
1546
Пост удалён автором.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 130  След.

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



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

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


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

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