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