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

[Nataly-Mak]

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

Nataly-Mak

Цитата:

Спасибо за определение. Это, разумеется, в курсе высшей алгебры на первом курсе нам давали. Забыть за полвека немудрено!

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

Вам странно, что человек забыл за полвека то, что учил на первом курсе мехмата?
И что же вы видите в этом странного? Этот человек (то бишь моя скромная персона) тоже учился в основном на "отлично", в том числе и курс высшей алгебры был сдан на "отлично". И после того, как он был благополучно сдан, мне с ним встречаться больше не приходилось. Где-то лет через 30 я встретилась с необходимостью решать СЛУ, работая с магическими квадратами. Это была, пожалуй, первая встреча с высшей алгеброй с университетских времён. Ну, метод Крамера, конечно, помню. Больше ничего существенного, всё забыла.

Меня удивляет, что вам это кажется странным. На форуме ПЕН есть замечательная форумчанка Светлана Файнштейн, окончила мехмат МГУ, младше меня на 10 лет. Так она пишет на форуме, что начисто забыла всю математику! Вы удивлены??? Это притом, что Светлана и сейчас преподаёт в вузе. А я уже с 1994 г. вообще не связана даже с работой программиста в заводских условиях.

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

Цитата:

Да и ещё: полем может быть не только множество чисел. Правильно я понимаю?

Цитата:

Число ... задумайтесь, что это такое. К этой абстракции человечество шло очень долго. Два яблока - понятно, два пальца - понятно. Что же их связывает? Значок $2$? Но ведь это условность, мы могли бы использовать и другие значки. Помните рассказ Лема про гостиницу с бесконечным числом мест? Когда мы отображаем взаимно-однозначно конечное множество в себя, то образ этого отображения полностью совпадает с исходным множеством. Но вот человечество встретилось со странным множеством, которое этим свойством не обладает - это множество натуральных чисел. Если вы распишите эту ситуацию, то получите аксиомы Пеано

Опять мудрствования вместо прямого ответа на прямой вопрос.

Цитата:

Но вы не ответили на вопрос: как понятие "поля" относится к преобразованиям прямоугольников по лемме 4.3?

Цитата:

В этой лемме понятие поля не используется, а вот при поиске раскрасок для $C=p^s$ его можно использовать.

Разговор у нас шёл, как я помню (пока ещё!), именно об этой лемме, и вы тут ввернули понятие поля. А оно тут, оказывается, совершенно не к месту.

P.S. Извините, но мне кажется, нам пора прекратить "трёп" (следуя вашей терминологии).

[svb]

Поглядел на появившиеся тексты
Конечно, натуральные числа не являются полем, они даже не являются группой относительно операции сложения - необходимо добавить отрицательные числа.
Еще хуже с умножением . Например, у $2$ нет обратного элемента. Но вот $(2 \times 3)\mod 5=1$

Цитата:

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

Я забываю имена, могу и свое имя забыть, но забыть, что такое поле! Нужно еще немного подождать

Цитата:

Разговор у нас шёл, как я помню (пока ещё!), именно об этой лемме, и вы тут ввернули понятие поля. А оно тут, оказывается, совершенно не к месту.

Это он у вас шел А я уже давно говорю про другое. Пример с полем я привел, как пример среды и взаимодействия.

Цитата:

P.S. Извините, но мне кажется, нам пора прекратить "трёп" (следуя вашей терминологии).

Ваше дело

[Pavlovsky]

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

использование поля можно заменить на что-то другое?

Любую алгебраическую структуру можно заменить на полный перебор.

-- Вт июл 17, 2012 15:32:34 --

А если серьезно. Скажем мы ищем 10 сильно окрашенный прямоугольник 90х10. Нам надо описать множество таких прямоугольников. Найти опереции преобразования одного прямоугольника в другой. То есть определить различные изоморфные преобразования и симметрии. Ну и как вершина описать алгебраическую структуру этого множества. Алгебраических структур всяких море! Решетки, различные группы, кольца и поля.

[svb]

Pavlovsky

Цитата:

Любую алгебраическую структуру можно заменить на полный перебор.

Увы, практически невозможно, особенно в случае отсутствия решения

