Олимпиадная задача о пяти гирях: определение порядка масс с девятью вопросами
Задача
Имеются пять внешне одинаковых гирь с попарно различными массами. Разрешается выбрать любые три из них A, B и C и спросить, верно ли, что
m(A) < m(B) < m(C) (через m(x) обозначена масса гири x). При этом даётся ответ "Да" или "Нет". Можно ли за девять вопросов гарантированно узнать, в каком порядке идут веса гирь?
Решение
Пусть у нас есть гири A, B, C, D, E. Всего имеется 5! = 120 различных способов упорядочивания весов этих гирь. А при условии m(A) < m(B) < m(C) существует 5!: 3! = 20 различных способов упорядочивания весов. Поэтому если на какой-то вопрос получен отрицательный ответ, то этот вопрос может исключить не более 20 вариантов.
Следовательно, первые пять вопросов могут (при "неудачных" ответах) исключить не более 100 вариантов. Каждый из следующих четырёх вопросов может исключить (при одном из двух возможных вариантов ответа) не более половины из оставшихся вариантов. То есть после 6-го вопроса может остаться не менее 10 вариантов, после 7-го – не менее 5, после 8-го – не менее 3, и, наконец, после 9-го вопроса может остаться по крайней мере два варианта.
Таким образом, мы показали, что при любой последовательности из девяти задаваемых вопросов найдётся последовательность ответов, которой удовлетворяют по крайней мере два варианта упорядочивания весов гирь.
Ответ
Нельзя.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь