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

[Zealint]

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

Ну, вот что нет времени послать решения, в это совсем не верю. Для этого надо максимум 10 минут времени (для 10-15 решений). К тому же, как вы утверждаете, он активно работает над дезарговыми плоскостями. Значит, время у него всё-таки есть.

Ошибка в логике. Из того, что он чем-то активно занимается не следует, что у него есть время : ) 10 минут у него нет, так как это сопряжено с уходом от темы, что влечёт за собой потерю концентрации.

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

Так значит, Антон построил некую проективную плоскость для n=6.
Так и запишем

Да, запишите, только укажите, что это с моих слов, так как я мог неправильно его понять или не расслышать (по телефону).

Цитата:

Вообще я не удовлетворена вашими рассказами.

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

[Nataly-Mak]

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

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

Ну, вот что нет времени послать решения, в это совсем не верю. Для этого надо максимум 10 минут времени (для 10-15 решений). К тому же, как вы утверждаете, он активно работает над дезарговыми плоскостями. Значит, время у него всё-таки есть.

Ошибка в логике. Из того, что он чем-то активно занимается не следует, что у него есть время : ) 10 минут у него нет, так как это сопряжено с уходом от темы, что влечёт за собой потерю концентрации.

Не вижу никакой ошибки! Он занимается темой, связанной с конкурсной задачей (дезарговы плоскости), значит, у него есть время на эту задачу. Только это я и сказала.

Ну, мне такое неизвестно, чтобы уход от темы на 10 минут мог выбить меня из темы
Я могу и на год уходить из темы, и меня это не выбивает из неё, через год могу вернуться и продолжить. Так что сие мне тоже непонятно.

Какой-то загадочный Антон

А вас, собственно, никто и не просил за него рассказывать, сами вызвались
Так ещё может получиться что-то вроде испорченного телефона.

[Zealint]

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

А вас, собственно, никто и не просил за него рассказывать, сами вызвались

Я просто сказал, что могу, а Вы уже попросили:

Nataly-Mak писал(а):

Так расскажите, если можете

Цитата:

Не вижу никакой ошибки!

Бывает.

Цитата:

Ну, мне такое неизвестно, чтобы уход от темы на 10 минут мог выбить меня из темы

А мы и не Вас обсуждаем.

Ладно, отстаньте от Антона, ему не до квадратиков сейчас. Его полное решение я напишу после завершения конкурса.

[Nataly-Mak]

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

Ладно, отстаньте от Антона, ему не до квадратиков сейчас. Его полное решение я напишу после завершения конкурса.

А я разве к нему приставала?

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

Сейчас начала просматривать, такие интересные экземплярчики обнаружила. Например, решение C8N64 очень оригинальное (один из вариантов). Очень похоже на алгоритм, который недавно показал Pavlovsky, но только заполнение матрицы выполняется не унитарными ЛК!
А матрица вот такая:

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

Решение построила давно, но тогда не взглянула на него с позиции этого алгоритма, т.к. ещё и не знала о нём. А строила его совсем по другому алгоритму.

В общем, материалов у меня столько, что вполне на книгу хватит. Только не знаю, найду ли силы её написать. Очень устала

-- Вт авг 21, 2012 12:01:03 --

Заворожил меня этот алгоритм - заполнение матрицы унитарными ЛК (а может, и не только унитарными?).
Начала делать по порядку.
Для С=4 матрица такая получилась:

1 1 1
1 2 3
1 4 2

Для С=5 совсем просто, это же простое число:

1 1 1 1
1 2 3 4
1 3 5 2
1 4 2 5

Для С=6 с наскоку не получилось у меня. Тогда взяла решение, которое тут выложил svb.
Такая матрица по его решению:

1 1 1 1 1
1 6 5 3 2
1 5 3 6 4
1 4 6 2 5
1 3 4 5 6

Для С=7 не делала ещё, но это тоже просто должно быть.

А вот для С=8 интересно. Надо своё решение посмотреть, в котором не унитарные ЛК заполняют матрицу. Да и с унитарными ЛК тоже интересно.

[Nataly-Mak]

Вот моё оригинальное решение C8N64, о котором говорила выше:



Есть в теме решение C8N64, выложенное svb.
По-моему, совсем разные у нас решения.
У меня есть ещё варианты этого решения.

