Доска 13х13
Доска 13х13
download/file.php?id=268 Покажу, как изменить в клетках (k,m) и (k,m+9) и только в них. Два квадрата со стороной 9,сдвинутые на 1, объединение квадратов накрыть, кроме нижней строки,квадратами 2х2, пересечение тоже накрыть, кроме нижней строки, останутся 2 клетки, накрытые нечетное количество раз, (k,m)+(k,m+9)
Доска 13х13
Ну и конечно я предположил, что раз с первого раза так хорошо, то можно изменить и в одной отдельно взятой клетке, но ответ n=169 не прошел. Значит, клетки разобьются не на 169 классов а меньше. Может для каймы ширины 4 и центральных по-разному описываются классы.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Доска 13х13
А можно еще считать так. Очевидно, повторная перекраска того же самого квадрата возвращает нас к исходному состоянию. Поэтому каждый квадрат можно либо перекрашивать один раз, либо не перекрашивать вовсе. Количество квадратов 9х9 в квадрате 13х13 равно 5х5=25, то есть всего вариантов закраски, а количество квадратов 2х2 в квадрате 13х13 равно 12х12=144, то есть всего вариантов закраски. И, если бы все варианты были различны, то было бы вариантов закраски. Но проблема в том, что некоторые варианты сводятся к "единичному" (без перекраски). Например, возьмем 4 квадрата 9х9 с верхними левыми углами в (1,1), (1,3), (3,1), (3,3) и четыре квадрата 2х2 с углами в (1,1), (10,1), (1,10), (10,10). Их закраска оставляет первоначальную раскраску неизменной. Наверное, таких комбинаций не так много, можно их пересчитать и внести поправку на число возможных раскрасок. Вот, например, вариантов, подобных описанному, 16 штук.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Доска 13х13
P. S. Собственно, если судить по их ответу (153=169-16), других вариантов и нет.
Доска 13х13
задача еще далека от решения, это не 153=169-16, а [math]
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Доска 13х13
Вы, конечно, правы. Ну, тогда лучше считать так, как вы предлагаете. Разделим квадрат 13х13 на девять частей по 4:5:4 строки и колонки. Четверки клеток (i,j), (i+9,j), (i,j+9), (i+9,j+9) в углах 4х4 могут принимать 8 раскрасок, итого комбинаций. Аналогично клетки (i,j), (i+9,j) и (i,j), (i,j+9) в серединах сторон 4х5 могут принимать 2 значения, итого комбинаций. Допустим, в середине 5х5 возможны все комбинаций (хотя не знаю, как их получить). Итого комбинаций --- маловато будет...
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Доска 13х13
Однако не все мне понятно с подсчетом комбинаций. Рассмотрим более простой, даже примитивный пример. Пусть у нас доска из двух клеток и за один ход можно перекрасить либо одну клетку, либо обе. Итого три варианта хода и комбинаций. Но "перекрасить две клетки"="перекрасить одну первую"+"перекрасить одну вторую". По вашей, Ian, логике, это уменьшает число комбинаций на 1 (с 8 до 7), но на самом-то деле --- в два раза (с 8 до 4). Может, и в сложной задаче так: каждая "нулевая" комбинация закраски уменьшает число вариантов не на единицу, а вдвое? Ну вот глядите, допустим, есть 169 вариантов хода и последовательное применение 1, 3, 87 и 160-го вариантов дают "нулевую" закраску. Тогда закраска 1 равна просто сумме 3+87+160, и у нас не 169 независимых вариантов хода, а только 168, соответственно, и вариантов закраски вдвое меньше, а не на одну. Только вот надо сообразить, если у нас несколько "нулевых" комбинаций, будет ли каждая уменьшать число вариантов вдвое или тут возможна "интерференция"? Как-то это надо формализовать, в виде линейного пространства над полем по модулю 2, что ли...
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Доска 13х13
Короче, вот что я в конце концов сделал. Взял следующую "нулевую" закраску из четырех квадратов 9х9 и восемнадцати квадратов 2х2 с верхними левыми углами в
9х9: (1,1) (1,2) (3,1) (3,2)
2х2: (1,1) ... (1,9) (10,1) ... (10,9)
Размножил ее сдвигами по вертикали и горизонтали и отражениями относительно диагонали, всего получилось 24 "нулевых" закраски. Каждую представил как 169-разрядное двоичное число. Ну и дальше привел составленную из этих чисел матрицу к "верхнему треугольному" виду перестановкой столбцов и сложением строк. Ранг оказался равен 15. То есть, если верить моим предыдущим рассуждениям, 15 закрасок из 169 можно выразить через другие и число комбинаций . Где-то я одну независимую "нулевую" закраску проглядел, если верить ответу жюри...
9х9: (1,1) (1,2) (3,1) (3,2)
2х2: (1,1) ... (1,9) (10,1) ... (10,9)
Размножил ее сдвигами по вертикали и горизонтали и отражениями относительно диагонали, всего получилось 24 "нулевых" закраски. Каждую представил как 169-разрядное двоичное число. Ну и дальше привел составленную из этих чисел матрицу к "верхнему треугольному" виду перестановкой столбцов и сложением строк. Ранг оказался равен 15. То есть, если верить моим предыдущим рассуждениям, 15 закрасок из 169 можно выразить через другие и число комбинаций . Где-то я одну независимую "нулевую" закраску проглядел, если верить ответу жюри...
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Доска 13х13
Все, я, кажется, понял, какое должно быть решение.
Надо выбрать другие базисные "нулевые" закраски. Четыре квадрата 9х9 и 81 квадрат 2х2:
9х9: (1,1) (1,2) (2,1) (2,2)
2х2: (1,1) ... (1,9) (2,1) ... (2,9) ... ... ... (9,1) ... (9,9)
сдвигаем по горизонтали и вертикали, всего получается 16 "нулевых" раскрасок. При этом матрица автоматически получается "верхней треугольной", то есть раскраски независимы и позволяют выразить квадраты 2х2 с левым верхним углом в квадрате 4х4 через остальные квадраты 2х2 и квадраты 9х9. Итого получается 169-16=153 независимых базисных раскраски, комбинаций.
Нужно только как-то доказать, что других независимых "нулевых" раскрасок нет.
Надо выбрать другие базисные "нулевые" закраски. Четыре квадрата 9х9 и 81 квадрат 2х2:
9х9: (1,1) (1,2) (2,1) (2,2)
2х2: (1,1) ... (1,9) (2,1) ... (2,9) ... ... ... (9,1) ... (9,9)
сдвигаем по горизонтали и вертикали, всего получается 16 "нулевых" раскрасок. При этом матрица автоматически получается "верхней треугольной", то есть раскраски независимы и позволяют выразить квадраты 2х2 с левым верхним углом в квадрате 4х4 через остальные квадраты 2х2 и квадраты 9х9. Итого получается 169-16=153 независимых базисных раскраски, комбинаций.
Нужно только как-то доказать, что других независимых "нулевых" раскрасок нет.
Доска 13х13
По СВ-500, да, там нужно найти размерность линейного подпространства в .
Если размерность , то количество элементов всего , включая нулевой вектор.
Т.е. нужно взять матрицу (размер вектора) на (количество векторов) и найти её ранг.
Забил эту матрицу в программу (я её писал в сентябре 2019 для другой задачи тут на форуме), которая приводит её к треугольному виду и выдаёт ранг. Программа выдала 153.
Если вручную считать, то нужно из вычесть размерность пересечения линейных пространств размерностей и (очевидно, что все линейно независимы, так же как и все ), которая заведомо будет не более .
По факту, пересечение имеет размерность , что можно получить учитывая симметрии системы.
PS: На регате её можно было бы програмно решить за пару минут, если бы её открыли. Но мы там с этими графами застряли - не повезло.
Если размерность , то количество элементов всего , включая нулевой вектор.
Т.е. нужно взять матрицу (размер вектора) на (количество векторов) и найти её ранг.
Забил эту матрицу в программу (я её писал в сентябре 2019 для другой задачи тут на форуме), которая приводит её к треугольному виду и выдаёт ранг. Программа выдала 153.
Если вручную считать, то нужно из вычесть размерность пересечения линейных пространств размерностей и (очевидно, что все линейно независимы, так же как и все ), которая заведомо будет не более .
По факту, пересечение имеет размерность , что можно получить учитывая симметрии системы.
PS: На регате её можно было бы програмно решить за пару минут, если бы её открыли. Но мы там с этими графами застряли - не повезло.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость