Клетчатые задачи на Курчатове
Ошибка.
Попробуйте повторить позже
Имеется таблица 
в каждой клетке которой стоит 0 или 1. Каждую минуту с ней проделывается следующая операция: для каждой
клетки считается сумма чисел в соседних с ней по сторонам клетках и одновременно в каждой клетке число заменяется на 0, если
соответствующая сумма четна, и на 1 — если нет. Докажите, что в течение 6 минут какая-нибудь расстановка повторится
дважды.
Источники:
Подсказка 1
В этой задаче важно обратить внимание на более простые случаи. Рассмотрите таблицы с одной единицей (базисные). Покажите, что их эволюция циклическая. Как симметрия сокращает перебор? Намёк: Достаточно проверить 4 варианта расположения единицы в углу 2×2 из-за симметрии)
Подсказка 2
Любая таблица — сумма базисных. Как операция преобразования действует на такие суммы? Почему это сохраняет свойство цикличности?
Подсказка 3
Для базисных таблиц 3-я и 5-я конфигурации совпадают. Как это гарантирует повторение для произвольной таблицы за ≤6 шагов? Число состояний конечно, то-есть повторение неизбежно, а циклы более простых таблиц ускоряют его.
Рассмотрим сначала таблицы, в которых стоит только одна единица (назовем эти таблицы базисными). Докажем перебором, что для таких таблиц условие задачи выполнено.
В силу симметрии конструкции перебор достаточно провести для таблиц, у которых единица стоит в верхнем левом квадрате
(даже в верхнем уголке этого квадрата, так как остальные таблицы получаются из этих подходящим отражением).
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