[Pavlovsky]

До конца конкурса осталось чуть больше недели. Вряд ли смогу улучшить результаты. Поэтому сбрасываю последние остатки идей.

Строим сильно окрашенный прямоугольник размером N^2xN. Будем заполнять его набором из С унитарных перестановок ввиде колонок Nx1. Набор перестановок будем представлять ввиде ЛК. Каждая колонка ЛК - перестановка. То есть надо заполнить матрицу NxN перестановками из набора.
Примеры для С=6

0 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4
ЛК 6х6, полученный циклическими перестановками. По ЛК полученным циклическим сдвигом легко строятся решения C^2xC^2 для простых C .

2 3 4 5
3 5 2 4
5 2 6 3
6 4 3 2
Матрица перестановок. Число означает номер перестановки, то есть колонка в исходном ЛК. В матрице перестановок не показаны строка и колонка №1, которые заполняются перестановкой №1
По этой матрице строится решение C6N36.

0 1 2 3 4 5
1 2 0 4 5 3
2 0 1 5 3 4
3 4 5 0 1 2
4 5 3 1 2 0
5 3 4 2 0 1
ЛК 6х6. Таблица сложения, полученная декртовым произведением G(2)xG(3). Где G(p) таблица сложения по модулю p. p - простое. По ЛК полученным выше описанным способом строятся решения C^2xC^2 для C=p^s .

2 3 4 5
3 5 2 4
4 6 5 3
5 2 3 6
Матрица перестановок. По этой матрице строится решение C6N36.

0 1 2 3 4 5
1 0 5 4 3 2
2 3 4 5 0 1
3 2 1 0 5 4
4 5 0 1 2 3
5 4 3 2 1 0
ЛК Агриппы (любезно предоставлен Наталией)

2 3 4
3 4 2
4 2 3
Матрица перестановок. По этой матрице строится решение всего C6N30. Отрицательный результат тоже результат. Исходный ЛК имеет большое значение.

0 1 2 3 4 5
1 3 0 2 5 4
2 5 4 0 3 1
3 4 5 1 0 2
4 0 1 5 2 3
5 2 3 4 1 0
ЛК 6х6 Наталии

2 4 6
3 2 4
5 3 2
Матрица перестановок. Строится решение тоже всего лишь C6N30.

-- Вт авг 21, 2012 13:49:21 --

С=10
Циклический ЛК 10х10.
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 3 4 5 6 7 8 9 0 1
3 4 5 6 7 8 9 0 1 2
4 5 6 7 8 9 0 1 2 3
5 6 7 8 9 0 1 2 3 4
6 7 8 9 0 1 2 3 4 5
7 8 9 0 1 2 3 4 5 6
8 9 0 1 2 3 4 5 6 7
9 0 1 2 3 4 5 6 7 8

Матрица перестановок
2 3 4 5 6 7 8
3 5 9 8 2 4 6
4 9 8 6 5 10 3
5 8 6 2 10 3 7
6 2 5 10 3 9 4
7 4 10 3 9 6 2
8 6 3 7 4 2 9


ЛК 10х10. Таблица сложения.
0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 6 7 8 9 5
2 3 4 0 1 7 8 9 5 6
3 4 0 1 2 8 9 5 6 7
4 0 1 2 3 9 5 6 7 8
5 6 7 8 9 0 1 2 3 4
6 7 8 9 5 1 2 3 4 0
7 8 9 5 6 2 3 4 0 1
8 9 5 6 7 3 4 0 1 2
9 5 6 7 8 4 0 1 2 3

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


По этим матрицам можно получить решение C10N90. Интересно можно ли его нарастить до приличных значений?! Например до C10N94??

[Nataly-Mak]

Сейчас попробовала в программе Эда методом тыка заполнить матрицу унитарными ЛК 8-го порядка. Вот что удалось:



Pavlovsky
если не жалко, скажите, какая будет матрица для С=8.

Надо вникнуть в то, что вы написали в последнем сообщении. Может быть, и сама построю эту матрицу.

[Pavlovsky]

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

если не жалко, скажите, какая будет матрица для С=8.

