ФИЗТЕХ МАТ-9) На столе лежит 120 внешне одинаковых монет. Известно, что среди них ровно 60 фальшивых. Разрешается указать на любые две монеты и спросить, верно ли, что обе эти монеты фальшивые. За какое наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ «Верно»?
математика 10-11 класс
8732
В первую очередь формируем 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 – кол–во монет, при условии, что ровно половина из них – фальшивые.
Вопросы к решению (2)
А если количество монет нечётное?
такого быть не может наверно условие передано неверно(((
На столе лежит $$207$$ внешне одинаковых монет. Известно, что среди них ровно $$104$$ фальшивых. Разрешается указать на любые две монеты и спросить, верно ли, что обе эти монеты фальшивые. За какое наименьшее количество вопросов можно гарантированно получить по крайней мере один ответ «Верно»?
Ошибки в решение (1)
решение не достаточно эффективное (соответственно не правильное). Во - первых, оно ни разу не доказывает, что число таких проверок минимальное, чего казалось бы достаточно, чтобы просто прикопаться к решению, но прикопаться я хочу именно к неэффективности. Поэтому, во-вторых, ответ не верный. Перебрав уже 59 пар мы гарантированно знаем всю нужную инфу о 60 парах (-1проверка). перебор из 4ех такой же = > 63 проверки