Ранжирование грузов по весу

Задача

Даны 5 грузов попарно различных масс. Требуется их проранжировать по весу, используя 7 взвешиваний на чашечных весах без гирь.

Решение

Это ещё одна из задач теории информации. Для ещё решения требуется определить, с какой неопределённостью в вариантах мы имеем дело в начале и как эту неопределённость урезать до единственного варианта после указанного количества измерений.

Сколькими способами 5 грузов могут располагаться в порядке убывания массы? Самым тяжёлым может быть один из пяти, следующим по массе – один из оставшихся четырёх, за ним – один их трёх,  и т.д. Следовательно, всего 5*4*3*2*1=120 вариантов.

Как результаты одного взвешивания может сократить количество вариантов расположения грузов? Поскольку мы можем получить только один из ответов: (>) или (<), то с каждым взвешиванием количество возможных вариантов расположения грузов сокращается не более, чем вдвое. Следовательно, пока мы не нашли противоречия в условии: т.к. 120 < 128, то из 120 вариантов можно семью последовательными делениями пополам получить 1.

Итак, начнём проводить взвешивания. Обозначим грузы буквами А, Б, В, Г, Д. Сравним (А, Б), затем (В, Г), и третьим взвешиванием сравним самые тяжёлые из грузов в каждой из пар. Пусть, не нарушая общности, А>Б, В>Г, А>В.

Каким теперь может быть расположение этих четырёх грузов по массе? Может быть всего 3 варианта:
АБВГ
АВБГ
АВГБ

Поскольку шар Д пока не связан с остальными никакими соотношениями, то он может занять любую из пяти позиций: от самого лёгкого до самого тяжёлого. Получается 15 вариантов:

АБВГД АВБГД АВГБД

АБВДГ АВБДГ АВГДБ

АБДВГ АВДБГ АВДГБ

АДБВГ АДВБГ АДВГБ

ДАБВГ ДАВБГ ДАВГБ

Теперь, глядя на эту таблицу, нужно подобрать такую пару грузов для сравнения, чтобы в зависимости от показания весов 15 возможных вариантов разбились на группы по 7 и 8. Легко видеть, что если выбрать, к примеру, сравнение, (А, Д), то показанию весов (>) удовлетворяют целых 12 вариантов, а показанию (<) - всего 3.

А вот если сравнить грузы (В,Д), то 15 вариантов разделяться именно так, как нам нужно.

В>Д	В<Д
АБВГД, АВБГД, АВГБД, АБВДГ, АВБДГ, АВГДБ, АВДБГ, АВДГБ,	АБДВГ, АДБВГ, АДВБГ, АДВГБ, ДАБВГ, ДАВБГ, ДАВГБ,

Далее снова при выборе пары для сравнения руководствуемся принципом уменьшения вдвое количества вариантов. Для левой группы таким сравнением будет (Г, Д), а для правой – (А, Д). И далее для каждой получающейся четвёрки(тройки) вариантов можно подобрать дихотомическое сравнение.

В>Д				В<Д
АБВГД, АВБГД, АВГБД, АБВДГ, АВБДГ, АВГДБ, АВДБГ, АВДГБ,				АБДВГ, АДБВГ, АДВБГ, АДВГБ, ДАБВГ, ДАВБГ, ДАВГБ,
Г>Д		Г<Д		А>Д		А<Д
АБВГД АВБГД АВГБД АВГДБ		АБВДГ АВБДГ АВДБГ АВДГБ		АБДВГ АДБВГ АДВБГ АДВГБ		ДАБВГ ДАВБГ ДАВГБ
Б>Г	Б<Г	Б>Д	Б<Д	Б>В	Б<В	Б>В	Б<В
АБВГД АВБГД	АВГБД АВГДБ	АБВДГ АВБДГ	АВДБГ АВДГБ	АБДВГ АДБВГ	АДВБГ АДВГБ	ДАБВГ	ДАВБГ ДАВГБ

Таким образом, после шести сравнений у нас по каждой ветке осталось не более двух вариантов, которые можно разделить оставшимся, седьмым взвешиванием. Задача решена.