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

[Pavlovsky]

Тоже опубликую картинку, просто так.

[Nataly-Mak]

Уф! "Десяточка" прошла
Ну, за остальные я уже не волнуюсь - дело техники, там все простые числа уже.

Так, а Алексей уже придумал расширение ещё на единицу.
Вот молодец! Завидую белой завистью

Кстати, а кто за кого болеет?
Я, конечно, только за Алексея. Дай Бог ему удержать первое место!

Цитата:

12 Jim Gillogly 19.210600 06-18-2012 @ 12:45:09
13 Natalya Makarova 19.210600 06-26-2012 @ 23:26:24

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

[Scryer]

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

А Джим тоже, небось, имеет новые результаты, с 18 июня затаился

Вы видите все мои результаты до сих пор - дела идут не быстро для меня.

         Джим

[Nataly-Mak]

Так вы и есть Джим???
Рада познакомиться

[dimkadimon]

Наконец нашёл диагональное решение 36х36 для 6 цветов. Красивое решение, но к сожалению совершенно не помогает найти 37х37. Так же не получилось найти диагональное решение 26х26 для 5 цветов, хотя 25х25 нахожу за минуту. Возможно диагональные решения не существуют для 17х17, 26х26 и 37х37. Сейчас попробую найти 49х49 для 7 цветов.

[Nataly-Mak]

Может быть, моя гипотеза верна: диагональное решение G(C,N) может иметь максимум N=С^2?

Уже найдены диагональные решения G(2,4), G(3,9), G(4,16), G(5,25), G(6,36).
И не найдены: G(2,5), G(3,10), G(4,17), G(5,26) и т. д.

[Nataly-Mak]

Да, много будет конкурсантов в зоне 19 баллов с хвостиком.
Вот и я вошла в эту зону
До джентльменского набора решений №1 мне осталось ввести решения для C=18,20,21.

Известные алгоритмы кончились. Теперь кто что придумает оригинальное.
Лидеры конкурса уже что-то оригинальное придумали. Молодцы!

[Pavlovsky]

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

Может быть, моя гипотеза верна: диагональное решение G(C,N) может иметь максимум N=С^2?

dimkadimon в сообщении #589559 писал(а):

Наконец нашёл диагональное решение 36х36 для 6 цветов. Красивое решение, но к сожалению совершенно не помогает найти 37х37. Так же не получилось найти диагональное решение 26х26 для 5 цветов, хотя 25х25 нахожу за минуту. Возможно диагональные решения не существуют для 17х17, 26х26 и 37х37. Сейчас попробую найти 49х49 для 7 цветов.

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

Диагонального решения для 17x17, C=4 тоже не существует.

Чего то все как то безрадостно. Получается реальный результат можно получить только для С=10 и более. Но при этом перебор скорее всего выйдет за рамки разумного.

[dimkadimon]

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

Чего то все как то безрадостно. Получается реальный результат можно получить только для С=10 и более. Но при этом перебор скорее всего выйдет за рамки разумного.

Да скорее имено так. Тоже самое произошло когда я пытался построить 66х66 для 8 цветов таким же методом как строился 18х18 из 4 цветов - даже близко решением не пахнет. А вот 18х18 из 4 цветов я могу найти примерно за час. Такое впечатление что "умные" методы перебора работают только для С<=6 для которых уже имеем хорошие результаты. А вот С>=10 они уже не тянут.

[Nataly-Mak]

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

Чего то все как то безрадостно.

У меня пока всё очень радостно
Я снова в первой десятке:

Цитата:

1 Alex Chernov 19.941400 06-24-2012 @ 17:12:15
2 Herbert Kociemba 19.891500 06-26-2012 @ 20:21:36
3 Dmitry Kamenetsky 19.888500 06-22-2012 @ 15:14:03
4 Nick Gardner 19.839200 06-21-2012 @ 15:41:06
5 Artem Karavaev 19.811800 06-24-2012 @ 14:23:02
6 Tom Sirgedas 19.766000 06-07-2012 @ 07:11:18
7 Il brigante Pennastorta 19.766000 06-08-2012 @ 16:28:33
8 Valery Pavlovsky 19.766000 06-15-2012 @ 11:02:58
9 Wes Sampson 19.643900 06-26-2012 @ 19:51:08
10 Natalya Makarova 19.576200 06-27-2012 @ 12:14:21

Не ввела ещё два решения: C=20,21.
Надеюсь, что это будет как раз джентльменский набор №1 и 19,766 баллов.

svb не вводит джентльменский набор решений.
Я верно предположила, что он вступит в игру, когда наберёт 19,99 баллов

[Pavlovsky]

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

