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

[Pavlovsky]

Удалено

[whitefox]

Pavlovsky

Большое спасибо, что откликнулись на мою просьбу.

[Pavlovsky]

Проверил доказательство Tom Sirgedas о невозможности C5N28. Вроде все чисто.

[Nataly-Mak]

Продолжаю теоретические исследования.
Пока меня очень занимает наша с svb лемма.
Удалось составить прямоугольник 25х50 с (10,5)-раскраской в соответствии с требованиями данной леммой.



Применила к этому прямоугольнику лемму, получился прямоугольник 25х100 10-coloring.

Теперь дело за маленьким : составить прямоугольник 100х50 с такими же свойствами
[(10,5)-раскраска в соответствии с требованиями леммы].

Ну, для начала можно составить прямоугольник 95х50, ведь решение 95х95 для С=10 тоже пока не получено.

[Pavlovsky]

По мотивам доказательства Tom Sirgedas.

Утверждение. В решении C5N26 нет строк (колонок) в которых размещено 9 и более единичек.
Доказательство.
Количество единичек должно быть >=26*26/5=135.2. То есть как минимум 136.

Пусть в некоторой строке есть 9 или более единичек. Переставим строки (колонки), что бы эти 9 единичек были в первой колонке в первых 9-ти строках. Тогда в этих 9-ти строках может быть не более 9+25=34 единичек. Получается оставшиеся 136-34=102 единичек будут в оставшихся 26-9=17 строках. Распределим эти единички равномерно по колонкам (почему позже). Получится 24 колонок по 4 единички, 2 колонки по 3 единички. 24*4+2*3=102. 4 единички дают нам 4*3/2=6 одноцветных пар, 3 единички дают нам 3*2/2=3 одноцветных пар. Тогда всего у нас 24*6+2*3=150 одноцветных пар. Можно убедиться, что равномерное распределение единичек по колонкам дает нам минимальное количество одноцветных пар. Но в 17 строках может быть всего 17*16/2=136 одноцветная пара. Получили противоречие.

[Nataly-Mak]

Какая-то непонятная пошла игра: пишем-стираем

Бегу со всех ног читать (уведомление в почту приходит, что есть новое сообщение), а читать-то и нечего.

[svb]

Pavlovsky

Цитата:

удалено

А я опять не успел прочитать

[Nataly-Mak]

Дык и я не успела

Pavlovsky
положите пост на место

Ага, уже положили...

[Pavlovsky]

Положил.
Идея в доказательстве Tom Sirgedas очень полезная вещь. Скажем ищем перебором решение C5N26, заполняя по-строчно последовательно числа 1,2,... Тогда мы достаточно точно можем определить можно ли оставшийся прямоугольник MxN заполнить K символами x.

[Nataly-Mak]

Итак, невозможность построить решение C5N28 доказана.
Вот что пишет конкурсант о решении C5N27:

Цитата:

For a while I fiddled with C=5 N=27 as a 3x3 grid of 9x9 sections, trying to find some symmetry, but I gave up after not finding anything. I figured C=4 fits nicely with rotational symmetry (and with 4 quadrants) but C=5 fits less nicely with a grid based on 3x3.

I actually wonder whether C=8 is a better candidate for a symmetry based solution > C^2.

[цитата с форума конкурса]

Как я поняла, он пытался строить это решение из квадратов 9х9, но ничего не нашёл.
Правда, ещё не факт, что это решение не существует. Строгого доказательства пока нет.

-- Сб июл 14, 2012 10:24:04 --

Вот это что за схемы тут? Может, какая польза от них?



Это я у Тома скопировала по ссылке:
http://content.screencast.com/users/Tom ... 1_2341.png

Там у него ещё есть одна ссылка на картинку, не смотрела ещё, что там.
Вот следующая картинка:



Как я понимаю, конструируется решение C3N10. Только как конструируется, ни фига не понимаю
А интересная схема. В подквадратах 4х4 и 6х6 символ X поставлен на диагонали; в прямоугольниках этот символ расставлен другим способом. Обратите внимание: в итоге этот символ занимает 34 ячейки. Всё очень красиво! Потом расставляется второй символ - *

Картинка скопирована по ссылке:
http://screencast.com/t/5pWpGCAga

-- Сб июл 14, 2012 10:52:16 --

И обалденно красивое решение C4N18 тут

Я его сейчас переведу в программу Эда и с подквадратами 9х9 покажу.

[ogaman]

Господа, ваш подвижнический труд восхищает: я одним глазом наблюдаю за вашей дискуссией, насколько это возможно - к сожалению, времени в обрез. Вы не приведете оптимальные решения для C=4 и C=3, желательно в цифровой форме? Как я понял, для C=5 проблема еще далека от завершения: каковы подвижки для нее?

[Nataly-Mak]

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

И обалденно красивое решение C4N18тут

Я его сейчас переведу в программу Эда и с подквадратами 9х9 покажу.

Вот оно:

[Pavlovsky]

Еще раз по мотивам доказательства Tom Sirgedas.
Невозможны следующие решения:

C2N5
C3N11
C4N19
C5N28
C6N40
C7N54
C8N70
C9N88
C10N107
C11N129
C12N153
C13N179
C14N207
C15N237
C16N269
C17N302
C18N338
C19N376
C20N416
C21N458

[Nataly-Mak]

Как-то всё очень далеко.
По поводу ближайших интересующих нас решений - C5N26, C6N37, C10N100 - ничего и нет.

[Nataly-Mak]

Это решение получено на основе двух ортогональных ЛК 10-го порядка по базовому алгоритму №1 - прямоугольник 30х100 10-coloring.
Раньше я показала часть этого прямоугольника - квадрат 30х30.