Высшая проба 2025, 8 класс, задача 4
( баллов) В лаборатории лампочек, к каждой из лампочек подключено по кнопке. Нажатие кнопки включает лампочку, с которой она соединена, если эта лампочка выключена, и выключает, если включена. За одну операцию можно нажать на две соседние кнопки. Изначально включено чётное число лампочек. Какое минимальное число операций потребуется, чтобы гарантированно выключить все лампочки, если кнопки расположены
а) ( баллов) в ряд?
Ответ. а) .
Решение. Заметим, что порядок нажатий не имеет значения, а также что дважды переключая одну и ту же пару лампочек, мы ничего не меняем. Значит, для каждой пары лампочек нам нужно решить, хотим ли мы её переключить, или нет.
Назовём блоком подряд идущих лампочек, среди которых горят только первая и последняя.
Пример: Пусть первая и последняя лампочки горят, а остальные — нет. Заметим, что чтобы погасить первую лампочку, нам нужно переключить первую лампочку и вторую. Тогда загорится вторая лампочка, и чтобы погасить её, нам понадобится переключить вторую и третью (так как первую пару мы уже переключили). Таким образом нам придётся переключить все пары лампочек, то есть совершить действий.
Оценка: разобьём все лампочки на блоки (так как их чётное число, нам удастся это сделать). Каждый блок можно погасить, переключив все пары в нём. Заметим, что пар в ряду всего , а значит, действий точно хватит. Ряд однозначно разбивается на блоки. Сумма длин блоков не превосходит , поэтому суммарная сложность не превосходит . Если весь ряд представляет из себя один блок, то операций необходимо.
Верное решение.
Доказана достаточность 99 действий.
Приведен пример, показывающий необходимость 99 действий.
Решение не соответствует ни одному из критериев выше.
б) ( баллов) по кругу?
Ответ. б) .
Решение. Пример: если горят все лампочки, то меньше действий сделать не получится, так как за одно действие мы можем погасить не более двух лампочек.
Оценка: Из пункта а) мы знаем, что все лампочки точно можно погасить. Заметим, что если переключить все пар лампочек, ничего не изменится. Значит, если мы можем погасить все лампочки за действий, мы также можем сделать это и за действий, просто переключив все оставшиеся пары.
Верное решение.
Доказана достаточность 50 действий.
Приведён пример, показывающий необходимость 50 действий.