Московская МО-2020

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

Московская МО-2020

Сообщение Ian » 26 мар 2021, 09:02

mmo3.png
mmo3.png (34.78 KiB) 17284 просмотра

Несколько предварительных действий. Среднее по 14 поворотам число совпадений 8*7 (белого с белым)+7*6(черного с черным) /14=7. Значит, минимума больше 7 добиться нельзя.
Число совпадений при любом повороте нечетно, так как число несовпадений (белое на черное)+(черное на белое) это сумма двух одинаковых количеств, четно
Число совпадений для симметричных поворотов одинаково (если при одном i попало на j, то при другом j попадет на i )
Значит правильный ответ 7 либо 5. Примеров расстановки с 5 полно. А вот на 7 не имею. И может быть, такие экстремальные расстановки имеют общую закономерность.
Но при n=5 вместо 15 , 3 белых и 2 черных, добиться гарантии 2х совпадений невозможно, там всего 2 принципиально различных расстановки.Ну а также потому, что число совпадений должно быть нечетно Может, играет роль, что 15 делится на 5?

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

Московская МО-2020

Сообщение zykov » 26 мар 2021, 09:11

Из условия не видно, что запрещен поворот на 0 (или 360) градусов. Тогда все 15 совпадут.
Конечно этот случай можно отсеить как слишком простой.

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

Московская МО-2020

Сообщение zykov » 26 мар 2021, 10:54

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

Если я правильно понял, то - человеческим языком - надо найти максимум по всем рассадкам от минимума по всем поворотам для количества совпадений.

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

Московская МО-2020

Сообщение Ian » 26 мар 2021, 12:54

zykov писал(а): надо найти максимум по всем рассадкам от минимума по всем поворотам для количества совпадений.

Да

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

Московская МО-2020

Сообщение zykov » 26 мар 2021, 14:03

Вот 4 варианта дающие 7.
(Рассматривались только варианты начинающиеся с "0 0 1" для сокращения объема вычислений.)

Код: Выбрать все

   0   0   1   1   1   0   1   1   0   0   1   0   1   0   0
   0   0   1   1   0   1   1   1   0   0   0   0   1   0   1
   0   0   1   0   1   0   0   1   1   0   1   1   1   0   0
   0   0   1   0   1   0   0   0   0   1   1   1   0   1   1

Все 4 - это один варинат с точностью до сдвига и отражения.
Ровно 7 совпадений при любом ненулевом повороте.

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

Московская МО-2020

Сообщение Ian » 26 мар 2021, 15:59

Прекрасно. Идеально бессистемно. А как школьнику в аудитории это придумать.
Например, есть 4 нуля подряд, но нет четырех единц подряд, ну это понятно, нулей больше.
Зато равносторонний треугольник с вершинами в единицах есть, а с вершинами в нулях нет

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

Московская МО-2020

Сообщение zykov » 26 мар 2021, 23:20

Насчет системы, то можно рассмотреть 15-мерное векторное пространство над полем $GF(2)$.
Искомый вектор $a$ содержит ровно 8 единиц.
Матрица $M$ - матрица циклического сдвига на 1.
Тогда все вектора $x_n = (E+M^n)a$ должны содержать тоже ровно по 8 единиц для $n=1..14$.

Можно заметить, что для чётных $n>0$ будет $E+M^n = (E+M)^n$, т.к. внутренние биномиальные коэффициенты будут чётные, т.е. равны нулю в $GF(2)$. Это верно для любой матрицы $M$.
Для нашей матрицы ещё верно, что $M^{15} = E$. Значит для нечётных $n$ будет $E+M^n = (E+M)^{15+n}$.
Возможно могут быть какие-то другие варианты, но один очевидный вариант, если матрица $E+M$ применительно к данному $a$ даёт циклический сдвиг этого $a$, т.е. для какого-то $k$ будет $(E+M)a = M^k a$.
Т.е. нужно найти $k$ для которого уравнение $(E+M+M^k)a=0$ имеет решение с ровно 8 единицами.

Сразу отпадают 0 и 1 для $k$.
Если учесть, что $a$ где-то содержит последовательность "0 1 1", то тоже отпадают 2 и 3 для $k$.
А вот $k=4$ даёт подходящее решение.

Код: Выбрать все

011************
011*10**1******

Для первой звёздочки может быть 0 или 1.
Попробуем 1.
(Хотя 0 тоже сработает, просто получится такое же сдвинутое решение.)

Код: Выбрать все

011110**1******
011110001001101

PS: Вобщем система такая, что $a_{i+4}=a_i+a_{i+1}$ по модулю 2, сам индекс складывается по модулю 15.

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

Московская МО-2020

Сообщение Ian » 27 мар 2021, 05:41

Да, спасибо, в общем этот подбор можно перевести и на школьный язык
zykov писал(а):Насчет системы, то можно рассмотреть 15-мерное векторное пространство над полем $GF(2)$.
Искомый вектор $a$ содержит ровно 8 единиц.

А у Вас в первых 4=х примерах было по 7 единиц. Перепутали белое и черное?

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

Московская МО-2020

Сообщение zykov » 27 мар 2021, 05:50

Специально поменял для удобства, т.к. XOR даёт 0 при совпадении и 1 при несовпадении, т.е. будет 7 нулей и 8 единиц.
Отсюда гипотеза, что эти 8 единиц 14 раз - это циклические повороты самой рассадки с 8 единицами.

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

Московская МО-2020

Сообщение zykov » 28 мар 2021, 05:52

zykov писал(а):Source of the post Вобщем система такая, что $a_{i+4}=a_i+a_{i+1}$

Тут ещё такая закономерность, что идущие подряд циклически 4 значения принимают все возможные 15 ненулевых значений, т.е. они отличны друг от друга.
Само по себе - любопытная задача, найти вектор с таким свойством.

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

Московская МО-2020

Сообщение Ian » 28 мар 2021, 16:35

Так что же все-таки сыграло роль, что [math], или что [math]
Общая задача. Пусть 2N+1 гномов, N+1 белых, N черных. Существует ли рассадка, гарантирующая N совпадений при каждом из 2N нетривиальных поворотов, если при тривиальном повороте совпадение полное. Если N четно то нет.

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

Московская МО-2020

Сообщение zykov » 28 мар 2021, 19:01

Например для 11 (это если $N=5$), будет несколько вариантов дающих 5 совпадений.
Подозреваю, что случай $2^k-1$ - это наиболее тяжелый случай, когда редкие вектора дают оптимум. А именно, только вектора удовлетворяющие упомянутому свойству (что встречаются все ненулевые подпоcледовательности).

(Для 19 тоже есть несколько векторов дающих 9 совпадений.)
Последний раз редактировалось zykov 29 мар 2021, 08:09, всего редактировалось 1 раз.

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

Московская МО-2020

Сообщение zykov » 29 мар 2021, 07:20

$N=5$:

Код: Выбрать все

   1   1   0   0   0   1   0   1   1   0   1
   1   1   0   1   0   0   0   1   1   1   0
   1   1   0   1   1   0   1   0   0   0   1
   1   1   0   1   1   1   0   0   0   1   0


$N=9$:

Код: Выбрать все

   1   1   0   0   0   0   1   0   1   0   1   1   1   1   0   0   1   1   0
   1   1   0   0   1   1   0   1   1   0   0   0   0   1   0   1   0   1   1
   1   1   0   0   1   1   1   1   0   1   0   1   0   0   0   0   1   1   0
   1   1   0   1   0   1   0   0   0   0   1   1   0   1   1   0   0   1   1
   1   1   0   1   1   0   0   0   0   1   0   1   0   1   1   1   1   0   0
   1   1   0   1   1   0   0   1   1   1   1   0   1   0   1   0   0   0   0


$N=11$:

Код: Выбрать все

   1   1   0   0   0   0   1   0   1   0   0   1   1   0   0   1   1   0   1   0   1   1   1
   1   1   0   0   1   0   1   0   0   0   0   1   1   1   1   1   0   1   0   1   1   0   0
   1   1   0   0   1   1   0   0   1   0   1   0   0   0   0   1   1   1   1   1   0   1   0
   1   1   0   0   1   1   0   1   0   1   1   1   1   1   0   0   0   0   1   0   1   0   0
   1   1   0   1   0   1   1   0   0   1   1   0   0   1   0   1   0   0   0   0   1   1   1
   1   1   0   1   0   1   1   1   1   1   0   0   0   0   1   0   1   0   0   1   1   0   0

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

