Московская МО-2020
Московская МО-2020
Несколько предварительных действий. Среднее по 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?
Московская МО-2020
Из условия не видно, что запрещен поворот на 0 (или 360) градусов. Тогда все 15 совпадут.
Конечно этот случай можно отсеить как слишком простой.
Конечно этот случай можно отсеить как слишком простой.
Московская МО-2020
Какое-то условие путанное - все эти "гарантировать", "не знают как повернётся". Опять же - "случайным образом". При чём тут случайность? Тогда уж нужно: "произвольным образом".
Если я правильно понял, то - человеческим языком - надо найти максимум по всем рассадкам от минимума по всем поворотам для количества совпадений.
Если я правильно понял, то - человеческим языком - надо найти максимум по всем рассадкам от минимума по всем поворотам для количества совпадений.
Московская МО-2020
zykov писал(а): надо найти максимум по всем рассадкам от минимума по всем поворотам для количества совпадений.
Да
Московская МО-2020
Вот 4 варианта дающие 7.
(Рассматривались только варианты начинающиеся с "0 0 1" для сокращения объема вычислений.)
Все 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 совпадений при любом ненулевом повороте.
Московская МО-2020
Прекрасно. Идеально бессистемно. А как школьнику в аудитории это придумать.
Например, есть 4 нуля подряд, но нет четырех единц подряд, ну это понятно, нулей больше.
Зато равносторонний треугольник с вершинами в единицах есть, а с вершинами в нулях нет
Например, есть 4 нуля подряд, но нет четырех единц подряд, ну это понятно, нулей больше.
Зато равносторонний треугольник с вершинами в единицах есть, а с вершинами в нулях нет
Московская МО-2020
Насчет системы, то можно рассмотреть 15-мерное векторное пространство над полем .
Искомый вектор содержит ровно 8 единиц.
Матрица - матрица циклического сдвига на 1.
Тогда все вектора должны содержать тоже ровно по 8 единиц для .
Можно заметить, что для чётных будет , т.к. внутренние биномиальные коэффициенты будут чётные, т.е. равны нулю в . Это верно для любой матрицы .
Для нашей матрицы ещё верно, что . Значит для нечётных будет .
Возможно могут быть какие-то другие варианты, но один очевидный вариант, если матрица применительно к данному даёт циклический сдвиг этого , т.е. для какого-то будет .
Т.е. нужно найти для которого уравнение имеет решение с ровно 8 единицами.
Сразу отпадают 0 и 1 для .
Если учесть, что где-то содержит последовательность "0 1 1", то тоже отпадают 2 и 3 для .
А вот даёт подходящее решение.
Для первой звёздочки может быть 0 или 1.
Попробуем 1.
(Хотя 0 тоже сработает, просто получится такое же сдвинутое решение.)
PS: Вобщем система такая, что по модулю 2, сам индекс складывается по модулю 15.
Искомый вектор содержит ровно 8 единиц.
Матрица - матрица циклического сдвига на 1.
Тогда все вектора должны содержать тоже ровно по 8 единиц для .
Можно заметить, что для чётных будет , т.к. внутренние биномиальные коэффициенты будут чётные, т.е. равны нулю в . Это верно для любой матрицы .
Для нашей матрицы ещё верно, что . Значит для нечётных будет .
Возможно могут быть какие-то другие варианты, но один очевидный вариант, если матрица применительно к данному даёт циклический сдвиг этого , т.е. для какого-то будет .
Т.е. нужно найти для которого уравнение имеет решение с ровно 8 единицами.
Сразу отпадают 0 и 1 для .
Если учесть, что где-то содержит последовательность "0 1 1", то тоже отпадают 2 и 3 для .
А вот даёт подходящее решение.
Код: Выбрать все
011************
011*10**1******
Для первой звёздочки может быть 0 или 1.
Попробуем 1.
(Хотя 0 тоже сработает, просто получится такое же сдвинутое решение.)
Код: Выбрать все
011110**1******
011110001001101
PS: Вобщем система такая, что по модулю 2, сам индекс складывается по модулю 15.
Московская МО-2020
Да, спасибо, в общем этот подбор можно перевести и на школьный язык
А у Вас в первых 4=х примерах было по 7 единиц. Перепутали белое и черное?
zykov писал(а):Насчет системы, то можно рассмотреть 15-мерное векторное пространство над полем .
Искомый вектор содержит ровно 8 единиц.
А у Вас в первых 4=х примерах было по 7 единиц. Перепутали белое и черное?
Московская МО-2020
Специально поменял для удобства, т.к. XOR даёт 0 при совпадении и 1 при несовпадении, т.е. будет 7 нулей и 8 единиц.
Отсюда гипотеза, что эти 8 единиц 14 раз - это циклические повороты самой рассадки с 8 единицами.
Отсюда гипотеза, что эти 8 единиц 14 раз - это циклические повороты самой рассадки с 8 единицами.
Московская МО-2020
zykov писал(а):Source of the post Вобщем система такая, что
Тут ещё такая закономерность, что идущие подряд циклически 4 значения принимают все возможные 15 ненулевых значений, т.е. они отличны друг от друга.
Само по себе - любопытная задача, найти вектор с таким свойством.
Московская МО-2020
Так что же все-таки сыграло роль, что [math], или что [math]
Общая задача. Пусть 2N+1 гномов, N+1 белых, N черных. Существует ли рассадка, гарантирующая N совпадений при каждом из 2N нетривиальных поворотов, если при тривиальном повороте совпадение полное. Если N четно то нет.
Общая задача. Пусть 2N+1 гномов, N+1 белых, N черных. Существует ли рассадка, гарантирующая N совпадений при каждом из 2N нетривиальных поворотов, если при тривиальном повороте совпадение полное. Если N четно то нет.
Московская МО-2020
Например для 11 (это если ), будет несколько вариантов дающих 5 совпадений.
Подозреваю, что случай - это наиболее тяжелый случай, когда редкие вектора дают оптимум. А именно, только вектора удовлетворяющие упомянутому свойству (что встречаются все ненулевые подпоcледовательности).
(Для 19 тоже есть несколько векторов дающих 9 совпадений.)
Подозреваю, что случай - это наиболее тяжелый случай, когда редкие вектора дают оптимум. А именно, только вектора удовлетворяющие упомянутому свойству (что встречаются все ненулевые подпоcледовательности).
(Для 19 тоже есть несколько векторов дающих 9 совпадений.)
Последний раз редактировалось zykov 29 мар 2021, 08:09, всего редактировалось 1 раз.
Московская МО-2020
:
:
:
Код: Выбрать все
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
:
Код: Выбрать все
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
:
Код: Выбрать все
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
Московская МО-2020
zykov писал(а):Source of the post Подозреваю, что случай - это наиболее тяжелый случай
Нет, видимо не так.
В этом случае есть регулярность вроде такой
zykov писал(а):Source of the post система такая, что
А в других случаях такой регулярности нет. Наверно есть какая-то другая...
Московская МО-2020
Интересно, что во всех этих случаях () есть только один подходящий вектор, с точностью до сдвигов/отражения.
Любопытно, дальше тоже так будет?
Для вектор имеет простую регулярность (для запуска итераций можно взять подряд единиц).
Интересно, как выглядит регулярность для других случаев?
Любопытно, дальше тоже так будет?
Для вектор имеет простую регулярность (для запуска итераций можно взять подряд единиц).
Интересно, как выглядит регулярность для других случаев?
Московская МО-2020
zykov писал(а):Для вектор имеет простую регулярность (для запуска итераций можно взять подряд единиц).
Мне кажется, при 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 совпадения. Может ли быть общее обоснование этому эффекту?
Московская МО-2020
zykov писал(а):Source of the post т.к. внутренние биномиальные коэффициенты будут чётные
Ха, тут вообще не верно.
Для 2 и 4 верно, а уже для 6 не верно. И дальше, иногда верно, а иногда нет.
Московская МО-2020
Ian писал(а):Source of the post так как приводим.
Там видимо должен быть многочлен .
Вот на вики есть похожее: Регистр сдвига с линейной обратной связью.
PS: Ссылка
Ian писал(а):Source of the posthttps://lh3.googleusercontent.com/proxy ... swU43Bxf2D
не работает. Выдаёт "нет доступа".
Московская МО-2020
Ian писал(а):Source of the post В общем, мой прогноз, что при (круг из элементов) решение будет, но не со свойством
Да, для это работает.
А вот для других (например ) не работает. При этом для работает.
Вобщем всё сложно там.
Работает для , может и дальше для каких.
Московская МО-2020
Один из списков неприводимых, явно не полныйzykov писал(а):Ian писал(а):Source of the posthttps://lh3.googleusercontent.com/proxy ... swU43Bxf2D
не работает. Выдаёт "нет доступа".
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей