Олимпиадная задача на делимость: 31 кошелёк и поиск «облегчённого» кошелька
Задача
В ряд слева направо лежит 31 кошелёк, в каждом по 100 монет. Из одного кошелька часть монет переложили: по одной монете в каждый из кошельков справа от него. За один вопрос можно узнать суммарное число монет в любом наборе кошельков. За какое наименьшее число вопросов можно гарантированно вычислить "облегчённый" кошелёк?
Решение
Достаточно получить ответ на вопрос "сколько всего монет в кошельках с нечётными номерами?"
Действительно, если ответ на него "1600 + n" (n > 0), то монеты перекладывали из кошелька с чётным номером, справа от которого было ровно n кошельков с нечётными номерами – то есть из (2n+1)-го справа кошелька. Если же ответ на него "1600 – n" (n > 0), то монеты перекладывали из кошелька с нечётным номером, справа от которого было ровно n кошельков с чётными номерами – то есть из 2n-го справа кошелька.
Ответ
За один вопрос.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь