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