Мигалка

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

Мигалка

Сообщение Ian » 22 окт 2021, 21:38

10.png
10.png (59.25 KiB) 4076 просмотра

Моя схема решения. Перефразируем процесс в терминах двоичной арифметики. Будем обозначать [math] утверждение, что точки i,j соединены ребром, [math] обозначает цвет, [math]-сложение по модулю 2.
[math] изменится тогда и только тогда, когда [math] - сумма(под сигмой) тут равна четности числа соседей, равных нулю
[math] изменится тогда и только тогда, когда [math] - сумма(под сигмой) тут равна четности числа соседей, равных единице. Составляем правило изменения
[math] -первая добавка равна 1 только при х=0 и условии изменения 0, вторая -только при х=1, и условии изменения 1цы.
Естественно, это можно как-то упрощать. Потом составить симметричную функцию относительно всех [math], со значениями тоже 0,1, которая при каждой одновременной замене всех будет мигалкой, то есть при всякой структуре ребер изменяться на 1. Например [math]-четность числа одноцветных ребер.
Ну вот кажется я доказал что задачка мудреная, а вы докажите что она простая)

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

Мигалка

Сообщение zykov » 23 окт 2021, 01:03

У Вас тут никак нечётность 2021 не использовалась?
Например, всего есть 2 точки и они соединены одним ребром и покрашены в один цвет.
Тогда раскраска вообще не меняется, в том числе и через нечётное количество минут.

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

Мигалка

Сообщение Ian » 23 окт 2021, 07:55

Да у меня и решения-то нет. Просто общий путь: записан закон изменения, как система разностных уравнений (возможно линейных.можно пользоваться тождеством [math] ) А найти формулу для мигалки - это найти общий интеграл (конечно нетривиально зависящий от состояния).
А если 2021 точка соединены по циклу то процесс идет интересно и непредсказуемо. И тут конечно благодаря нечетности

PS. Гипотеза: число точек, сменивших цвет за один шаг, нечетно. То есть [math] будет мигалкой. Равносильно тому, что число точек, не сменивщих цвет за один шаг -четно. А известно что сумма степеней вершин всегда четна.

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

Мигалка

Сообщение zykov » 23 окт 2021, 08:45

Далее все величины и суммирование по модулю 2.
Обозначим для ребра $(i,j)$ факт что оба конца имеют один цвет как $c_{ij}=1+x_i+x_j$ - один цвет, если равно 1, иначе 0.
Тогда новый цвет для точки - сумма по рёбрам из этой точки $y_i=x_i + 1+\sum_{j} c_{ij}$.
Обозначим чётность суммы всех точек как $S = \sum_i x_i$.

Тогда чётность нового состояния будет $S' = \sum_i y_i = \sum_i x_i + \sum_i 1 + 2\sum_{ij} c_{ij} = S + 1 + 0=S+1$, т.к. количество точек нечётно.
Т.е. $S$ будет "мигать".

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

Мигалка

Сообщение zykov » 23 окт 2021, 23:31

Можно это кстати без формул "на пальцах" показать.
Заменим процесс из задачи на эквивалентный процесс.
  1. Для каждого ребра запоминаем, одноцветно оно или нет.
  2. Для каждой точки инвертируем её цвет.
  3. Для каждой точки перебираем все её рёбра по очереди - если ребро одноцветное, то меняем цвет этой точки.

Этот процесс в свою очередь эквивалентен такому процессу.
  1. Для каждого ребра запомниаем, одноцветно оно или нет.
  2. Для каждой точки инвертируем её цвет.
  3. Перебираем все рёбра по очереди - если ребро одноцветное, то меняем цвета двух точек на концах.
Из последнего процесса очевидно, что полное количество инверсий цветов точек равно количеству точек плюс удвоенное количество одноцветных рёбер. Т.е. это полное количество инверсий цветов точек будет нечётным (т.к. количество точек нечётно).
Значит чётность количества точек покрашенных каким-то одним цветом будет "мигать".


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

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

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