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

[Nataly-Mak]

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

Вот получу C10N100 или, хотя бы, C21N400 - обязательно введу данные

Вы уверены, что успеете это сделать до 31 августа?
А после 31 августа вы не сможете уже ввести данные в БД, не будучи участником конкурса.

Я понимаю ваше нежелание быть где-то там в первой десятке сильнейших
Вам надо непременно быть первым!

Но тут есть такая фишка: все не могут быть на первом месте Первое место одно, а участников около 90.

Понимаю: вы - не все

Вспомнилось из фильма "Граница: таёжный роман". Там героиня говорит своему мужу: "Миллионы людей женятся, разводятся", на что он отвечает: "Но я - не миллионы!"

[Pavlovsky]

Следующий текст является смутным потоком сознания.

Все алгебраические регулярные подходы основаны на следующем. Пользуясь свойствами полей строим С пучков паралельных прямых по С точек в каждом. Так как у нас конечные поля, то надо говорить не о прямых а о циклах. С пучков паралельных циклов по С точек возможно только для C=p^s. Для C<>p^s это сделать невозможно. В этом случае приходится говорить о разорваных циклах (цепочках) длины меньше С. для C=p^s, за счет манипуляций с обрамлениями, можно построить даже квадрат (C^2+C)x(C^2+C) с вырезанным квадратом CxC. Для С=6 было найдено решение 36х36, но это тоже уже не циклы, а цепочки. 36х36 получается за счет обрамлений. Построить квадрат 42х42 с вырезанным углом 6х6 для С=6 невозможно. Для С=10,12,14,15 и далее ситуация ухудшается. Полагаю, что построить для этих С, квадрат C^2xC^2 крайне маловероятно.

Получается, искать регулярные алгебраические структуры безперспективно. Максимум чего можно выжать из этого подхода это процедуры сокращения перебора.

-- Чт авг 09, 2012 11:54:13 --

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

А после 31 августа вы не сможете уже ввести данные в БД, не будучи участником конкурса.

Это не так. После окончания конкурса, любой зарегестрированный участник, может заносить рекордные результаты. Пример из предыдущего конкурса, Tristrom Cooke в конкурсе не участвовал. Но таблицу рекордов обновил кардинально.
http://infinitesearchspace.dyndns.org/samegame/tops

[svb]

Nataly-Mak

Цитата:

Эта матрица является обобщённым латинским квадратом.
Да и первая матрица у вас не является классическим ЛК, т.к. содержит строку и столбец из одинаковых символов. Это тоже обобщённый ЛК. Классическим ЛК является подквадрат 7х7, содержащийся в этой матрице.

Спасибо, про обобщенный ЛК не знал.
Сейчас решил проверить $C=9$ с аналогичной таблицей умножения:

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

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

Цитата:

Вы уверены, что успеете это сделать до 31 августа?

Подозреваю, что не успею

Цитата:

Вам надо непременно быть первым!

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

Цитата:

Понимаю: вы - не все

Как и вы, как и остальные - это же тривиальная мысль. Всю жизнь старался быть "как все", но сейчас понимаю, что нет более глупого занятия, чем пытаться менять себя. Конечно, не очень приятно, когда тебя не понимают. "И зачем вам нужны магические квадраты?" - вам это знакомо?

[Nataly-Mak]

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

.
Это не так. После окончания конкурса, любой зарегестрированный участник, может заносить рекордные результаты. Пример из предыдущего конкурса, Tristrom Cooke в конкурсе не участвовал. Но таблицу рекордов обновил кардинально.
http://infinitesearchspace.dyndns.org/samegame/tops

Да, совершенно верно, я вспомнила
Сейчас уже шла, чтобы сообщить об этом, а вы меня опередили.

Но! Всё равно плохо, ибо в рейтинг после окончания конкурса новые участники уже не вносятся. Кажется, так?
И svb тогда не сможет стать первым

[dimkadimon]

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

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

Вот получу C10N100 или, хотя бы, C21N400 - обязательно введу данные

