Время: месяц (1 октября — 31 октября 2010 г.). Конкурс завершён. Итоги

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

Это третий конкурс. Призовой фонд 3000 р. (на два призовых места: 2000 р. + 1000 р.). Задача следующая. Имеется квадратная решётка с нечётным числом вершин. Сколько на ней существует простых циклов с максимальной длиной? Поясню условия. Квадратная решётка — это целочисленные точки координатной плоскости, связанные по принципу ближайшего соседства. Обозначается Pn×Pn. Данное обозначение связано с тем, что целочисленный квадрат является прямым произведением двух цепей из n звеньев. Цепь из n звеньев обозначается через Pn.

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

В данной задаче нас интересуют только квадратные решётки с нечётным числом вершин, то есть P2n+1×P2n+1. Циклы максимальной длиной в таком графе будут иметь длину (2n+1)2-1. Будем такие циклы называть «предгамильтоновыми». Дело в том, что вообще-то интерес представляют гамильтоновы циклы, но их на нечётных решётках не существует. На рисунке ниже представлен пример «предгамильтонового» цикла на решётке 7×7.

Пример цикла длиной 48 на решётке размером 7x7
Рисунок 1 — Пример цикла длиной 48 на решётке размером 7×7

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

Советую также ознакомиться с FAQ.

В чём смысл и кому это нужно?

Это задача, имеющая реальное практическое приложение в физике полимеров. Что такое полимер? Это высокомолекулярное соединение, по сути – большая молекула. Например, шерсть, шелк, некоторые виды краски, полистирол, капрон и т. д. — это полимерные материалы. Вообще, повсюду полимеры, поэтому они настолько важны, что лет 60 назад физика полимеров стала отдельным научным направлением. Полимер удобно моделировать в виде цепочки, узлы которой проходят через точки воображаемой трехмерной решётки.

Пример полимера
Рисунок 2 — Пример полимерной цепочки и глобулы

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

Итак, решётка – это среда для выращивания полимера, а сам полимер – это любая простая цепочка на этой решётке. Если полимер плотно упакован (глобула, на рис. 2 справа), то цепочка будет проходить через все узлы воображаемой решетки, то есть будет гамильтоновой. Кроме того, цепочка может замкнуться сама с собой, образуя цикл. Наша задача – искать именно циклы, поскольку это проще, чем искать пути.

Зачем считать количество циклов? Физиков интересует так называемая энтропия системы – один из термодинамических потенциалов, с помощью которого можно получить различные свойства системы. Если не вдаваться в подробности и формулы, то энтропия в данном случае равна логарифму от числа всех возможных конформаций полимера, то есть от числа всех циклов. Другой вопрос: зачем знать точное количество циклов? На самом деле, конечно, точное количество знать не нужно, но для того, чтобы вывести приближённую формулу, которую смело можно будет обобщать для очень больших значений n, необходимо отыскать так называемую константу связности для циклов на решётке. Эта константа может быть найдена приближённо, если посчитать точный ответ для как можно большего количества решёток. Чем больше решёток насчитаем, тем точнее получится константа. Для чётных решёток она равна примерно 1.4728. То есть число циклов на любой чётной решётке, размером m×n будет иметь порядок O(1.4728m×n).

Для квадратной решётки с чётным числом вершин задача была решена для P22×P22. Результаты есть в энциклопедии OEIS под номером A003763. Поэтому я предлагаю теперь решить задачу для нечётных решёток.

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

Положения

Общие правила и ограничения

