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

[svb]

Дополнение.
Похоже, что в первом варианте вместо p[i,(n-j)mod n] можно использовать любой латинский квадрат?

[Pavlovsky]

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

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

Ааа вы все свои идеи изложили ввиде трех строчек кода. Посмотрю внимательно.

А Г-достраивание наверно будет нужно всегда.

Функция присовения цвета такова (i*k+j+l), что если прямоугольник находится в одном квадранте, то формула i*k+j+l = i*c+j+d = a*c+b+d = a*k+b+l
Превращается в j+l = j+d = b+d = b+l
То есть каждый квадрант у нас будет латинским квадратом(в строках и колонках нет одинаковых чисел). А это означает, что Г-крюк всегда можно добавить.
Получается, что все выкладки можно применить к области под Г-крюком. То есть мы строим квадрат со стороной С^2-C, разбитый на квадранты со стороной С (или С-1). Впрочем размер таблицы умножения при этом не уменьшается и задача проще не становится.

[svb]

Nataly-Mak

Цитата:

но как я понимаю, тут мало кто интересуется чужими идеями, все сами с усами

Ну, почему же? Но из того, что

Цитата:

Всё это я уже рассказывала.

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

Я не хочу ничего плохого говорить о ваших идеях, но постоянные реплики "Я это уже рассказывала" могут вызвать недоумение. Ну и что? Когда я использую поля, то мне и в голову не приходит, что это оригинально. Более того, я уверен что их использовали большинство участников. Меня удивило сообщение Павловского, я искренне считал это хорошо известным.

Прошу не воспринимать мои слова отрицательно - к сожалению, я часто этим грешу. Меня иногда так и подмывает кого-нибудь укусить. Относитесь к ним, как к обыкновенному "трепу" человека, который застрял во "втором классе" Я бы мог подыскать себе оправдания, дескать старый и больной на голову, дескать я мало времени занимаюсь задачей, и т.д. Но это не так

-- Сб июл 28, 2012 15:10:27 --

Pavlovsky

Цитата:

А Г-достраивание наверно будет нужно всегда.

В примере для GF(4), который я приводил, этого нет.

[Nataly-Mak]

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

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

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

Я прекрасно знаю ваше отношение к моим идеям (не только по форуму, но и по личной переписке). Это первое.

Второе: я была приведена в неописуемое удивление, когда тут разволновались, как бы вас не отлучили от конкурса за то, что вы выложили решение C6N36
Два часа смеялась и до сих пор смеюсь
Ведь я выложила это решение, наверное, месяц назад!

Вот это и дало мне основания предполагать, что я совершенно напрасно стараюсь выкладывать здесь свои идеи, их всё равно никто не читает. Увы, но это так.

(Оффтоп)

Это заодно и ответ на вопрос, почему я вас "принципиально игнорирую".
И давайте не будем дальше развивать "трёп".
Помните, как вы написали в теме "Магические квадраты": "Я на вас обиделся". Я на вас тоже обиделась, потому и игнорирую.

[Pavlovsky]

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

В примере для GF(4), который я приводил, этого нет.

Смогли построить квадрат целиком из ЛК. Для p^s это возможно. А для С=6 уже требуется каемка на коврике. Или можно построить решение C6N36 целиком состоящее из ЛК 6х6??

-- Сб июл 28, 2012 17:31:45 --

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

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

Интересно откуда я мог это узнать? Можно ссылку где это обсуждалось. Стараюсь тщательно мониторить информацию по теме. Конечно, всякое бывает, может где то бегло пробежалася по сообщениям, ничего не понял и пошел дальше.

[Nataly-Mak]

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

Интересно откуда я мог это узнать? Можно ссылку где это обсуждалось.

Не удивляйтесь!
svb считает, что все просто обязаны знать то, что знает он.
Вот я поля обязана была узнать в университете, а почему-то не узнала

[Pavlovsky]

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

svb считает, что все просто обязаны знать то, что знает он.

Да ладно многие так считают. Всем кажется, что тема которую они обдумывают, простая и естественная. Помню как Алексей Чернов искренне удивлялся, что есть люди которые не читали книжек по компьютерной графике.

[svb]

Pavlovsky
Про поля было в "основной" статье.

Nataly-Mak

Цитата:

svb считает, что все просто обязаны знать то, что знает он.

Это невозможно - я слишком много знаю .

(Оффтоп)

Цитата:

Помните, как вы написали в теме "Магические квадраты": "Я на вас обиделся".

Честно скажу, абсолютно не помню. Может и писал, но уж, конечно, не помню за что обиделся. Я постоянно на кого-нибудь обижаюсь. На днях вот на дочь за что-то обиделся, а сейчас мы с ней прекрасно ладим. Я совершенно не отношусь к злопамятным людям, как некоторые (не буду тыкать пальцем ).

[Pavlovsky]

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

Про поля было в "основной" статье.

Про поля я читал. И даже нашел ссылки как с помощью полей строить ортогональные ЛК. А вот что можно просто цвет квадрата задавать функцией вида i*k+j+l там не было. Я все делал как написано в той статье, пункт за пунктом. В обсуждениях проскакивали намеки, что решения C^2 можно строить очень просто. Но конкретики не было. Ну а если пытаться читать между строк, так это никакого времени не хватит.

