Сортировка по весу

Пять различных по весу предметов требуется расположить в порядке убывания их веса. Пользоваться можно только простейшими весами без гирь, которые позволяют лишь установить, какой из двух сравниваемых по весу предметов тяжелее.
Как следует действовать, чтобы решить задачу оптимальным образом, то есть так, чтобы число взвешиваний было минимальным? Сколько взвешиваний придется при этом произвести? 

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

Ваша оценка: Нет Средняя: 4.3 (13 оценки)


Комментарии

Не видно в этом решении доказательства оптимальности.