На одном из математических турниров предлагалась следующая задача, причём была она в варианте для 6 класса:
По кругу стоит n > 2 лампочек. У каждой лампочки есть выключатель, который при нажатии изменяет состояние лампочки. Изначально все лампочки выключены. Петя может одновременно нажимать на два выключателя соседних лампочек. При каких n он может такими переключениями добиться того, что среди любых трёх идущих подряд лампочек ровно одна будет включена?
Попробуйте решить её самостоятельно, прежде чем читать решение. Но учтите, задача не простая!
Ответ в этой задаче следующий: при всех n, кратных 6.
Решение: Докажем следующий факт: в любой момент времени включено чётное число лампочек. Изначально включено 0, т.е. чётное число лампочек. Нам достаточно доказать, что после каждого переключения двух соседних лампочек число включенных лампочек изменяется либо на 0, либо на 2. Итак, если мы затрагиваем две выключенных (или включенных лампочки), число включенных увеличивается (или уменьшается) на 2, а если мы затрагиваем одну включенную и одну выключенную лампочку, то количество включенных лампочек не меняется. Итак, в любой момент времени у нас имеется чётное число лампочек. Как же они должны располагаться, чтобы условие выполнялось? Давайте рассуждать. Если рядом есть 2 соседние лампочки, то условие задачи не выполнено: мы можем выбрать такую тройку подряд идущих лампочек, что обе эти соседние лампочки попадут в эту тройку. Если 2 включенные лампочки стоят через одну, то мы, опять же, можем выбрать тройку подряд идущих лампочек, где обе эти лампочки присутствуют. Если между двумя соседними включенными лампочками хотя бы 3 выключенных, мы можем выбрать тройку, где нет включенных лампочек, что опять же противоречит условию. Итак, между любыми двумя соседними включенными лампочками не 0, не 1, и не более 2 выключенных лампочек. А значит, между любыми двумя включенными лампочками ровно две выключенных! Итак, если немного напрячь воображение, мы поймём, что лампочки располагаются так:
где 0 – выключенная лампочка, 1 – включенная. Но тогда лампочки можно разбить на тройки «100». А значит, количество лампочек делится на 3! Самое время вспомнить, что единиц – включенных лампочек чётное количество. В каждой тройке одна включенная лампочка, т.е. троек чётное количество. А значит, n делится на 2 и на 3, т.е. делится на 6. Итак, мы получили, что n кратно 6. Стало быть, задача решена! Подождите! Нужно привести пример действий Пети, подтверждающий, что если n делится на 6, то Петя сможет выполнить требуемое условие. Как же действовать Пете? Ведь число n может быть невероятно большим! На самом деле все просто. Достаточно работать не со всем лампочками, а с шестёрками подряд стоящих лампочек. Итак, разобьём n лампочек на шестёрки подряд стоящих, и в каждой шестёрке проделаем следующую операцию: 000000 => 110000 => 101000 => 100100. И так с каждой шестёркой. Сопоставим все наши шестёрки и поймём, что условие задачи выполнено. Ура! Победа!!
Делитесь впечатлениями о задаче в комментариях, ставьте лайк и подписывайтесь на канал!