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