Пять различных по весу предметов требуется расположить в порядке убывания их веса. Пользоваться можно только простейшими весами без гирь, которые позволяют лишь установить, какой из двух сравниваемых по весу предметов тяжелее.
Как следует действовать, чтобы решить задачу оптимальным образом, то есть так, чтобы число взвешиваний было минимальным? Сколько взвешиваний придется при этом произвести?
Ответ: Первым взвешиванием сравним любые 2 из 5 данных предметов. Пусть A - более легкий, а B - более тяжелый предмет. Тогда результат первого взвешивания запишем в виде A<B (читается: «A легче В»).
Затем сравним два других предмета и обозначим более легкий D а более тяжелый - E: D<E.
Пятый предмет обозначим C.
Третьим взвешиванием сравним предметы B и E. Обе возникающие здесь возможности приводят к аналогичным рассуждениям, поэтому мы ограничимся рассмотрением случая B<E. В итоге после трех взвешиваний мы знаем, что A<B<E и D<E.
Четвертым взвешиванием сравним пятый предмет C с предметом B. Необходимо различать два случая:
а) B<C;
б) C<B.
В первом случае (B<C)
A<B<E, D<E и B<C.
Сравним (для этого понадобится пятое взвешивание) предметы C и E. Здесь также необходимо различать два возможных случая: E<C или C<E.
Если A<B<E<C, то место предмета D, более легкого, чем E, можно определить, сравнив A с D и B с D. Таким образом, для полного упорядочения пяти предметов по весу в этом случае необходимо произвести 7 взвешиваний.
В случае A<B<C<E для определения места D также достаточно произвести два взвешивания, а именно: сначала сравнить D с B, а затем в зависимости от результата взвешивания сравнить D либо с A либо с C. В итоге мы снова производим 7 взвешиваний.
Во втором случае (C<B)
A<B<E, C<B и D<E.
Сравним предметы A и C (пятое взвешивание). В обоих возможных случаях (A<C<B или C<A<B<E) для определения места предмета D, о котором уже известно, что он легче предмета E, достаточно двух взвешиваний. Следовательно, и в случае, когда C<B, семи взвешиваний достаточно, чтобы расположить предметы в порядке возрастания их веса.
Поскольку мы исчерпали все возможные случаи, то доказательство на этом заканчивается.
Комментарии
Не видно в этом решении доказательства оптимальности.
5 разновесных предметов можно расположить 5! = 120 различными способами. Результатов взвешивания разновесных предметов 2: либо тяжелее, либо легче. Значит, потребуется не менее 7 взвешиваний. В этом случае 2^7 = 128 > 120, поэтому каждой комбинации будет соответствовать своя последовательность взвешиваний. А пример уже приведён.
Второй случай ( C < B), когда A < C < B < E и D < E расставить за 2 взвешивания D не удастся. Из того, что D < E, следует, что его нужно впихнуть в *A*C*B*, где * - свободные места. А про отношение D и A, B, C мы ничего не знаем. Получается, нужно сравнить его с каждым, а это 3 взвешивания. Итого 8. Лажа получается...
UPD: я ошибся. В той части, про которую я говорил, все верно. Извините.