Свои результаты по заполнению Матрицы наборами ЛК я писал где то раньше. Найти этот пост среди 93 страниц очень трудная задача. Очевидно используя конечное поле GF(8), с помощью таблицы сложения строим набор из унитарных ЛК. Таблица умножения будет матрицой, по которой заполняем квадрат решения.

А если заполнять матрицу перестановками, то таже картниа. Если взять таблицу сложения G(2)xG(2)xG(2) Это будет исходный ЛК, где каждая колонка это перестановка из набора. По исходному ЛК, легко заполняется матрица и строится решение C8N64.

[Nataly-Mak]

У вас там не было матрицы для С=8. Я знаю, где это. Сейчас дам ссылку.
Совсем это не трудная задача. Есть Поиск, между прочим
Не пользуетесь? Очень быстро всё находит!

-- Вт авг 21, 2012 13:46:35 --

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

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.

Стр. 87.

[Pavlovsky]

Для С=p^s. Строим таблицу сложения и умножения для конечного поля GF(C).

Таблица сложения будет исходным ЛК для набора. Остальные ЛК получаем циклической перестановокой колонок таблицы сложения. Таблица умножения будет матрицей, где число означает номер ЛК из набора. Строим квадрат.

[Nataly-Mak]

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

Очевидно используя конечное поле GF(8), с помощью таблицы сложения строим набор из унитарных ЛК. Таблица умножения будет матрицой, по которой заполняем квадрат решения.

Получается, что для С=8 надо строить унитарные ЛК не циклическим сдвигом?
Ничего пока не поняла.
Я думала, что для всех С набор ЛК строится одинаково - циклическим сдвигом.
Так построила сейчас решение для С=4. Получилось.

-- Вт авг 21, 2012 14:02:59 --

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

Для С=p^s. Строим таблицу сложения и умножения для конечного поля GF(C).

Таблица сложения будет исходным ЛК для набора. Остальные ЛК получаем циклической перестановокой колонок таблицы сложения. Таблица умножения будет матрицей, где число означает номер ЛК из набора. Строим квадрат.

А, ну их к дьяволу эти конечные поля. Я в них не желаю разбираться.

-- Вт авг 21, 2012 14:10:34 --

Вот решение C4N16, полученное по вашему методу из унитарных ЛК 4-го порядка, построенных циклическим сдвигом:



Нету тут никаких таблиц сложения и умножения.
Повторю матрицу заполнения унитарными ЛК:

1 1 1
1 2 3
1 4 2

Для С=8 нет аналога?

[Pavlovsky]

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

Я в них не желаю разбираться.

А чего там разбираться. Есть две таблички NxN. Одна называется таблицей сложения, другая таблицей умноежния. Для всех нужных С, Сергей давал эти таблички. Больше ничего знать не нужно.

-- Вт авг 21, 2012 15:20:57 --

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

Для С=8 нет аналога?

Если строить набор ЛК, циклическим сдвигом цветов, то можно получить максимум матрицу 6х6.

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

Как получить C8N64 я описал чуть выше.

[Nataly-Mak]

Ага, вот теперь, когда вы разобрались, говорите "А чего там разбираться?"
Что-то забыли, как сами по этим самым полям вопросы задавали

Не желаю разбираться - и точка!

-- Вт авг 21, 2012 14:25:02 --

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

Как получить C8N64 я описал чуть выше.

Спасибо, но мне это описание непонятно.
Буду со своим решением разбираться.
Оно у меня тоже весьма красивое (выше показано).
В нём ЛК есть разные, и с циклическим сдвигом и без него.

[svb]

Как много страниц! Неужели во всем этом потом придется разбираться? А хотелось бы...

С трудом нашел свои прошлые полезные сообщения:

Постоянно используемая теорема
Пример "нетрадиционных таблиц к теореме
Традиционные таблицы для всех используемых нами полей

Так как латинский квадрат $L$ можно выбрать произвольно, то обычно используется вариант $L(x,y)=x+y (\mod c)$.

[Nataly-Mak]

Не понимаю этих треволнений.
Уже написала чуть выше: есть Поиск. Пользуйтесь! Всё находится мгновенно.
Я не испытываю никаких сложностей в этом плане.

Например, ищу слова "такую регулярность" (искать желательно только в "Свободном полёте", то есть там, где эта тема находится). Мгновенно выхожу на нужное мне сообщение.