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

[Pavlovsky]

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

Jim Gillogly (США) - Scryer

Исправил.

[Nataly-Mak]

И ещё есть один форумчанин - участник конкурса:

Jarek - Jarek Wroblewski (Польша)

Я писала ему недавно, приглашала принять участие в настоящей дискуссии.
Он ответил, что пока очень занят и не имеет времени решать задачу, хотя задача ему очень интересна.
Принимал участие в теме о конкурсе с перекладыванием карт (на этом форуме).

Кстати, вроде Jarek первым применил алгоритм для простых чисел.

[Pavlovsky]

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

И ещё есть один форумчанин - участник конкурса:Jarek - Jarek Wroblewski (Польша)

Все уже запрещено редактировать.

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

Кстати, вроде Jarek первым применил алгоритм для простых чисел.

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

Цитата:

19 361 130321 Jarek Wroblewski @ 11:19:13 on 05-30-2012

[Nataly-Mak]

Да, точно! Я ещё тогда удивилась, как быстро он нашёл этот алгоритм.

Цитата:

5 25 625 Jarek Wroblewski @ 09:04:36 on 05-30-2012 37
7 49 2401 Jarek Wroblewski @ 09:05:38 on 05-30-2012 34
11 121 14641 Jarek Wroblewski @ 09:06:25 on 05-30-2012 33
13 169 28561 Jarek Wroblewski @ 09:07:27 on 05-30-2012 33
17 289 83521 Jarek Wroblewski @ 09:13:49 on 05-30-2012 33
19 361 130321 Jarek Wroblewski @ 09:19:13 on 05-30-2012 33

По-английски он, конечно же, читает (и пишет!) очень хорошо. При этом знает ещё довольно хорошо русский (пишет мне письма по-русски), ну, и, разумеется, польский.
Завидую белой завистью

-- Ср июл 04, 2012 13:39:06 --

Ввёл новые результаты россиянин Vladimir Chirkov.
Кстати, тоже какой-то полуджентльменский набор решений одинаковый у трёх участников:

Цитата:

22 Markus Egli 18.386300 06-11-2012 @ 15:51:59
23 Jesse Kolman 18.386300 06-26-2012 @ 22:31:39
24 Vladimir Chirkov 18.386300 07-04-2012 @ 13:19:49

Да, а ведь на конкурсе, кажется, есть возможность отправлять письма участникам.
По крайней мере, мне так писал dimkadimon (письма приходят в домашний ящик, то есть по e-mail, указанному при регистрации).
А я не умею пользоваться этой почтой.
Кто-нибудь подскажет?

-- Ср июл 04, 2012 14:03:08 --

Испекла очередной пирожок квадрат:



Замечательный квадратик 100х100 в 10 цветов раскрашен.
Одно плохо - ошибок многовато, 15825
Но уже лучше, в первом у меня было 19500 ошибок, во втором 18785, а вот в третьем всего 15825. Прогресс налицо

Да, процесс выпечки - применение леммы 4.3 к показанному выше "неправильному" прямоугольнику 100х20 10-coloring.

[Nataly-Mak]

Теорема 4.5 в любимой нами статье гарантирует существование прямоугольника 12x66 strong (10,2)-coloring.

Кто-нибудь знает, как такой прямоугольник построить?

Весьма хиленький прямоугольничек
Нам нужен прямоугольник 100х20, но! не strong (10,2)-coloring!! У нас требования значительно слабее.
Но вот существует ли такой прямоугольник

Для начала нас бы устроил и прямоугольник 95х19 с нужными свойствами (по усиленной лемме 4.3). Такой прямоугольник мог бы дать решение С=10, N=95x95, которое тоже пока не получено.

[Nataly-Mak]

Анализирую... прямоугольник 100х20 10-coloring.
Насколько он "плохой" и можно ли его сделать "хорошим".
Просто вручную выписала первые 9 строк из этого прямоугольника, эти 9 строк вполне удовлетворяют условиям усиленной леммы 4.3:

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

Обратите внимание: здесь есть, например, такой прямоугольничек:

5 6
5 6

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

И вот прямоугольник 9х100 10-coloring, полученный из найденного мной прямоугольника 9х20 применением леммы 4.3:



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

Но не обязательно продолжать данный прямоугольник; можно начинать с совершенно произвольной первой строки длины 20, составленной из чисел 1,2,3,...,10.

[whitefox]

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

Ники на текущем форуме

Цитата:

??? whitefox

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

whitefox
раскройтесь, пожалуйста, вы участвуете в конкурсе?

Я в конкурсе не участвую.
Катастрофически мало времени
Просто ради интереса написал программу поиска диагональных решений.
Она, конечно же , переборная, но с ранним отсечением.
За доли секунды нашла решения C=3 N=9, C=4 N=16, C=5 N=25.
Не больше минуты ушло на доказательство отсутствия решений для C=3 N=10, C=4 N=17.
За пару секунд нашлось решение C=14 N=100.
И уже несколько часов работает над C=13 N=100.

[Nataly-Mak]

whitefox в сообщении #592074 писал(а):

Я в конкурсе не участвую.
Катастрофически мало времени

Жалко!

Цитата:

Просто ради интереса написал программу поиска диагональных решений.
Она, конечно же , переборная, но с ранним отсечением.
За доли секунды нашла решения C=3 N=9, C=4 N=16, C=5 N=25.
Не больше минуты ушло на доказательство отсутствия решений для C=3 N=10, C=4 N=17.
За пару секунд нашлось решение C=14 N=100.
И уже несколько часов работает над C=13 N=100.

Интересное исследование.