Решайте задачу как угодно, считайте на чём угодно. Побеждает тот, кто предоставит ответ для наибольшего возможного значения n. В целях борьбы с беспределом кое-какие ограничения все же будут.

  1. Предоставляя ответ для некоторого n участник обязан сказать ответ также для всех значений k<n. Разумеется, не надо повторять те числа, которые уже записаны в таблице результатов ниже. Например, если лидер сказал ответ для n=3, а Вы посчитали до n=5, то ответ засчитывается только если Вы также называет ответ для n=4.
  2. Победители конкурса обязуются предоставить мне полный исходный код (не важно, на каком языке, только, пожалуйста, не на эзотерическом типа BrainFuck : ) ) после его окончания.
  3. Я, автор конкурса, тоже принимаю в нём участие на равных с остальными. Почему? Хочу победить, так как призовой фонд составляет больше половины моей месячной зарплаты. Я её просто так не отдам : )
  4. Конкурс завершается 31 октября 2010 г. ровно в 12 ч. 00 м.
  5. Приз можно получить только через Яндекс.Деньги или WebMoney.
  6. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой типа «Циклы на нечетной решетке – Конкурс». В письме необходимо указать свой ник, значение n, для которого был посчитан ответ и сам ответ. Также требуется указать, на чём выполнялось вычисление (сколько ядер) и сколько минут (или часов (или дней)) заняли расчёты для указанного n. Будет вестись рейтинговая таблица, в которой указываются все участники и их результаты.
  2. Чтобы переместиться по рейтинговой таблице вверх, нужно указать ответ для того значения n, которое больше, чем у текущего лидера. То есть, если у лидера n=3, то Вам надо как минимум сказать ответ для n=4, иначе попытка не засчитывается.
  3. Почта проверяется случайным образом (не меньше одного раза в сутки), поэтому может возникнуть ситуация, когда несколько участников предоставляют одно и то же число, но кто-то раньше, а кто-то позже. В этом случае сравнивается дата попадания письма в ящик конкурса.
  4. Победителем считается тот, кто назвал ответ к задаче для наибольшего возможного n, а также прислал (по требованию) полный исходный код программы по истечении конкурса. За победу 2000 р.
  5. Второе место занимает тот, кто окажется в финальной рейтинговой таблице под номером два (если под номером два тот же, кто и под номером один, то берётся следующая позиция и т. д.) и пришлёт (по требованию) полный исходный код программы по окончании конкурса. За второе место 1000 р.

Гарантии

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

Пожелания

По мере проведения конкурса привлекайте новых участников. Мой блог не так сильно раскручен, поэтому участие хотя бы 10 человек я буду считать большим успехом. Не надо думать, что этим конкурсом я оптимизирую блог (как меня постоянно обвиняют). Если бы я хотел это сделать, то на 3000 р. просто купил бы ссылок.

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

Если пишете комментарии, то подписывайтесь тем ником, который у вас отображается в таблице рейтинга (если отображается).

Чтобы не оказаться разочарованным, убедитесь, что на вашем компьютере достаточно оперативной памяти. Если у Вас меньше 2 Gb, то соревнование может оказаться бессмысленным.

Текущий рейтинг

Таблица ниже будет постоянно обновляться по мере поступления новых чисел. Внимание: прежде чем присылать число, убедитесь, пожалуйста, что до Вас его ещё никто не вывел. Удачи!

Таблица участников

Конкурс завершён. Итоги

  1. Zealint :: 18.10 :: n = 10 :: 8 ядер (2.67 GHz) :: 6 д. 7 ч. 27 мин.
  2. Zealint :: 07.10 :: n = 9 :: 1 ядро (2.67 GHz) :: 18 ч.
  3. alexBlack :: 06.10 :: n = 8 :: 1 ядро (2.9 GHz) :: 200 мин.
  4. alexBlack :: 06.10 :: n = 7 :: 1 ядро (2.9 GHz) :: 6 мин.
  5. alexBlack :: 06.10 :: n = 6 :: 1 ядро (2.9 GHz) :: 16 c.
  6. alexBlack :: 06.10 :: n = 5 :: 1 ядро (2.9 GHz) :: 1 c.
  7. alexBlack :: 06.10 :: n = 4 :: 1 ядро (2.9 GHz) :: 0 c.
  8. Silent :: 04.10 :: n = 3 :: 1 ядро (2 GHz) :: 20-40 мин.
  9. Zealint :: 01.10 :: n = 2 :: 1 ядро (3 GHz) :: 0 с.
  10. Zealint :: 01.10 :: n = 1 :: 1 ядро (3 GHz) :: 0 с.

Если Вы хотите оказать безвозмездную материальную помощь на проведение конкурсов, можно сделать это через Яндекс.Деньги [ 41001260825785 ] или WebMoney [ R204587204793, Z334185961044 ].

Таблица значений

Таблица значений n и количества циклов длиной (2n+1)2-1 на решётке размером (2n+1)×(2n+1).

  1. 5
  2. 226
  3. 255088
  4. 6663430912
  5. 3916162476483538
  6. 51249820944023435573470
  7. 14870957102232406137455708164254
  8. 95494789899510664733921727510895952184006
  9. 13559554600804304977439766815372028940021573343275526
  10. 42557777273614434293884765869188518513149602332875710275078966598

Следите за конкурсами на моём блоге. Дальше будет сложнее и интереснее.

Информационные спонсоры

КиберФорум — форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных. Компьютерный форум.

Клуб ПРОграммистов — Форум программистов.

dxdy — Научный форум.

Обсуждение конкурса на форуме в этой теме.