Задача 17869 ФИЗТЕХ МАТ-9) На столе лежит 120 внешне...

slava191

02.10.2017

ФИЗТЕХ МАТ-9) На столе лежит 120 внешне одинаковых монет. Известно, что среди них ровно 60 фальшивых. Разрешается указать на любые две монеты и спросить, верно ли, что обе эти монеты фальшивые. За какое наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ «Верно»?

Eritrean

08.10.2017

★

В первую очередь формируем 60 пар монеток. Далее про каждую пару узнаем, верно ли что обе монетки в этой паре фальшивые. Нам может попасться один из трех видов пар:
1) н–н
2) ф–н
3) ф–ф
Если мы слышим ответ не верно, значит нам попалась либо 1–я(н–н) либо 2–я(ф–н) пара. Если при проходе k пар нам выпала хотя бы одна 1–я пара (н–н), то в оставшихся 60–k парах попадется хотя бы одна 3–я пара(ф–ф), так как кол–во фальшивых и настоящих монет одинаковое. Тогда мы получим ответ ''верно'' менее, чем за 60 вопросов.

Предположим, что на все 60 вопросов мы получили ответ неверно, тогда мы точно знаем, что все пары были вида (ф–н). Мы берем 2 любые пары и знаем, что в каждой из них по одной настоящий и по одной фальшивой монете.

Обозначим монеты: Ф1 ,Н1, Ф2, Н2.
Перебором 2 фальшивые монеты мы узнаем максимум за 4 вопроса. Пример:
1) Ф1–Н2 – неверно;
2) Ф2–Н1 – неверно;
3) Н1–Н2 – неверно;
4) Ф1–Ф2 – верно;

60+4= 64 вопроса.
Таким образом за 64 вопроса мы гарантированно получим ответ ''верно''.
Ответ: 64
Общий ответ для задачи: n/2+4, где n – кол–во монет, при условии, что ровно половина из них – фальшивые.