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

alexBlack · 02/05/10 26

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

Почему неявно?
Насколько могу читать по-английски, это явно присутствует в доказательстве леммы 4.3.
Впрочем, я могу ошибаться, т.к. читать по-английски не умею.

Да, явно. Это я давно не смотрел в grid.dbf.

Nataly-Mak писал(а):

ещё половинку расширения можете сочинить?

Вот если бы в исходном прямоугольнике не было четных пар, хотя бы в некоторых колонках...

Код:

1 2 1 4 1 1 2 4 4 2   3 3 4 3 2 3 3 4 2 2 4   5 5 x 5 x 5 x 2 4 x 2 
5 4 3 5 2 2 1 5 4 3   3 1 2 5 1 4 4 3 1 2 5   5 3 x 1 x 2 x 5 3 x 1 
4 2 5 3 3 2 5 3 2 4   3 2 4 1 5 5 4 1 5 4 2   5 4 x 3 x 1 x 3 1 x 4 
3 1 2 4 4 2 4 1 3 5   3 5 3 4 2 2 4 2 3 5 1   5 1 x 2 x 4 x 4 5 x 3 

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

То есть для 4-х строк 7 столбцов расширения получилось?

Уже хорошо

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

Подозреваю, что при $\mathrm{N}>\mathrm{C^2}$ редукция в принципе не возможна, ни при использовании
сильной $\mathrm{C}$ -раскраски ни при использовании сильной $(\mathrm{C}{,}\mathrm{C'})$ -раскраски.

Для получения этих решений нужно использовать какие-то, совершенно другие, идеи.

Для получения решения C5N26

идея №1: заполнять квадрат 26х26 сначала единичками (их надо записать в квадрат не менее 136), потом двойками и т.д.

Вроде записать 136 (или более) единичек в квадрат 26х26 возможно.

идея № 2: построить квадрат 26х26 из 4-х подквадратов 13х13, например, так, как это сделал Tom Sirgedas: его квадрат 18х18 (С=4) я показала выше. Он составил этот квадрат из 4-х подквадратов 9х9 с очень изящной симметрией.
Наверняка Том работает в этом направлении с подквадратами 13х13.
Или же так, как это сделали немцы, составив квадрат 18х18 (С=4) из подквадратов 6х6.

У кого есть ещё идеи построения решения C5N26?
А вообще-то, как правильно сделал Том, начать надо с доказательства существования/несуществования этого решения. Может быть, Том как раз думает над этим доказательством.

Да, и почему собственно нельзя применить МБ-лемму?
Выше я показала пример (5,2)-сильной раскраски в смысле этой леммы, которая прекрасно расширилась до 29 столбцов, правда, не для всех строк исходного прямоугольника.
Не утверждаю, что возможно составить такой исходный прямоугольник, который даст нужное расширение до 26х26.

-- Вс июл 15, 2012 21:15:00 --

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

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

Прямоугольник 6х11 strong (5,2)-coloring:

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

Где в этом прямоугольнике, хотя бы один полу-прямоугольник? Сдается мне, что этот прямоугольник 6х11 5-strong coloring.

Раскраска strong c-coloring сильнее любой раскраски (c,c')-coloring, поэтому к такой раскраске, конечно, применима лемма 4.3, что я и продемонстрировала на этом примере.

-- Вс июл 15, 2012 21:28:38 --

А на конкурсе полнейший штиль, за весь день введён только один результат; вчера не введено ни одного результата, позавчера - один результат.
Ну, и не права ли я в том, что 3 месяца - это слишком много для конкурса?! Вполне хватило бы и двух.
Впереди ещё полтора месяца вот такой спячки. Скучно!
Для тех, кого задача зацепила, Нил неоднократно повторяет, что можно вводить новые результаты и после окончания конкурса. Так вот и вводите на здоровье свои значимые результаты хоть через год

А что делать тем, у кого значимых результатов нет и не предвидится? Правильно - спать.

Ну никак не хочу крутить переборные программы. Неинтересно это!
Конечно, если в основе перебора лежит какой-то интересный алгоритм, тогда да, можно и покрутить. А крутить, к примеру, достраивание - "вытряхивание блох" - нет, скучно!

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

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

Любой 5-сильно окрашенный прямоугольник 26х6 имеет не менее 15 ошибок.

5-сильно окрашенный прямоугольник 26х6 не существует.
Sirgedas
26*6=156. 156 ячеек распределим равномерно (почему равномерно больше объяснять не буду) по 5-ти цветам. 156=31*4+32*1. 31 символ можно распределить равномерно по 6-ти колонкам так: 31=1*6+5*5. Такое распределение дает 1*(6*5/2)+5*(5*4/2)=65 одноцветних вертикально расположенных пар. 32 символа можно распределить равномерно по 6-ти колонкам так: 32=2*6+4*5. Такое распределение дает 2*(6*5/2)+4*(5*4/2)=70 одноцветних вертикально расположенных пар.
Итого одноцветных пар будет как минимум 4*65+1*70=330. А всего вертикально расположенных пар может быть 26*25/2=325. Значит обязательно есть минимум 5 пар строк, где есть две вертикально расположенные одноцветные пары.

На форуме конкурса доказали, что даже 26х2 5-strong не существует:

Цитата:

Even a 26x2 strong colouring is impossible. Proof:

With only 5 colours there are 5 x 5 = 25 pairs of colours. In the 26th row you must therefore repeat a pair and thus produce a colouring that is not strong.

This does not necessarily mean that C=5 N=26 is impossible, because there are ways to colour that don't rely on strong colourings.

(Note: 'strong colouring' here is as defined in grid.pdf)

Но пока не доказано, что решение C5N26 не существует.

-- Пн июл 16, 2012 08:14:13 --

Кстати, выше я уже приводила демонстрацию идеи №1:

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

Два подквадрата 13х13 5-coloring уже построила :roll:

они прекрасно уживаются в квадрате 26х26:

Но очень может быть, что к этим двум подквадратам не удастся добавить больше ничего.
Демонстрация идеи, так сказать :-)

Чем плохая идея?

Pavlovsky
вам, как асу по доказательствам, предлагается доказать, что приведённая конструкция не имеет продолжений, ведущих к успеху.

Pavlovsky · 21/02/10 1594 Екатеринбург

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

идея №1: заполнять квадрат 26х26 сначала единичками (их надо записать в квадрат не менее 136), потом двойками и т.д.

Для начала надо найти хотя бы одно решение 26х26 заполненное единичками. У Tom Sirgedas есть такое решение. А у наших такое решение есть? В идеале надо найти все не изоморфные решения.

К решению можно предъявить дополнительные требования.

5 цветов распределить так первый цвет 136 штук, остальные цвета по 135 штук. 136*1+135*4=676=26*26.
136 распределить по колонкам(строкам) в 6-ти колонках 6 символов, в 20-ти колонках 5 символов.6*6+20*5=136.
135 распределить по колонкам(строкам) в 5-ти колонках 6 символов, в 21-ти колонках 5 символов.5*6+21*5=135.

Равномерное распределение всегда самое лучшее!

-- Пн июл 16, 2012 10:17:50 --

идея № 3: Можно еще все таки посмотреть возможность построения C5N26 по МБ-лемме.

Для этого надо построить прямоугольник 26х13. Даже можно обойтись прямоугольником 21х13 с дополнительным условием. В одной строке в колонках с номерами с равным остатком от деления на 5, не должно быть одинаковых чисел. При этом появляется возможность достроить 5 строк уже после репликации.

Интересно, диагональные алгоритмы способны построить прямоугольник 21х13 удовлетворяющий МБ-лемме и дополнительному условию?

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

идея № 3: Можно еще все таки посмотреть возможность построения C5N26 по МБ-лемме.

Для этого надо построить прямоугольник 26х13. Даже можно обойтись прямоугольником 21х13 с дополнительным условием. В одной строке в колонках с номерами с равным остатком от деления на 5, не должно быть одинаковых чисел. При этом появляется возможность достроить 5 строк уже после репликации.

Вы себе противоречите. Выше вы полностью согласились с whitefox в том, что решение C5N26 невозможно построить с помощью репликаций.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Ещё один эксперимент на применение МБ-леммы.
Это прямоугольник 12х13 с (5,2)-сильной раскраской по МБ-лемме:

Код:

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

Обычная репликация опять не прошла. А вот замена по схеме alexBlack получилась, результат - решение 12х26 5-coloring:

Код:

26,12,E,B,B,C,E,E,A,B,B,D,A,C,C,A,D,D,E,A,A,C,D,D,B,C,E,E,B,B,D,A,E,B,E,E,E,A,C,D,E,D,D,B,C,
A,D,A,A,A,C,E,B,A,A,D,A,C,C,A,B,D,A,A,B,D,B,C,B,C,E,E,C,D,B,C,C,D,B,D,E,C,C,D,C,B,B,E,B,C,D,
E,A,A,E,E,B,E,D,D,A,D,E,B,A,C,C,C,D,B,E,C,B,C,A,E,E,B,D,E,E,B,D,A,E,D,E,C,A,A,D,B,B,A,E,A,B,A
,D,C,B,B,A,E,B,D,C,A,C,D,C,B,E,D,D,C,A,D,D,D,C,B,B,D,A,A,A,D,D,A,E,B,B,E,D,D,B,C,C,C,B,B,C,A
,D,E,D,D,A,E,C,B,C,A,E,E,B,B,A,B,B,C,A,E,D,E,C,A,A,D,A,A,C,E,B,B,C,B,D,E,C,B,C,C,C,E,A,D,D,E,
D,B,A,E,D,E,C,B,E,E,C,E,E,D,D,B,D,A,D,E,D,A,A,E,A,A,B,B,D,B,C,B,B,A,A,D,A,C,E,A,D,D,B,C,A,D,
C,C,B,C,E,A,C,B,B,D,E,C,C,E,B,D,D,D,D,A,E,C,A,D,D,E,A,D,B,B,B,B,C,A,E,C,B,B

В общем, не всё так плохо на этом пути. Почти половина квадрата 26х26 готова

alexBlack
спасибо за идею замены!

-- Пн июл 16, 2012 12:11:51 --

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

Для начала надо найти хотя бы одно решение 26х26 заполненное единичками. У Tom Sirgedas есть такое решение. А у наших такое решение есть?

В этом решении цвета расставлены так:

цвет А - 135 ячеек
цвет В - 136 ячеек
цвет С - 135 ячеек
цвет D - 136 ячеек
цвет Е - 134 ячейки

В решении 60 ошибок. Мастера по "вытряхиванию блох" могут потрясти

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

Опа! не получится с цветом В, он даёт ошибки. И цвет D тоже даёт ошибки. Всё плохо, а я было обрадовалась - 136 единичек есть в решении

whitefox · 19/12/10 1546

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

Вы себе противоречите. Выше вы полностью согласились с whitefox в том, что решение C5N26 невозможно построить с помощью репликаций.

А в чём Вы видите противоречие?
Это всего лишь reductio ad absurdum (сведение к абсурду).

alexBlack
Вот Вам ещё одно значение термина редукция (сведение).

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

А в чём Вы видите противоречие?

Думаю, что Pavlovsky меня понял.

-- Пн июл 16, 2012 20:47:59 --

По поводу терминов "репликация"и "редукция"...
В лемме 4.3 говорится о том, что исходный прямоугольник nxm превращается в прямоугольник nx(km)

[заменила x на k, чтобы не спутать с предыдущим символом "x"].

Предлагаю термин "k-расширение" по лемме 4.3.
У кого есть другие предложения?

whitefox · 19/12/10 1546

Думаю, что меня он тоже понял.
Ведь это фактически идея доказательства не возможности построить C5N26 редукциями.

Надо только предположить существование (5,2)-окраски (по МБ-лемме) прямоугольника 26х13, и вывести отсюда существование 5-сильной окраски прямоугольника 26х2 (не возможность существования которой доказана, по Вашим же словам). Вот и получили абсурд.

-- 16 июл 2012, 20:00 --

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

Предлагаю термин "k-расширение" по лемме 4.3.
У кого есть другие предложения?

Термин подходит для процесса получения "расширенного" прямоугольника из исходного.
А как назвать процесс получения отдельной репликации исходного прямоугольника (т.е. редукцию)?

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

Ведь это фактически идея доказательства не возможности построить C5N26 редукциями.

Надо только предположить существование (5,2)-окраски (по МБ-лемме) прямоугольника 26х13, и вывести отсюда существование 5-сильной окраски прямоугольника 26х2 (не возможность существования которой доказана, по Вашим же словам). Вот и получили абсурд.

То есть вы хотите сказать, что в прямоугольнике 26х13 (5,2)-окраски по МБ-лемме обязательно найдутся 2 столбца с сильной окраской? Это очевидно? Я пока сильно не вдумалась.

Цитата:

Предлагаю термин "k-расширение" по лемме 4.3.
У кого есть другие предложения?

Цитата:

Термин подходит для процесса получения "расширенного" прямоугольника из исходного.
А как назвать процесс получения отдельной репликации исходного прямоугольника (т.е. редукцию)?

Ну, давайте назовём единичным расширением или разовым.

Но почему "редукция"?
Открываю словарь, читаю: "Редукция - переход, сведение сложного к простому. ||Уменьшение, ослабление чего-л. в каком-л. отношении.
(от лат. reductio - возвращение, отодвигание назад)"

Не вижу даже близкого значения к той операции, которой вы присвоили это название.

А слова "репликация" в моём словаре вообще нет (словарь довольно солидный, 4-томный, академическое издание).
У кого есть это слово в словаре, приведите, пожалуйста, его значение.

-- Пн июл 16, 2012 21:38:34 --

Вот что выдал Яндекс:

Цитата:

Репликация (позднелат. replicatio — повторение, от лат. replico — обращаюсь назад, повторяю), редупликация, ауторепродукция, аутосинтез, протекающий во всех живых клетках процесс самовоспроизведения (самокопирования) нуклеиновых кислот, генов…

Вроде к единичному расширению этот термин подходит. И всё же у нас не "повторение", не "копирование", а преобразование исходного образца.

svb · 20/01/10 766 Нижний Новгород

По поводу терминов редукция и репликация.
Из Вики:

Цитата:

Редукция в логике и математике — логико-методологический приём сведения сложного к простому.

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

whitefox · 19/12/10 1546

Цитата:

Редукция (лат. reductio — сведение, возведение, приведение обратно)

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

-- 16 июл 2012, 20:54 --

Согласен на замену термина "редукция" термином "трансформация" :-)