Установление порядка по весу

[xolodec]

Задача
Есть 10 монет разного веса и некоторые весы. При помощи одного взвешивания на весах можно узнать для выбранных двух монет, какая тяжелее. Можно ли за 20 взвешиваний узнать, в каком порядке монеты идут по весу?

Если, честно, то мне кажется, что нельзя это сделать. С обоснованием сложнее.
В принципе, задача эквивалентна расстановке монет в порядке уменьшения (увеличения) их веса.
Всего монет 10, возможных вариантов их расстановок $10!$, каждое взвешивание уменьшает неопределенность в два раза, а т.к. $ \log_2 (10!) = 21,791... $, то за 20 взвешиваний это сделать не получится.
Если можно, то я бы начал действовать с взвешивания 5 неперескающихся пар, что дало бы мне 5 пар, в каждой из которых я бы знал какая из этой пары тяжелее. Как правильно и оптимальным образом двигаться дальше - пока не придумал.

[Cash]

xolodec в сообщении #1006381 писал(а):

Всего монет 10, возможных вариантов их расстановок $10!$, каждое взвешивание уменьшает неопределенность в два раза, а т.к. $ \log_2 (10!) = 21,791... $, то за 20 взвешиваний это сделать не получится.

Это нормальное рассуждение "на пальцах". Ему можно придать строгий смысл. Посмотрите, например, у Кнута. 3-й том. Под рукой нет - название раздела что-то типа сортировка с минимальным числом сравнений или оптимальная сортировка.

[svv]

Нумеруем монеты от $1$ до $10$.
По некоторому алгоритму выполняем процедуру из 20 взвешиваний.
Каждой процедуре соответствует 20-разрядное двоичное число $a$, например, $1001\;0110\;1010\;0111\;1010$, цифра в $k$-м разряде показывает результат $k$-го взвешивания.
Каждому расположению монет по весу соответствует перестановка $b$ чисел от $1$ до $10$.
Пусть $A$ — множество 20-разрядных двоичных чисел, а $B$ — множество перестановок чисел от $1$ до $10$.
Если алгоритм позволяет определить порядок, то ...

[ИСН]

Зачем так много букв. У 20 взвешиваний "без равенства", как ни крути, максимум $2^{20}$ разных результатов, сиречь вариантов упорядочения. А надо - $10!$, что больше.

[xolodec]

Cash в сообщении #1006392 писал(а):

Посмотрите, например, у Кнута. 3-й том.

Cпасибо большое! Действительно, посмотрел, у него нижняя граница количества сравнений определяется как
$ S(n) \ge \lceil \lg (n!) \rceil $ , где n - количество предметов.

svv в сообщении #1006399 писал(а):

Пусть $A$ — множество 20-разрядных двоичных чисел, а $B$ — множество перестановок чисел от $1$ до $9$.
Если алгоритм позволяет определить порядок, то ...

Если честно, svv, то не уверен, что понял Вас. Чисел в задаче 10, а не 9.

Цитата:

Если алгоритм позволяет определить порядок, то ...

честно, нет мыслей .
Кажется, что Вы имели в виду:

ИСН в сообщении #1006454 писал(а):

У 20 взвешиваний "без равенства", как ни крути, максимум $2^{20}$ разных результатов, сиречь вариантов упорядочения. А надо - $10!$, что больше.

Интересно то, что не предполагается использование никаких вычислительных средств для этой задачи. я вот, наизусть не знаю, сколько 10!. И Могу только ориентировочно сказать, что это где то рядышком с $2^{20} = 1024 \cdot 1024$

[svv]

Извините, я там ошибся, почему-то написал 9, а надо 10. Уже исправил.

Концовка: если алгоритм позволяет определить порядок, то каждому $a$ соответствует одно $b$, а каждому $b$ хотя бы одно $a$. Но $2^{20}<10!$

[grizzly]

xolodec в сообщении #1006485 писал(а):

я вот, наизусть не знаю, сколько 10!. И Могу только ориентировочно сказать, что это где то рядышком с $2^{20} = 1024 \cdot 1024$

А устному счёту в школе зачем учат?
$10! = 720 \cdot 7 \cdot 720> 700\cdot 2 \cdot2 \cdot 700 = 1400\cdot 1400 >1024\cdot 1024$
Фуф... В уме это намного быстрее, чем писать. И, как видите, это совсем даже не рядышком.

[Geen]

Интереснее упорядочить 5 монет...

[xolodec]

grizzly в сообщении #1006534 писал(а):

Фуф... В уме это намного быстрее, чем писать. И, как видите, это совсем даже не рядышком.

Согласен, признаю, был не прав.

svv в сообщении #1006491 писал(а):

Концовка: если алгоритм позволяет определить порядок, то каждому $a$ соответствует одно $b$, а каждому $b$ хотя бы одно $a$. Но $2^{20}<10!$

Понял, спасибо Вам огромное!

Geen в сообщении #1006541 писал(а):

Интереснее упорядочить 5 монет...

Немного не понял Вас, поясните, пожалуйста?

[ИСН]

Ну, сколько нужно взвешиваний, чтобы упорядочить 5 монет?

[xolodec]

ИСН в сообщении #1006609 писал(а):

Ну, сколько нужно взвешиваний, чтобы упорядочить 5 монет?

По логике оценка снизу - это 7 взвешиваний.

Для 4 монет - нижняя оценка это 5 взвешиваний: взвешиваем две пары, затем большие взвешиваем между собой, затем меньшие между собой. И еще одно, дополнительное взвешивание для однозначного определения порядка.
Для 5 монет - нижняя оценка это 7 взвешиваний, но сказать определенный алгоритм, который привел бы к этому ответу затрудняюсь, если честно. Я перебрал в голове уже много всего, но именно за 7 придумать не получается.

[Cash]

Потому и интересная, что сходу не получается

[xolodec]

Cash в сообщении #1006829 писал(а):

Потому и интересная, что сходу не получается

А точно за 7 есть алгоритм ? (глупый вопрос, понимаю, но все же)

[Xaositect]

Есть, в Кнуте есть, например.

[grizzly]

Посмотрел по алгоритму, 5 монет довольно легко отслеживается в уме. Важно только правильно (по теории) сделать первые 4 шага.
Сравниваем (1) первую со второй и (2) третью с четвёртой.
Затем (3) -- лидеров среди (1) и (2).
На шаге (4) -- проигравшую в (3) с пятой.
Теперь уже легко разглядеть, что за три сравнения всё упорядочивается.