Доска 13х13

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Доска 13х13

Сообщение Ian » 22 май 2021, 16:13

download/file.php?id=268
изображение_2021-05-22_160950.png
изображение_2021-05-22_160950.png (61.66 KiB) 10969 просмотра
Покажу, как изменить в клетках (k,m) и (k,m+9) и только в них. Два квадрата со стороной 9,сдвинутые на 1, объединение квадратов накрыть, кроме нижней строки,квадратами 2х2, пересечение тоже накрыть, кроме нижней строки, останутся 2 клетки, накрытые нечетное количество раз, (k,m)+(k,m+9)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Доска 13х13

Сообщение Ian » 22 май 2021, 16:16

Ну и конечно я предположил, что раз с первого раза так хорошо, то можно изменить и в одной отдельно взятой клетке, но ответ n=169 не прошел. Значит, клетки разобьются не на 169 классов а меньше. Может для каймы ширины 4 и центральных по-разному описываются классы.

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Доска 13х13

Сообщение peregoudov » 25 май 2021, 12:15

А можно еще считать так. Очевидно, повторная перекраска того же самого квадрата возвращает нас к исходному состоянию. Поэтому каждый квадрат можно либо перекрашивать один раз, либо не перекрашивать вовсе. Количество квадратов 9х9 в квадрате 13х13 равно 5х5=25, то есть всего $2^{25}$ вариантов закраски, а количество квадратов 2х2 в квадрате 13х13 равно 12х12=144, то есть всего $2^{144}$ вариантов закраски. И, если бы все варианты были различны, то было бы $2^{169}$ вариантов закраски. Но проблема в том, что некоторые варианты сводятся к "единичному" (без перекраски). Например, возьмем 4 квадрата 9х9 с верхними левыми углами в (1,1), (1,3), (3,1), (3,3) и четыре квадрата 2х2 с углами в (1,1), (10,1), (1,10), (10,10). Их закраска оставляет первоначальную раскраску неизменной. Наверное, таких комбинаций не так много, можно их пересчитать и внести поправку на число возможных раскрасок. Вот, например, вариантов, подобных описанному, 16 штук.

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Доска 13х13

Сообщение peregoudov » 26 май 2021, 16:26

P. S. Собственно, если судить по их ответу (153=169-16), других вариантов и нет.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Доска 13х13

Сообщение Ian » 27 май 2021, 08:37

задача еще далека от решения, это не 153=169-16, а [math]

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Доска 13х13

Сообщение peregoudov » 27 май 2021, 18:36

Вы, конечно, правы. Ну, тогда лучше считать так, как вы предлагаете. Разделим квадрат 13х13 на девять частей по 4:5:4 строки и колонки. Четверки клеток (i,j), (i+9,j), (i,j+9), (i+9,j+9) в углах 4х4 могут принимать 8 раскрасок, итого $8^{16}=2^{48}$ комбинаций. Аналогично клетки (i,j), (i+9,j) и (i,j), (i,j+9) в серединах сторон 4х5 могут принимать 2 значения, итого $2^{20}\cdot2^{20}=2^{40}$ комбинаций. Допустим, в середине 5х5 возможны все $2^{25}$ комбинаций (хотя не знаю, как их получить). Итого $2^{48+40+25}=2^{113}$ комбинаций --- маловато будет...

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Доска 13х13

Сообщение peregoudov » 11 июн 2021, 16:58

Однако не все мне понятно с подсчетом комбинаций. Рассмотрим более простой, даже примитивный пример. Пусть у нас доска из двух клеток и за один ход можно перекрасить либо одну клетку, либо обе. Итого три варианта хода и $2^3=8$ комбинаций. Но "перекрасить две клетки"="перекрасить одну первую"+"перекрасить одну вторую". По вашей, Ian, логике, это уменьшает число комбинаций на 1 (с 8 до 7), но на самом-то деле --- в два раза (с 8 до 4). Может, и в сложной задаче так: каждая "нулевая" комбинация закраски уменьшает число вариантов не на единицу, а вдвое? Ну вот глядите, допустим, есть 169 вариантов хода и последовательное применение 1, 3, 87 и 160-го вариантов дают "нулевую" закраску. Тогда закраска 1 равна просто сумме 3+87+160, и у нас не 169 независимых вариантов хода, а только 168, соответственно, и вариантов закраски вдвое меньше, а не на одну. Только вот надо сообразить, если у нас несколько "нулевых" комбинаций, будет ли каждая уменьшать число вариантов вдвое или тут возможна "интерференция"? Как-то это надо формализовать, в виде линейного пространства над полем по модулю 2, что ли...

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Доска 13х13

Сообщение peregoudov » 11 июн 2021, 18:59

Короче, вот что я в конце концов сделал. Взял следующую "нулевую" закраску из четырех квадратов 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 можно выразить через другие и число комбинаций $2^{169-15}=2^{154}$. Где-то я одну независимую "нулевую" закраску проглядел, если верить ответу жюри...

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Доска 13х13

Сообщение peregoudov » 11 июн 2021, 19:08

Все, я, кажется, понял, какое должно быть решение.

Надо выбрать другие базисные "нулевые" закраски. Четыре квадрата 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 независимых базисных раскраски, $2^{153}$ комбинаций.

Нужно только как-то доказать, что других независимых "нулевых" раскрасок нет.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Доска 13х13

Сообщение zykov » 15 июн 2021, 08:17

По СВ-500, да, там нужно найти размерность линейного подпространства в $GF2$.
Если размерность $n$, то количество элементов всего $2^n$, включая нулевой вектор.
Т.е. нужно взять матрицу $13^2=169$ (размер вектора) на $12^2+5^2=144+25=169$ (количество векторов) и найти её ранг.
Забил эту матрицу в программу (я её писал в сентябре 2019 для другой задачи тут на форуме), которая приводит её к треугольному виду и выдаёт ранг. Программа выдала 153.

Если вручную считать, то нужно из $169$ вычесть размерность пересечения линейных пространств размерностей $144$ и $25$ (очевидно, что все $144$ линейно независимы, так же как и все $25$), которая заведомо будет не более $25$.
По факту, пересечение имеет размерность $169-153=16$, что можно получить учитывая симметрии системы.

PS: На регате её можно было бы програмно решить за пару минут, если бы её открыли. Но мы там с этими графами застряли - не повезло.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 7 гостей