rectangle-free-grid-coloring-21x12-grid

Сергей ты разбирался с этой статьей? Там при построении прямоугольника 21х12 какой то хитрый метод используется.

Цитата:

I have been playing around with the 21x12 solution to find the relationship between the color classes and the reduced latin squares of order 4, according to the Zarankiewicz Problem (see my upcoming paper).

[svb]

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

Сергей ты разбирался с этой статьей? Там при построении прямоугольника 21х12 какой то хитрый метод используется.

Когда я бегал по интернету, то просматривал очень бегло, выложил только 2 адреса, которые показались хоть чем-то интересными. В rectangle-free-grid-coloring-21x12-grid мне бросились в глаза последние картинки, но статью я даже не пытался читать.

Nataly-Mak

Цитата:

svb не вводит джентльменский набор решений.
Я верно предположила, что он вступит в игру, когда наберёт 19,99 баллов

Да я бы вступил в игру, но не умею этого делать - это, конечно, решаемо, но ... самое главное, хотелось бы найти для начала квадрат 441x441 или, хотя бы, 100x100.

[Nataly-Mak]

Уф! Запарилась со сборкой квадрата 381х381 для C=20
Программки у меня примитивные для сборки, ну кое-как собрала, отправила.
Осталось C=21.

На этом можно взять тайм-аут, отдохнуть, собраться с мыслями. Мысли все растеклись от жары, как мороженое собрать их в кучу очень трудно.

-- Ср июн 27, 2012 15:42:40 --

Постоять хоть рядом с умным человеком, может, ума наберусь

Цитата:

8 Valery Pavlovsky 19.766000 06-15-2012 @ 11:02:58
9 Natalya Makarova 19.766000 06-27-2012 @ 15:36:36

svb
присоединяйтесь, пока есть место в десятке

[svb]

Продолжение диагональной темы:

(Оффтоп)

A,A,A,A,B,B,B,B,C,C,C,C,D,D,D,D,
A,B,C,D,B,C,D,A,C,D,B,A,D,B,C,A,
A,C,D,B,B,D,A,C,C,B,A,D,D,C,A,B,
A,D,B,C,B,A,C,D,C,A,D,B,D,A,B,C,
B,B,B,B,C,C,C,C,D,D,D,D,A,A,A,A,
B,C,D,A,C,A,B,D,D,B,C,A,A,B,C,D,
B,D,A,C,C,B,D,A,D,C,A,B,A,C,D,B,
B,A,C,D,C,D,A,B,D,A,B,C,A,D,B,C,
C,C,C,C,D,D,D,D,A,A,A,A,B,B,B,B,
C,D,B,A,D,B,C,A,A,B,C,D,B,C,A,D,
C,B,A,D,D,C,A,B,A,C,D,B,B,A,D,C,
C,A,D,B,D,A,B,C,A,D,B,C,B,D,C,A,
D,D,D,D,A,A,A,A,B,B,B,B,C,C,C,C,
D,B,C,A,A,B,C,D,B,C,A,D,C,D,B,A,
D,C,A,B,A,C,D,B,B,A,D,C,C,B,A,D,
D,A,B,C,A,D,B,C,B,D,C,A,C,A,D,B

Вряд ли это можно считать подсказкой, т.к. самого главного пока нет

[Pavlovsky]

Так красивее.
A,B,C,D,A,A,A,B,B,B,C,C,C,D,D,D,
B,C,D,A,B,B,B,C,C,C,D,D,D,A,A,A,
C,D,A,B,C,C,C,D,D,D,A,A,A,B,B,B,
D,A,B,C,D,D,D,A,A,A,B,B,B,C,C,C,
A,B,C,D,B,C,D,C,D,A,D,B,A,B,C,A,
A,B,C,D,C,D,B,D,A,C,B,A,D,C,A,B,
A,B,C,D,D,B,C,A,C,D,A,D,B,A,B,C,
B,C,D,A,C,D,A,A,B,D,B,C,A,B,C,D,
B,C,D,A,D,A,C,B,D,A,C,A,B,C,D,B,
B,C,D,A,A,C,D,D,A,B,A,B,C,D,B,C,
C,D,A,B,D,B,A,B,C,A,B,C,D,C,A,D,
C,D,A,B,B,A,D,C,A,B,C,D,B,A,D,C,
C,D,A,B,A,D,B,A,B,C,D,B,C,D,C,A,
D,A,B,C,B,C,A,B,C,D,C,A,D,D,B,A,
D,A,B,C,C,A,B,C,D,B,A,D,C,B,A,D,
D,A,B,C,A,B,C,D,B,C,D,C,A,A,D,B