Задача 115391

Темы:    [ Теория алгоритмов (прочее) ] [ Математическая логика (прочее) ] [ Четность и нечетность ]

Сложность: 4- Классы: 8,9,10,11

Условие

Автор: Шаповалов А.В.

В ряд слева направо лежит 31 кошелёк, в каждом по 100 монет. Из одного кошелька часть монет переложили: по одной монете в каждый из кошельков справа от него. За один вопрос можно узнать суммарное число монет в любом наборе кошельков. За какое наименьшее число вопросов можно гарантированно вычислить "облегчённый" кошелёк?

Решение

  Достаточно получить ответ на вопрос "сколько всего монет в кошельках с нечётными номерами?"
  Действительно, если ответ на него  "1600 + n"  (n > 0),  то монеты перекладывали из кошелька с чётным номером, справа от которого было ровно n кошельков с нечётными номерами – то есть из (2n+1)-го справа кошелька. Если же ответ на него  "1600 – n"  (n > 0),  то монеты перекладывали из кошелька с нечётным номером, справа от которого было ровно n кошельков с чётными номерами – то есть из 2n-го справа кошелька.

Ответ

За один вопрос.

Источники и прецеденты использования

олимпиада
Название	Турнир им.Ломоносова
номер/год
Год	2009
задача
Номер	7