У вас программа написана для "длинной" характеристической строки?
То есть строка для квадрата NxN состоит из (2N-1) элементов. Это общий случай.
Получается, что для квадрата 100х100 характеристическая строка состоит из 199 элементов. Солидная строка.

[whitefox]

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

У вас программа написана для "длинной" характеристической строки?
То есть строка для квадрата NxN состоит из (2N-1) элементов. Это общий случай.
Получается, что для квадрата 100х100 характеристическая строка состоит из 199 элементов. Солидная строка.

Да, именно так.
Хотя некоторые решения оказываются диагональными в "строгом" смысле т.е. получаются ломанные диагонали с базовой строкой длины N.
Например, C=6 N=31

(Оффтоп)

A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,
B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,
C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,
D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,
E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,
F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,
A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,
B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,
C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,
D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,
E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,
F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,
B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,
A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,
A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,
B,A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,
A,E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,
E,E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,
E,B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,
B,E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,
E,C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,
C,C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,
C,F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,
F,C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,
C,D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,
D,F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,
F,D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,
D,F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,
F,C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,
C,D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,
D,A,B,C,D,E,F,A,B,C,D,E,F,B,A,A,B,A,E,E,B,E,C,C,F,C,D,F,D,F,C

[Nataly-Mak]

Посмотрела решение. Очень красивое!

svb сообщил, что он получил аналогичное диагональное решение 36х36.
Ещё, как я поняла, он сообщил, что такого "строго" диагонального решения C=10, N=100x100 не существует.

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

Да, забыл сказать. Для C=10 не существует диагональных квадратов 100x100, если рассматривать ломанные диагонали.

whitefox
Как вы оцениваете возможность существования
а) диагонального решения 100х100 для C=10;
б) любого решения 100х100 для С=10?

[whitefox]

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

whitefox
Как вы оцениваете возможность существования
а) диагонального решения 100х100 для C=10;
б) любого решения 100х100 для С=10?

Пока не доказано противное, считаю:
а) что для каждого $C$ существует диагональное решение $C^2\times C^2$ (возможно "нестрогое").
б) следует из а).

[Nataly-Mak]

whitefox в сообщении #592111 писал(а):

Пока не доказано противное, считаю:
а) что для каждого $C$ существует диагональное решение $C^2\times C^2$ (возможно "нестрогое").

Думаю так же.
Для С=2,3,4,5,6 диагональные решения С^2xC^2 уже найдены.
О решении для С=7 я пока не видела сообщения (может, пропустила?)

Кстати, всего за несколько минут построила в программе Эда диагональное решение C=7, N=25x25. Строится очень легко!



Это уже 27х27, дальше туго идёт расширение.

(Оффтоп)

27,27,G,B,F,D,E,F,D,A,B,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,B,F,D,E,F,D,A,B,C,D,E,F,G,B,C,D,E
,F,G,A,D,E,F,B,C,A,G,F,D,E,F,D,A,B,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,D,E,F,D,A,B,C,D,E,F
,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,E,F,D,A,B,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,F,D,
A,B,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,D,A,B,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,
G,B,G,G,E,C,A,B,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,B,C,D,E,F,G,B,C,D,E,F,G,A,
D,E,F,B,C,A,G,B,G,G,E,C,D,A,C,D,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,D,E,F,G,B,
C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,E,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F
,B,F,F,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,G,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,
G,E,C,D,A,F,B,F,E,E,B,C,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,C,D,E,F,G,A,D,E,F,B,
C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,E,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,E,F,G
,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,F,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,
C,D,D,A,C,G,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,C,B,A,D,E,F,B,C,A,G,B,G,G,E,C,D,
A,F,B,F,E,E,C,D,D,A,C,B,A,D,E,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,C,B,A,A,E,F,B,C,A,G,B,
G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,C,B,A,A,D,F,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,C,B,A,A,D,
G,B,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,C,B,A,A,D,G,E,C,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,
A,C,B,A,A,D,G,E,B,A,G,B,G,G,E,C,D,A,F,B,F,E,E,C,D,D,A,C,B,A,A,D,G,E,B,B

[Nataly-Mak]

Цитата:

Нашел забавную ссылку.
http://www.politforums.ru/culture/1335647064.html
С помощью рампределенных вычислений ищут 3 ортогональных латинских квадратов 10х10.
По участвовать чтоли?!

[цитата с форума ПЕН:
http://e-science.ru/forum/index.php?sho ... 028&st=220]

Pavlovsky
в одной из моих
статей есть идея - использовать для поиска 3-х попарно ортогональных ЛК 10-го порядка квази-разностные матрицы.
Эту идею пробовал реализовать tolstopuz.
Где-то в теме "Латинские квадраты" есть его сообщение по этому поводу.

Задача очень хорошая! Задача века
Обязательно поучаствуйте.

P.S. В указанной статье обратите внимание на рис. 36 и предшествующие примеры квази-разностных матриц для пар ортогональных ЛК чётного порядка.

[Alexu007]

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

Кстати, всего за несколько минут построила в программе Эда диагональное решение C=7, N=25x25. Строится очень легко!
...
Это уже 27х27, дальше туго идёт расширение.

Моя программа-рэндом нашла 7-33. Это говорит о чём? О том, что таких корректных квадратов ещё очень очень много среди бесчисленного множества случайных вариантов. Стоит ли удивляться, что "дальше туго идёт расширение"? Либо найденная математическая закономерность (и очень высокий результат), либо случайный подбор даже диагоналей, что ненамного проще простого рэндома...

Кстати, как вам мои (alexu007) успехи? С помощью рэндома я буду твёрдым середнячком.

Немного насчёт правил - может ли быть у разных игроков заигран совершенно одинаковый квадрат?

[svb]

Новая версия программы Эда
Инструкция к ней