Мигалка
Мигалка
Моя схема решения. Перефразируем процесс в терминах двоичной арифметики. Будем обозначать [math] утверждение, что точки i,j соединены ребром, [math] обозначает цвет, [math]-сложение по модулю 2.
[math] изменится тогда и только тогда, когда [math] - сумма(под сигмой) тут равна четности числа соседей, равных нулю
[math] изменится тогда и только тогда, когда [math] - сумма(под сигмой) тут равна четности числа соседей, равных единице. Составляем правило изменения
[math] -первая добавка равна 1 только при х=0 и условии изменения 0, вторая -только при х=1, и условии изменения 1цы.
Естественно, это можно как-то упрощать. Потом составить симметричную функцию относительно всех [math], со значениями тоже 0,1, которая при каждой одновременной замене всех будет мигалкой, то есть при всякой структуре ребер изменяться на 1. Например [math]-четность числа одноцветных ребер.
Ну вот кажется я доказал что задачка мудреная, а вы докажите что она простая)
Мигалка
У Вас тут никак нечётность 2021 не использовалась?
Например, всего есть 2 точки и они соединены одним ребром и покрашены в один цвет.
Тогда раскраска вообще не меняется, в том числе и через нечётное количество минут.
Например, всего есть 2 точки и они соединены одним ребром и покрашены в один цвет.
Тогда раскраска вообще не меняется, в том числе и через нечётное количество минут.
Мигалка
Да у меня и решения-то нет. Просто общий путь: записан закон изменения, как система разностных уравнений (возможно линейных.можно пользоваться тождеством [math] ) А найти формулу для мигалки - это найти общий интеграл (конечно нетривиально зависящий от состояния).
А если 2021 точка соединены по циклу то процесс идет интересно и непредсказуемо. И тут конечно благодаря нечетности
PS. Гипотеза: число точек, сменивших цвет за один шаг, нечетно. То есть [math] будет мигалкой. Равносильно тому, что число точек, не сменивщих цвет за один шаг -четно. А известно что сумма степеней вершин всегда четна.
А если 2021 точка соединены по циклу то процесс идет интересно и непредсказуемо. И тут конечно благодаря нечетности
PS. Гипотеза: число точек, сменивших цвет за один шаг, нечетно. То есть [math] будет мигалкой. Равносильно тому, что число точек, не сменивщих цвет за один шаг -четно. А известно что сумма степеней вершин всегда четна.
Мигалка
Далее все величины и суммирование по модулю 2.
Обозначим для ребра факт что оба конца имеют один цвет как - один цвет, если равно 1, иначе 0.
Тогда новый цвет для точки - сумма по рёбрам из этой точки .
Обозначим чётность суммы всех точек как .
Тогда чётность нового состояния будет , т.к. количество точек нечётно.
Т.е. будет "мигать".
Обозначим для ребра факт что оба конца имеют один цвет как - один цвет, если равно 1, иначе 0.
Тогда новый цвет для точки - сумма по рёбрам из этой точки .
Обозначим чётность суммы всех точек как .
Тогда чётность нового состояния будет , т.к. количество точек нечётно.
Т.е. будет "мигать".
Мигалка
Можно это кстати без формул "на пальцах" показать.
Заменим процесс из задачи на эквивалентный процесс.
Этот процесс в свою очередь эквивалентен такому процессу.
Значит чётность количества точек покрашенных каким-то одним цветом будет "мигать".
Заменим процесс из задачи на эквивалентный процесс.
- Для каждого ребра запоминаем, одноцветно оно или нет.
- Для каждой точки инвертируем её цвет.
- Для каждой точки перебираем все её рёбра по очереди - если ребро одноцветное, то меняем цвет этой точки.
Этот процесс в свою очередь эквивалентен такому процессу.
- Для каждого ребра запомниаем, одноцветно оно или нет.
- Для каждой точки инвертируем её цвет.
- Перебираем все рёбра по очереди - если ребро одноцветное, то меняем цвета двух точек на концах.
Значит чётность количества точек покрашенных каким-то одним цветом будет "мигать".
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 11 гостей