Цитата:

А если серьезно. Скажем мы ищем 10 сильно окрашенный прямоугольник 90х10.

Откажитесь от этой тропы.

[Pavlovsky]

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

Откажитесь от этой тропы.

Почему? Для начала можно поэксперементировать с 6-сильно раскрашенным прямоугольником 30х6.
Можно немного уменьшить размер. Пусть строки всегда есть в нашем прямоугольнике:

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

Остается прямоугольник 24х6. Причем во всех его строках все числа различные. То есть перестановки чисел 1-6. Вот у нас уже появилась регулярность!
Далее любые две строки могут иметь совпадение чисел только в одной колонке. Множество прямо на глазах становится структурированным.
При перестановке строк получается тоже 6 сильно окрашенный прямоугольник. Можно нормализацией объеденить решения в классы изоморфизмов.
При удалении строк, полученный прямоугольник тоже правильный. Вот вам отношение частичного упорядочивания. Можно строить решетку.

А дальше уже наверно можно перебором сформировать все решения. И поискать новые зависимости.

[svb]

Pavlovsky

Цитата:

Для начала можно поэксперементировать с 6 ...

Увы, $C=6$ достаточно неудачный пример для экспериментов. Вот взгляните на таблицу смещений квадратика $6 \times 6$

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

Для $C=10$ подобной таблицы уже нет Перебором это быстро проверяется. Иначе я уже выложил бы решение $100 \times 100$

[Pavlovsky]

Вау
http://infinitesearchspace.dyndns.org/c ... uares-n-c2
Появлися автор статьи для ёжиков! Bill Gasarch. Спешите воспользоваться шансом пообщаться!

[Nataly-Mak]

Внимание, господа!

Соревнование персональных соперников, Россия - Украина:

Цитата:

41 Alexu007 7.671630 07-17-2012 @ 23:21:43
42 Victor Dimitriev 7.531220 07-17-2012 @ 19:50:55

Оба соперника активизировались. Соревнование обещает быть интересным

-- Ср июл 18, 2012 00:44:36 --

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

Появлися автор статьи для ёжиков! Bill Gasarch. Спешите воспользоваться шансом пообщаться!

Спасибо за информацию.

Я уже пообщалась, как один из ёжиков

[Nataly-Mak]

Nick Gardner покинул компанию джентльменов и вошёл в компанию оригиналов.
Теперь оригиналов стало 7 человек.
Всего 7 не-ёжиков на конкурсе

[Nataly-Mak]

Конгениальную идею alexBlack отправила на форум конкурса

Биллу сообщаю, что область применения его леммы 4.3 может быть значительно расширена.
Заодно ссылку на наш форум ещё раз дала, привлекаю иностранцев в нашу тему

(Оффтоп)

Сильно Гугл напортачил с переводом?
Я несколько раз туда-обратно переводила. Надеюсь, что меня поймут.

-- Ср июл 18, 2012 07:40:08 --

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

Похоже С10N100 у меня не будет. Максимум чего смог выжать из своего подхода С10N91. Так бывает. Зато согрелся.

-- Сб июл 14, 2012 17:55:32 --

Вот такая строка для С=10 получилась. Закономерностей море.

(Оффтоп)

Что-то очень мало вы выжали из 85-символьной строки.
Прямоугольник 92х100 10-coloring из этой строки получается легко:



Прямоугольник 93х100 у меня получился всего с 20 ошибками, а содержащийся в нём квадрат 93х93 имеет всего 13 ошибок. Увы, без ошибок не получается

[Alexu007]

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

Соревнование персональных соперников, Россия - Украина:

Цитата:

41 Alexu007 7.671630 07-17-2012 @ 23:21:43
42 Victor Dimitriev 7.531220 07-17-2012 @ 19:50:55

Оба соперника активизировались. Соревнование обещает быть интересным

У меня остался небольшой резерв - не заполнены С20, 21, 22. И остальные крупные значения С можно попробовать увеличить. Дальше всё... Зато все мои квадраты уникальны, никакого копипаста. И все созданы рэндомной компьютерной программой, т.е. компьютер за меня вкалывает. А мозги у меня не для работы, мозгами я думаю!!!

[Nataly-Mak]

Alexu007 в сообщении #596429 писал(а):

А мозги у меня не для работы, мозгами я думаю!!!

Ой, а другие, по-вашему, что мозгами делают?

А у меня вот и компьютер отдыхает, и квадратов довольно много настроила

Ах да, копипаст есть, признаюсь: в самом начале, когда статьи просматривала, сразу скопировала решения С3N10 и C4N18. Вот тут можно было и подумать, но очень не хочется, когда есть готовые результаты Впрочем, решения C3N9, C4N16 я и сама построила.

Львиная доля времени у меня уходит на эксперименты. Собираюсь писать статью. Хотя думаю, что даже книжица получится, т.к. материалов очень много.

А кстати: поскольку решения C3N10, C4N18 уже всем известны, предлагаю выложить оригинальные решения для данных С, у кого они есть.
Мне очень понравилось решение Тома C4N18 (показано выше).

[Alexu007]

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

Ах да, копипаст есть, признаюсь: в самом начале, когда статьи просматривала, сразу скопировала решения С3N10 и C4N18. Вот тут можно было и подумать, но очень не хочется, когда есть готовые результаты Впрочем, решения C3N9, C4N16 я и сама построила.

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

[Nataly-Mak]

Любопытно: нерегулярное решение C3N9 элементарно получается в программе Эда:

9,9,A,A,B,C,C,B,C,B,A,C,C,B,B,B,A,C,A,A,A,B,C,B,A,C,C,B,B,B,A,A,C,B,B,A,A,B,C,B,C,A,C,B,A,C,A
,B,B,A,C,A,C,B,C,A,A,C,C,C,B,A,A,B,C,A,C,B,A,C,C,B,A,B,B,A,B,A,A,A,C,C,C

А решение C3N10 уже никак, вот покрутила, с 6 ошибками:

10,10,A,A,B,C,C,B,C,B,A,B,C,C,B,B,B,A,C,A,A,A,A,B,C,B,A,C,C,B,B,A,B,A,A,C,B,B,A,A,B,C,C,B,C,A
,C,B,A,C,A,C,B,B,A,C,A,C,B,C,A,B,A,C,C,C,B,A,A,B,C,B,A,C,B,A,C,C,B,A,B,C,B,A,B,A,A,A,C,C,C,C,
C,A,A,A,B,C,B,B,C,A

Alexu007
интересно, что дал вам рэндом для C=3, C=4?
Думаю, что C3N9 вы получили, а вот C3N10 вряд ли. Не даст, скорее всего, рэндом и решение C4N18, даже и C4N17 не даст.

Кстати, кто-то на форуме конкурса сообщал, что по алгоритму получает решение C4N18 за считанные секунды. Это должен быть красивый алгоритм.

-- Ср июл 18, 2012 09:19:39 --

Здесь в решении C3N10 уже всего 3 ошибки и эти ошибки, похоже, фатальные:

10,10,A,A,A,C,C,B,C,B,B,A,C,B,A,B,B,C,B,A,A,C,A,B,C,C,A,C,A,A,B,B,C,A,C,A,C,A,B,B,C,B,B,B,C,A
,C,B,A,C,A,C,B,C,B,A,C,C,B,A,B,A,B,C,A,C,B,A,A,B,C,C,C,C,B,B,A,A,C,B,A,A,B,A,A,B,A,C,C,C,C,B,
C,A,B,C,B,B,A,C,A,B

[Alexu007]

2-4, 3-10, 4-15, 5-20, 6-28, 7-33, 8-43, 9-48, 10-60

Моё решение 3-10:

1,3,3,1,2,3,2,1,3,2,
3,3,1,3,1,2,1,1,2,2,
2,3,1,1,3,1,2,3,2,1,
1,2,3,3,2,1,1,2,2,3,
2,1,2,3,2,2,3,1,3,1,
1,2,2,3,1,3,2,3,1,1,
1,1,1,2,3,2,2,2,3,3,
3,1,2,1,3,3,1,2,1,2,
2,2,3,2,3,1,3,1,1,2,
3,1,2,2,1,1,3,3,2,3