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

[dimkadimon]

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

Решение С=4, N=7x7 "ход конём"



Интересно, для каких C и N существуют решения "ход конём"?
Такие решения очень просто составлять.

А что значит ход конем? Не понимаю как вы составили ето решение.

[Pavlovsky]

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

А что значит ход конем? Не понимаю как вы составили ето решение.

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

Диагональное решение фактически выглядит так. Через квадрат проводим пучок параллельных прямых. Далее раскрашиваются эти прямые. Но ведь через квадрат не обязательно проводить прямые под углом 45 градусов(диагонали). Можно проводить пучок параллельных прямых под любым углом! Например прямые с соотношением 1:2.

[Nataly-Mak]

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

А что значит ход конем? Не понимаю как вы составили ето решение.

Вы не играете в шахматы?

-- Пн июн 25, 2012 17:22:36 --

dimkadimon
а почему же вы не ответили на мой вопрос о прямоугольниках C^2x(C^2+C) C-coloring, которые я построила и показала?
Вы не знаете ответ?

Вот сейчас построила четвёртый вариант прямоугольника 9х12 3-coloring.
Показываю:



Этот вариант правильный? То есть соответствует ли он алгоритму теоремы 4.12?

Он мне нравится больше первых трёх вариантов

[svb]

Nataly-Mak

Цитата:

Как я понимаю, вы не знаете ответ на мой вопрос: соответствуют ли построенные мной прямоугольники C^2x(C^2+C) алгоритму теоремы 4.12.

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

Цитата:

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

Пытался и продолжаю пытаться - особенно интересна лемма 4.11, но о ней хорошо писал Павловский. Но зачем мне сейчас прямоугольники, если я не знаю, как его расширять до квадрата? Программа Эда плохой помощник при стороне квадрата 361

Цитата:

Заодно похвалились своими успехами.
Значит, джентльменский набор решений вы тоже получили

Цитата:

Толковый перевод, не правда ли?
По такому переводу даже будучи семи пядей во лбу понять что-либо абсолютно невозможно.

Но я формулировку теоремы поняла без перевода.

Кто же формулы переводит? Гугл не виноват, когда он видит странные вкрапления, то перестает понимать, что от него требуют Раньше он даже при переносе предложения на новую строку спотыкался - приходилось ему скармливать подготовленные предложения.

[Nataly-Mak]

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

Если бы они ей соответствовали, то вы бы не спрашивали

Не поняла! Замысловатая логика.

Я не знаю, соответствуют или нет, потому что не знаю алгоритм теоремы 4.12, вот поэтому и спрашиваю.
Они вполне могут соответствовать и могут не соответствовать, потому что я их строю по-своему, а не про алгоритму этой теоремы.

Вот, например, прямоугольник 9х12 3-coloring уже в 4-х вариантах построила.
Неужели все варианты не соответствуют алгоритму теоремы 4.12?

Далее: я могу не видеть способ достраивания в любом из двух случаев:
а) прямоугольники соответствуют ...
б) прямоугольники не соответствуют ...

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

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

Так что же непонятного в моей логике?

Цитата:

Но зачем мне сейчас прямоугольники, если я не знаю, как его расширять до квадрата?

Вот и я не знаю, как расширять до квадрата, но ведь прямоугольники-то у меня есть
И они мне, в конце концов, могут пригодиться.

Цитата:

Программа Эда плохой помощник при стороне квадрата 361

Это понятно ёжику
Я и не пытаюсь достраивать, например, прямоугольник 81х90 9-coloring до квадрата 91х91 10-coloring в программе Эда.

Цитата:

Кто же формулы переводит? Гугл не виноват, когда он видит странные вкрапления, то перестает понимать, что от него требуют

То есть надо переводить так: формулы все выбрасывать из текста и переводить только слова, потом в полученный перевод отдельных слов вставлять формулы.
Интересный будет процесс перевода

-- Пн июн 25, 2012 19:50:07 --

Кстати, весьма любопытно, что "сказала" бы о моём прямоугольнике 81х90 9-coloring программа достраивания?
Вполне возможно, что она смогла бы его достроить до квадрата 91х91 10-coloring достаточно быстро, коль скоро здесь утверждают, что прямоугольники C^2x(C^2+C) C-coloring легко достраиваются до квадрата со стороной C^2+C+1 (С+1)-coloring.

Ведь те, кто решение C=91x91 получил, скармливают это решение программе достраивания и начинают этот квадрат "трясти" по выражению Zealint.
Так ночку потрясут и получают квадрат 92х92, ещё ночку потрясут - и готов квадрат 93х93

[Zealint]

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

По лемме есть возможность построить диагональное решение 10х10 для С=3, 18х18 для С=4, 28х28 для С=5. Есть над чем поразмыслить.