[svb]

Pavlovsky

Цитата:

Я все делал как написано в той статье, пункт за пунктом.

Должен сознаться, что я остановился на слове "поле", а далее не читал по понятной мне и Наталии причине. До функции вида i*k+j+l я не сразу додумался и не вижу ничего странного в том, что ее можно пропустить. Но это вопрос времени, одни чуть раньше, другие чуть позже. Идеи они вообще в массе своей очень просты. Мой, достаточно богатый, опыт общения с различными людьми заставляет меня не завышать свои "способности", не занижать "способности" других людей. Редко я находил что-то, что ускользнуло от других. А идею функции i*k+j+l я никак не могу отнести к сложным, поэтому и был удивлен.

[dimkadimon]

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

dimkadimon

Цитата:

Хорошо можно сказать что p[a,b] = (a+b) mod n, a sq[a,b] = (ab) mod n?

для простых n это проходит, но уже для n=4 необходимо брать:

0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

Спасибо. У меня теперь еще больше вопросов. Почему для простых проходит, а для остальных нет? То есть что ломается? Как называются эти группы которые вы показали для с=4? Если не ошибаюсь то вторая группа это Z_2 х Z_2? Как эти группы находить?

Меня очень интересуют группы порядка 10. Их две: D_5 и Z_5 x Z_2. Можно ли эти группы также использовать?

[svb]

dimkadimon

Цитата:

Почему для простых проходит, а для остальных нет?

Если не ошибаюсь, имеется теорема о том, что конечные поля из $C$ элементов существуют только для степеней простых чисел $C=p^s$. При $s=1$ это обычные конструкции по модулю $p$, а для больших степеней они устроены несколько сложнее. Нам оказались полезными поля GF(8), GF(9), GF(16), таблицы умножения и сложения для этих полей можно найти в интернете:

(Оффтоп)

GF(8)
0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
0 2 4 6 3 1 7 5
0 3 6 5 7 4 1 2
0 4 3 7 6 2 5 1
0 5 1 4 2 7 3 6
0 6 7 1 5 3 2 4
0 7 5 2 1 6 4 3

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

GF(9)
 0 0 0 0 0 0 0 0 0
 0 1 2 3 4 5 6 7 8
 0 2 1 6 8 7 3 5 4
 0 3 6 2 5 8 1 4 7
 0 4 8 5 6 1 7 2 3
 0 5 7 8 1 3 4 6 2
 0 6 3 1 7 4 2 8 5
 0 7 5 4 2 6 8 3 1
 0 8 4 7 3 2 5 1 6

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

GF(16)
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  0  2  4  6  8 10 12 14  3  1  7  5 11  9 15 13
  0  3  6  5 12 15 10  9 11  8 13 14  7  4  1  2
  0  4  8 12  3  7 11 15  6  2 14 10  5  1 13  9
  0  5 10 15  7  2 13  8 14 11  4  1  9 12  3  6
  0  6 12 10 11 13  7  1  5  3  9 15 14  8  2  4
  0  7 14  9 15  8  1  6 13 10  3  4  2  5 12 11
  0  8  3 11  6 14  5 13 12  4 15  7 10  2  9  1
  0  9  1  8  2 11  3 10  4 13  5 12  6 15  7 14
  0 10  7 13 14  4  9  3 15  5  8  2  1 11  6 12
  0 11  5 14 10  1 15  4  7 12  2  9 13  6  8  3
  0 12 11  7  5  9 14  2 10  6  1 13 15  3  4  8
  0 13  9  4  1 12  8  5  2 15 11  6  3 14 10  7
  0 14 15  1 13  3  2 12  9  7  6  8  4 10 11  5
  0 15 13  2  9  6  4 11  1 14 12  3  8  7  5 10

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14
  2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13
  3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12
  4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11
  5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10
  6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9
  7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8
  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7
  9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6
 10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5
 11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4
 12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3
 13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2
 14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

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

Вот ссылка на вики. Вам, может, интереснее Finite field.

[Nataly-Mak]

Я же говорила, что Алексей ещё пару строк припрятал

Цитата:

21 396 156816 Alex Chernov @ 13:53:04 on 07-29-2012 1

[Nataly-Mak]

Просто раскраски...

Получены на основе группы из 10 попарно ортогональных ЛК 10-го порядка с дырками.
[см. статью "Нетрадиционные латинские квадраты"; статья экспериментальная, ничего научного! ]

Хотя дырок в раскраске 100х100 10-color больше, чем в показанной выше раскраске (там было 790), но зато данная раскраска является регулярным решением. Каждый из 10 цветов в раскраске занимает 909 ячеек, символ NULL занимает 910 ячеек, это и есть дырки.



И получена ещё раскраска 110х100 10-color, в которой тоже 910 дырок. Просто к раскраске 100х100 приписаны ещё 10 строк.

[Nataly-Mak]

Удалось немного улучшить раскраску 100х100 10-color, количество дырок стало 820.
Каждый из 10 цветов занимает 918 ячеек. Опять очень равномерно распределены цвета.