2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Установление порядка по весу
Сообщение21.04.2015, 16:04 
Задача
Есть 10 монет разного веса и некоторые весы. При помощи одного взвешивания на весах можно узнать для выбранных двух монет, какая тяжелее. Можно ли за 20 взвешиваний узнать, в каком порядке монеты идут по весу?

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

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 16:22 
xolodec в сообщении #1006381 писал(а):
Всего монет 10, возможных вариантов их расстановок $10!$, каждое взвешивание уменьшает неопределенность в два раза, а т.к. $ \log_2 (10!)  = 21,791... $, то за 20 взвешиваний это сделать не получится.

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

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

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

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 18:59 
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$

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 19:12 
Аватара пользователя
Извините, я там ошибся, почему-то написал 9, а надо 10. Уже исправил.

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

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 20:30 
Аватара пользователя
xolodec в сообщении #1006485 писал(а):
я вот, наизусть не знаю, сколько 10!. И Могу только ориентировочно сказать, что это где то рядышком с $2^{20} = 1024 \cdot 1024$

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

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 20:59 
Аватара пользователя
Интереснее упорядочить 5 монет...

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 21:03 
grizzly в сообщении #1006534 писал(а):
Фуф... В уме это намного быстрее, чем писать. И, как видите, это совсем даже не рядышком. :-)

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

Понял, спасибо Вам огромное!
Geen в сообщении #1006541 писал(а):
Интереснее упорядочить 5 монет...

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

 
 
 
 Re: Установление порядка по весу
Сообщение21.04.2015, 23:57 
Аватара пользователя
Ну, сколько нужно взвешиваний, чтобы упорядочить 5 монет?

 
 
 
 Re: Установление порядка по весу
Сообщение22.04.2015, 17:12 
ИСН в сообщении #1006609 писал(а):
Ну, сколько нужно взвешиваний, чтобы упорядочить 5 монет?

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

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

 
 
 
 Re: Установление порядка по весу
Сообщение22.04.2015, 17:30 
Потому и интересная, что сходу не получается :-)

 
 
 
 Re: Установление порядка по весу
Сообщение22.04.2015, 18:00 
Cash в сообщении #1006829 писал(а):
Потому и интересная, что сходу не получается

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

 
 
 
 Re: Установление порядка по весу
Сообщение22.04.2015, 18:16 
Аватара пользователя
Есть, в Кнуте есть, например.

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

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group