Из набора гирь весом 1, 2, ..., 26 выделить шесть гирь так, чтобы среди них не было выбрать двух кучек равного веса.
Доказать, что нельзя выбрать семь гирь, обладающих тем же свойством.

   Решение

Темы:    [ Взвешивания ] [ Сочетания и размещения ] [ Перестановки и подстановки (прочее) ] [ Математическая логика (прочее) ]

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

Прислать комментарий

Условие

Имеются пять внешне одинаковых гирь с попарно различными массами. Разрешается выбрать любые три из них 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-го вопроса может остаться по крайней мере два варианта.
  Таким образом, мы показали, что при любой последовательности из девяти задаваемых вопросов найдётся последовательность ответов, которой удовлетворяют по крайней мере два варианта упорядочивания весов гирь.

Ответ

Нельзя.

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