А что-то у меня diag-10x10 для C=3 не построилось : ( Вроде все варианты перебрал. А кто-нибудь построил?

-- Пн июн 25, 2012 18:58:22 --

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

Ведь те, кто решение C=91x91 получил, скармливают это решение программе достраивания и начинают этот квадрат "трясти" по выражению Zealint.
Так ночку потрясут и получают квадрат 92х92, ещё ночку потрясут - и готов квадрат 93х93

У меня в 93x93 никак не вытряхиваются ещё 2 ошибки, чтоб их... Одной ночки им мало : )

[Nataly-Mak]

Zealint

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

Пример
G(3,9) 6 > 17/3 решение может существовать
G(3,10) 6 < 19/3 решение не существует

Как я поняла, здесь утверждается, что диагональное решение C=3, N=10x10 не существует.

Хотя в более поздних исследованиях Pavlovsky оно вроде как и может существовать

[svb]

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

Не поняла! Замысловатая логика.

Это не логика, это мое мнение

Цитата:

Я не знаю, соответствуют или нет, потому что не знаю алгоритм теоремы 4.12, вот поэтому и спрашиваю.
Они вполне могут соответствовать и могут не соответствовать, потому что я их строю по-своему, а не про алгоритму этой теоремы.

Вот, например, прямоугольник 9х12 3-coloring уже в 4-х вариантах построила.
Неужели все варианты не соответствуют алгоритму теоремы 4.12?

Любая перестановка строк и столбцов приводит к прямоугольникам с теми же свойствами по окрашиванию. Сколько вариантов? Правильно - очень и очень много. И каждый из этих вариантов может быть результатом работы некоторого алгоритма. Но только один вариант является результатом работы по теореме 4.12.

Цитата:

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

Можете смело начинать

[Nataly-Mak]

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

Это не логика, это мое мнение

Вот и не вижу никакой логики в вашем мнении! Мне нужен точный ответ на мой вопрос, а не ваше мнение о самом вопросе.

Цитата:

Любая перестановка строк и столбцов приводит к прямоугольникам с теми же свойствами по окрашиванию. Сколько вариантов? Правильно - очень и очень много.

Вы открали Америку Право слово!

Цитата:

Но только один вариант является результатом работы по теореме 4.12.

Да, наверное, так. Но вот именно какой из вариантов, я и не знаю.
А все знают и молчат; даже те, кто изо всех сил пытается мне помочь (например, dimkadimon)

-- Пн июн 25, 2012 22:05:29 --

Цитата:

Можете смело начинать

Издеваетесь?
Вы же говорите, что ничего не знаете о моих прямоугольниках!

Забавно наблюдать, как джентльмены над дамой издеваются
Интересно, найдётся ли хоть один истинный джентльмен?
Была надежда на dimkadimon, но увы, и он не оправдал надежд. Тужился, тужился помочь, но так и не сдюжил

А я, вообще-то, ещё утром смело начала. И к третьему варианту прямоугольника 9х12 3-coloring добавился четвёртый. Кстати, он мне больше всех остальных вариантов нравится. И над достраиванием этого четвёртого варианта я ещё не думала. Завтра с утра на свежую голову подумаю.

-- Пн июн 25, 2012 22:27:08 --

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