Московская МО-2020

Сообщение zykov » 29 мар 2021, 07:40

zykov писал(а):Source of the post Подозреваю, что случай $2^k-1$ - это наиболее тяжелый случай

Нет, видимо не так.
В этом случае есть регулярность вроде такой
zykov писал(а):Source of the post система такая, что $a_{i+4}=a_i+a_{i+1}$

А в других случаях такой регулярности нет. Наверно есть какая-то другая...

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

Московская МО-2020

Сообщение zykov » 30 мар 2021, 18:38

Интересно, что во всех этих случаях ($N=1,3,5,7,9,11$) есть только один подходящий вектор, с точностью до сдвигов/отражения.
Любопытно, дальше тоже так будет?

Для $2N+1=2^k-1$ вектор имеет простую регулярность $a_{i+k}=a_i+a_{i+1}$ (для запуска итераций можно взять $k$ подряд единиц).
Интересно, как выглядит регулярность для других случаев?

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

Московская МО-2020

Сообщение Ian » 02 апр 2021, 05:50

zykov писал(а):Для $2N+1=2^k-1$ вектор имеет простую регулярность $a_{i+k}=a_i+a_{i+1}$ (для запуска итераций можно взять $k$ подряд единиц).

Мне кажется, при k=4 это получилось потому, что многочлен [math] неприводим.Если бы у Вас уравнение [math]разложилось бы на множители, то ничего бы не вышло. Но ведь не при всех больших k многочлен [math]неприводим.(Рассматриваются коэффициенты из [math])
Свойство:Последовательность [math] перечисляет все 15 возможных ненулевых многочленов степени не выше 3, выполняется благодаря тому, что [math] неприводим. Правда, эта последовательность получается не циклическим сдвигом коэффициентов [math]
https://lh3.googleusercontent.com/proxy ... swU43Bxf2D
В общем, мой прогноз, что при k=7 (круг из N=127 элементов) решение будет, но не со свойством [math] а с другим,так как [math] приводим. Сейчас кстати проверю, это недолго
PS. Нет, как ни странно годится [math], при всех циклических сдвигах по 64 совпадения. Может ли быть общее обоснование этому эффекту?

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

Московская МО-2020

Сообщение zykov » 02 апр 2021, 10:13

zykov писал(а):Source of the post т.к. внутренние биномиальные коэффициенты будут чётные

Ха, тут вообще не верно.
Для 2 и 4 верно, а уже для 6 не верно. И дальше, иногда верно, а иногда нет.

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

Московская МО-2020

Сообщение zykov » 02 апр 2021, 10:46

Ian писал(а):Source of the post так как $x^7+x+1$ приводим.

Там видимо должен быть многочлен $x^7+x^6+1$.
Вот на вики есть похожее: Регистр сдвига с линейной обратной связью.

PS: Ссылка
Ian писал(а):Source of the posthttps://lh3.googleusercontent.com/proxy ... swU43Bxf2D

не работает. Выдаёт "нет доступа".

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

Московская МО-2020

Сообщение zykov » 02 апр 2021, 11:23

Ian писал(а):Source of the post В общем, мой прогноз, что при $k=7$ (круг из $N=127$ элементов) решение будет, но не со свойством

Да, для $k=7$ это работает.
А вот для других (например $k=5,8,9,10,11,12,13,14,16,17$) не работает. При этом для $k=15$ работает.
Вобщем всё сложно там.
Работает для $k=1,2,3,4,6,7,15$, может и дальше для каких.

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

Московская МО-2020

Сообщение Ian » 02 апр 2021, 20:15

zykov писал(а):
Ian писал(а):Source of the posthttps://lh3.googleusercontent.com/proxy ... swU43Bxf2D

не работает. Выдаёт "нет доступа".
Один из списков неприводимых, явно не полный
x7.png
x7.png (51.99 KiB) 16955 просмотра


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

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

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