Question

На двери сейфа расположено 15 выключателей. У каждого выключателя есть два возможных состояния - "включен" и "выключен", но по виду выключателя невозможно определить, в каком положении он находится. За один рубль разрешается переключить один выключатель. Дверь откроется, если ровно 8 выключателей окажутся в положении "включен". Как гарантировано открыть сейф, потратив не более 15 рублей?

Answer 1

Поочередно переключим все 15 выключателей по одному разу. Докажем, что в какой-то момент дверь сейфа открылась. Заметим, что после каждого действия количество выключателей в положении "включен" изменяется ровно на 1. Пусть первоначально количество выключателей в положении "включен" было  , тогда после завершения всех операций их будет 15 −  . Значит все значения от  до 15 −  "включенных" выключателей будут достигаться при переключении всех выключателей.
Осталось заметить, что одно из чисел  и 15 −  обязательно меньше 8, а другое - не меньше 8. Таким образом, настанет момент, когда будут "включены" ровно 8 выключателей