Хммм... А по мойму участвовать по любому интересно, даже когда не на первом месте. Когда участвуешь то больше интереса и стремления к получению хороших результатов, а когда не участвуешь то всё по барабану и нет никакого стимула. Вот до сих пор пытаюсь убедить Tristrom Cooke поучаствовать в этом соревновании. Он гениальный мужик и вполне может ввести новые рекорды, но ему некогда или неохото :(

Кстати в этом соревновании есть очень силные участники, которые не раз в подобных соревнованиях выигрывали. Я говорю про людей как Tom Sirgedas, Wes Sampson, Jaroslaw Wroblewski (самый гениальный), Roland Postle, Il Brigante Pennasorta etc. Поэтому на мой взгляд даже войти в 10-ку лучших вполне хорошее достижение.

[svb]

Pavlovsky

Цитата:

Для C<>p^s это сделать невозможно.

Да я согласен, хоты бы, на такую регулярность

dimkadimon

Цитата:

Хммм... А по мойму участвовать по любому интересно, даже когда не на первом месте.

Конечно. А я и участвую

[Pavlovsky]

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

Да я согласен, хоты бы, на такую регулярность

Кто бы еще эту регулярность дал. Скажем для С=12, максимум чего построил матрицу 8х8 из унитарных ЛК:

1   1   1   1   1   1   1   1
1   2   3   4   5   6   9   12
1   3   2   6   10   4   12   9
1   4   6   2   9   11   3   7
1   5   10   9   3   2   11   6
1   6   4   11   2   5   7   3
1   9   12   3   11   7   2   4
1   12   9   7   6   3   4   2

Надеялся построить матрицу для С=15 размером 12х12. Тогда бы получил результат C15N195. Но похоже не судьба.

[Nataly-Mak]

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

"И зачем вам нужны магические квадраты?" - вам это знакомо?

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

-- Чт авг 09, 2012 12:01:26 --

dimkadimon в сообщении #604359 писал(а):

Вот до сих пор пытаюсь убедить Tristrom Cooke поучаствовать в этом соревновании. Он гениальный мужик и вполне может ввести новые рекорды, но ему некогда или неохото :(

Он придёт после окончания конкурса и обязательно внесёт свои рекорды

[svb]

(Оффтоп)

Nataly-Mak

Цитата:

То есть мне они и могут быть зачем-то нужны (ну, нечего бабке делать, она квадратами мается), а вот уж всем остальным они точно не нужны

Вот и вы пытаетесь найти объяснение Я очень люблю погружаться в прошлые века. Как они жили? Что их волновало? Почему, например, Баше совершил гигантский труд по нахождению всех магических квадратов 4-го порядка? Делать было нечего? Отчасти, может быть и так - крестьянам было не до квадратов. Но вот, что бросается в глаза - любая "рационализация" поступков всегда вела к деградации. Мы с ужасом наблюдаем то, что делают с нашей страной специалисты по "эффективности". Увы, только слепой может не видеть прямой связи между интересом к "магическим квадратам" и процветанием государства. Это почти теорема.

С точки зрения "полезности" задача конкурса превышает любые проекты типа "Сколково". Рекомендую, особенно молодым, задуматься об этом. Но можно просто решать задачу - так обычно и делают

[Nemiroff]

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

Увы, только слепой может не видеть прямой связи между интересом к "магическим квадратам" и процветанием государства. Это почти теорема.

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

С точки зрения "полезности" задача конкурса превышает любые проекты типа "Сколково". Рекомендую, особенно молодым, задуматься об этом.

А можно вот эти два утверждения поподробнее раскрыть? Если конкретно, я слепой в первом случае и не понял, о чем мне нужно задуматься, во втором.

[Nataly-Mak]

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

Скажем для С=12, максимум чего построил матрицу 8х8 из унитарных ЛК:

Красивая идея! Вот изобразила, даже попыталась улучшить Увы, не получилось.



Pavlovsky
вы рано сдаётесь. Впереди ещё уйма времени. Эх, где ваш капитан?
Он бы не дал вам впадать в такой пессимизм.

-- Чт авг 09, 2012 16:13:32 --

Да, мне этот метод напомнил построение сотовых магических квадратов. Очень похожий принцип!
Особенно мне понравился метод LUX, описан здесь

[svb]

(Оффтоп)

Nemiroff

Цитата:

А можно вот эти два утверждения поподробнее раскрыть? Если конкретно, я слепой в первом случае и не понял, о чем мне нужно задуматься, во втором.

Пояснить могу, а вот "раскрыть" вряд ли. Под "магическими квадратами" я, конечно, имел в виду не одну частную проблему, а множество "бессмысленных" задач, которые на протяжении веков решали люди. Тут вам и трисекция угла с квадратурой круга, тут вам и задачки Ферма, который читал Диофанта в переводе упоминаемого Баше, тут и странные занятия Ливенгука, тут и ... считай вся история науки. Часто приходилось и приходится искать "оправдания" своим занятиям. В СССР даже был период, когда математики гордились "ненужностью" проблем, которыми они занимались. В Англии Харди придерживался того же мнения. И все было бы хорошо, но в XX веке эти скромные незаметные люди были "пропиарены". Трудно было не заметить "достижений", даже заведомо бессмысленная забава в 0 и 1 родила компьютеры. Ну и началось! Давай еще, давай еще ... И вот "ученые" занялись "нанотехнологиями", "квантовыми компьютерами" и т.п. Но трудно, а точнее невозможно "лохам" соревноваться с профессиональным жульем. Появились "индексы цитирования" и прочая глупость - все это имеет "рациональные" объяснения. И т.д. - дальше вы сами можете продолжить.

[Nataly-Mak]

Какая красота!

http://radikal.ru/F/s017.radikal.ru/i40 ... 6.jpg.html

Pavlovsky
а матрица 8х8 - это максимум для С=12?
У вас в матрице отсутствует унитарный квадрат №8. Почему?
А для С=15 что даёт этот метод?

[Nataly-Mak]

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

Скажем для С=12, максимум чего построил матрицу 8х8 из унитарных ЛК:

1   1   1   1   1   1   1   1
1   2   3   4   5   6   9   12
1   3   2   6   10   4   12   9
1   4   6   2   9   11   3   7
1   5   10   9   3   2   11   6
1   6   4   11   2   5   7   3
1   9   12   3   11   7   2   4
1   12   9   7   6   3   4   2

Хм... а вот в этой матрице подквадрат 7х7 является нетрадиционным латинским квадратом.
А почему именно такой подквадрат получился? А другой нельзя сюда вставить?
А ещё лучше подквадрат 10х10 пытаться вставить.

Алгоритм простой: перебираем всевозможные нетрадиционные ЛК 10-го порядка (эти ЛК заполняются числами от 2 до 12; их очень много!), для каждого такого ЛК заполняем полную матрицу унитарными ЛК и проверяем, является ли она правильной раскраской.

Автор исчез куда-то Возможно, он именно так и делал...

Если такой подквадрат 10х10 найти удастся, это же даст решение C12N144.

[Pavlovsky]

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

а матрица 8х8 - это максимум для С=12?
У вас в матрице отсутствует унитарный квадрат №8. Почему?
А для С=15 что даёт этот метод?

Для С=10 нашел матрицу 7х7
Для С=12 нашел матрицу 8х8
Для С=15 нашел матрицу 9х9

Все это очень мало. Для получения решения C^2 необходимо найти матрицу (С-1)х(С-1). Еще С добавляется с помощью обрамления. На крайний случай, скажем для С=10, можно попытаться построить матрицу 8х8. Тем самым получить решение C10N190. А затем тряской чего то добавить. Ну и для С=15, матрица 12х12 дает решение C15N195.

Мой опыт исследований, показывает, что очень опасна погоня за миражами. Это когда поменял исходные данные и кажется что разрабатываешь что то новое. Но на самом деле, поменялся только язык задачи, и в результате приходишь к решениям давно известным.

Похоже здесь тот самый случай. Я уже писал, что подход с заполнением матрицы унитарными ЛК, дает квадраты, которые после небольших преобразований можно представить ввиде сильноокрашенного прямоугольника с последующей репликацией. То есть алгоритм принципиально ничем не отличается от алгоритма изложеннего в энциклопедии для ежиков.

С другой строны, вот исходный ЛК для С=10

1   2   3   4   5   6   7   8   9   10
10   1   2   3   4   5   6   7   8   9
9   10   1   2   3   4   5   6   7   8
8   9   10   1   2   3   4   5   6   7
7   8   9   10   1   2   3   4   5   6
6   7   8   9   10   1   2   3   4   5
5   6   7   8   9   10   1   2   3   4
4   5   6   7   8   9   10   1   2   3
3   4   5   6   7   8   9   10   1   2
2   3   4   5   6   7   8   9   10   1

А это матрица заполнения унитарными ЛК квадрата

1   1   1   1   1   1   1
1   2   3   4   5   6   10
1   3   2   6   8   4   7
1   4   6   5   3   10   9
1   5   8   10   9   7   2
1   9   7   3   10   2   8
1   10   4   9   2   5   6

Дык это таблицы сложения и умножения конечных полей! То есть это вариант алгоритма Сергея! То есть мы гуляем среди миражей!