А что-то у меня diag-10x10 для C=3 не построилось : ( Вроде все варианты перебрал. А кто-нибудь построил?

Да тут вроде не так много всех вариантов, даже если рассматривать характеристическую строку (по терминологии Pavlovsky) длины 2n-1, всего строка из 19 элементов получается.
Далее, если не ошибаюсь (мозги уже набекрень от прямоугольников ) число сочетаний из 19 по 3 равно 969.

svb, как я поняла, делал программу только для нормального циклического сдвига по строкам. Ну, тут строка совсем короткая - 10 элементов всего.
И решение C=3, N=9x9 он нашёл.

А, нет, кажется, ошибаюсь. Точно перегрелась с этими прямоугольниками
Тут надо не сочетания брать. А что тогда?
В характеристической строке должны находиться только числа 1,2,3, но в каких комбинациях?

[svb]

Nataly-Mak

Цитата:

Да, наверное, так. Но вот именно какой из вариантов, я и не знаю.

Я не открою Америку, если скажу, что тоже не знаю, что вы там напридумывали. Я даже перестал понимать, что вы хотите - то перевода статьи, то анализа ваших квадратов, то ...

"Тужимся", но вот ничего не выходит

Цитата:

Интересно, найдётся ли хоть один истинный джентльмен?

Это вам надо среди англичан поискать - куда уж мне серому претендовать на джентльмена

Извините Наталия, буду думать над задачей

[Nataly-Mak]

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

Я даже перестал понимать, что вы хотите - то перевода статьи, то анализа ваших квадратов, то ...

Да уж спасибо, вы мне всего надавали
И перевод статьи (было начало, целых 1,5 теоремы перевели - 4.4 и половинку 4.5 ), и перевод теоремы 4.12 (тут вы мне предложили перевод формулировки ), и анализ моего прямоугольника (по лемме 4.3)... и ещё много чего уже надавали.

Преогромное спасибо!
А я вот всё не довольна

Цитата:

"Тужимся", но вот ничего не выходит

Это значит я непроходимо тупая

Цитата:

Извините Наталия, буду думать над задачей

Если я вам мешаю думать над задачей, вы можете просто не открывать эту тему

-- Пн июн 25, 2012 22:56:22 --

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

Я не открою Америку, если скажу, что тоже не знаю, что вы там напридумывали.

Момент истины: всё, что я напридумывала "там", выложено здесь, в этой теме!
И не знать этого невозможно.
Можно просто не хотеть знать. Это мне понятно.

-- Пн июн 25, 2012 23:14:44 --

Цитата:

1 Alex Chernov 19.953100 06-24-2012 @ 09:12:15
2 Dmitry Kamenetsky 19.900100 06-22-2012 @ 07:14:03
3 Herbert Kociemba 19.886500 06-20-2012 @ 19:23:52
4 Nick Gardner 19.850900 06-21-2012 @ 07:41:06
5 Artem Karavaev 19.823400 06-24-2012 @ 06:23:02
6 Tom Sirgedas 19.777600 06-06-2012 @ 23:11:18
7 Il brigante Pennastorta 19.777600 06-08-2012 @ 08:28:33
8 Valery Pavlovsky 19.777600 06-15-2012 @ 03:02:58
9 Michael van Fondern 19.362900 06-13-2012 @ 16:27:57
10 Jim Gillogly 19.221000 06-18-2012 @ 04:45:09
11 Jarek Wroblewski 19.119200 06-04-2012 @ 00:14:00
12 Anton Voropaev 19.119200 06-04-2012 @ 07:38:59
13 Wes Sampson 18.958500 06-09-2012 @ 23:54:57
14 Sigi S 18.922900 06-21-2012 @ 13:36:50
15 Natalya Makarova 18.887100 06-23-2012 @ 04:02:34
16 Juha Saukkola 18.824800 06-24-2012 @ 18:24:30
17 Roy van Rijn 18.560600 06-24-2012 @ 05:29:15
18 Martin Richardt 18.547400 06-23-2012 @ 11:12:50
19 Aicke Hinrichs 18.410900 06-21-2012 @ 16:52:34
20 Markus Egli 18.408700 06-11-2012 @ 07:51:59

Пока в первой двадцатке пятеро россиян.

Жаль, что Ярослав Вроблевский не принимает участия в дискуссии. Я ему писала и давала ссылку на тему. Но он ничего не ответил в этот раз. Не похоже на него, всегда отвечал на письма. Попробую ещё раз ему написать, может, затерялось письмо где-то.

Алексей Чернов тоже тему игнорирует
В самом начале заглянул разок, ссылку одну привёл.

-- Пн июн 25, 2012 23:52:04 --

Эх, открою и я Америку

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

Это решение C=3, N=9x9, выложенное svb, после преобразования параллельного переноса на торе:



Думаю, что к диагональным решениям второго вида это преобразование применять нельзя.

[Nataly-Mak]

Это диагональное решение C=4, N=16x16 (из статьи), после преобразования параллельного переноса на торе:

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

[Scryer]

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

Сегодня утром встали трамваи пришлось на работу идти пешком. Во время пешей прогулки пришла такая бредовая идея.

Диагональное решение фактически выглядит так. Через квадрат проводим пучок параллельных прямых. Далее раскрашиваются эти прямые. Но ведь через квадрат не обязательно проводить прямые под углом 45 градусов(диагонали). Можно проводить пучок параллельных прямых под любым углом! Например прямые с соотношением 1:2. Что это дает непонятно.

Напоминает мне о символа Владимир Набоков в "Защита Лужина", - идя по улице, он думал, «В ход конем я могу захватить фонарный столб на углу".

[Nataly-Mak]

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

Диагональное решение фактически выглядит так. Через квадрат проводим пучок параллельных прямых. Далее раскрашиваются эти прямые. Но ведь через квадрат не обязательно проводить прямые под углом 45 градусов(диагонали). Можно проводить пучок параллельных прямых под любым углом! Например прямые с соотношением 1:2. Что это дает непонятно.

А мне это напомнило процедуру поворота параллельных прямых в позапрошлом конкурсе

[svb]

thesis.pdf - только что нашел.

-- Вт июн 26, 2012 01:20:57 --

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