задачи о взвешиваниях, и подобные им

[Brukvalub]

За два взвешивания пункт 2) сводится к 1) (либо в процессе сведения случайно находится неправильная монета). А дальше становится непонятной сама постановка задачи: требуется ли для каждого n найти точное минимальное число взвешиваний, или асимптотическую оценку?

[juna]

Brukvalub писал(а):

За два взвешивания пункт 2) сводится к 1) (либо в процессе сведения случайно находится неправильная монета). А дальше становится непонятной сама постановка задачи: требуется ли для каждого n найти точное минимальное число взвешиваний, или асимптотическую оценку?

Это точно. Рассмотрим на конкретных примерах. Пусть $n=10=2*5$.
Приведенная оценка дает: $log_2{10}=3.322$, т.е. не более четырех замеров. Далее утверждается, что есть путь короче. Один, два замера - это уж слишком, значит - три - но как? У меня для п.2 в лучшем случае четыре, а худшем шесть получается. Приведенные оценки асимптотические.

[vbn]

Артамонов Ю.Н. писал(а):

Рассмотрим на конкретных примерах. Пусть $n=10=2*5$. Приведенная оценка дает: $log_2{10}=3.322$, т.е. не более четырех замеров. Далее утверждается, что есть путь короче. Один, два замера - это уж слишком, значит - три - но как? У меня для п.2 в лучшем случае четыре, а худшем шесть получается.

И все же даже для 12-ти монет достаточно 3-х взешиваний. Вот решение.

Первое взвешивание: 1-4 vs 5-8.
Если 1-4 = 5-8, то фальшивая в 9-12. Разбиваем 9-12 на 9-10 и 11-12.
Второе взвешивание: 1-2 vs 9-10.

senormouse писал(а):

1. Если 1-2 = 9-10, то фальшивая в 11-12.
Третье взвешивание: 1 vs 11. Если 1 = 11, то фальшивая — 12, иначе фальшивая — 11.
2. Если 1-2 <> 9-10, то фальшивая среди 9-10.
Третье взвешивание: 1 vs 9. Если 1 = 9, то фальшивая — 10, иначе фальшивая — 9.

Если 1-4 <> 5-8, то фальшивая в 1-8. Для определенности, пусть 1-4>5-8.
Второе взвешивание: 1,9-12 vs 2-4,5-6.

senormouse писал(а):

1. Если 1,9-12 > 2-4,5-6, то фальшивая либо 1 (более тяжелая), либо 5-6 (более легкая).
Третье взвешивание: 5 vs 6. Если 5 = 6, то фальшивая — 1, иначе фальшивая — более легкая из 5,6.
2. Если 1,9-12 = 2-4,5-6, то фальшивая (более легкая) в 7-8.
Третье взвешивание: 7 vs 8. Если 7 < 8, то фальшивая — 7, иначе фальшивая — 8
3. Если 1,9-12 < 2-4,5-6, то фальшивая (более тяжелая) среди 2-4.
Третье взвешивание: 2 vs 3. Если 2>3, то фальшивая — 2, если 2 <3, то фальшивая — 3, иначе фальшивая — 4.

[Dims]

Сколько я ни встречаю эту задачу, каждый год находят решение всё короче и короче. Я думаю, что в конце концов окажется, что определить фальшивую монету можно и за одно взвешивание!

[maxal]

Dims писал(а):

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

Самое короткое решение приведено в FAQ конференции fido7.ru.golovolomka:

Цитата:

3.6 Взвешивание 12 монет
Q: У Вас есть 12 монет, одна из которых фальшивая и она либо легче, либо тяжелее настоящей. Как с помощью трёх взвешиваний балансировочных весах (которые показывают больше-меньше) определить фальшивую монету и то, легче она или тяжелей настоящей?
A:Решений много. Как мне кажется, приведенное здесь - одно из самых коротких. Обозначим монеты следующим образом:
FAKE MIND CLOT.
Взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку):
MA DO - LIKE, ME TO - FIND, FAKE - COIN.
Теперь совершенно просто найти фальшивую монету: к примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "A", которая легче других.

[Brukvalub]

Конечно, для отдельных количеств монет, и даже для бесконечных наборов таких количеств, имеющих специальное строение, известно немало коротких решений задачи об отыскании взвешиванием фальшивой монеты, но, как я понял из исходной постановки задачи, требуется найти нечто, относящееся ко всем возможным количествам монет, только вот что?

[Руст]

vbn писал(а):

Руст, а ответ можно, или еще не время?

Приведу пока ответ для первой задачи. Если f(n) обозначет ответ для первой задачи, то он выражается по формуле:
$f(n)=[\log _3(n-0.5)]+1.$
Получается он делением на 3. Если $n=3^k$ это легко получается f(n)=k, если $3^k<n<3^{k+1}$, то из 3m+1 или 3m+2 переходим к множеству в худшем случае c m+1 монетами и в итоге получим f(n)=k+1.
Вторая задача можеть быть разделена на 2 подзадачи, в зависимости от того, требуется допольнительно определить была ли фальшивая монета легче или тяжелее или без этого (только найти фальшивую).
В любом случае ответ не больше f(n)+2 и не меньше f(n), правда, за исключением случая n=2, когда никакое количество взвешиваний не даст ответа и n=1 взвешиваний не требуется, но определить легче или тяжелее не удастся.
Ответ зависит от строгости постановки, в чём не трудно убедится при n=4. Ответ при нестрогом условии 2=f(4) при строгом 3=f(n)+1.

[PAV]

Общее решение (с доказательством) второго пункта я приводил здесь http://dxdy.ru/viewtopic.php?p=4238#4238

[maxal]

А можно что-то подобное получить для случая, когда имеется 2 одинаковых фальшивых монеты? Или вообще, когда их $m$ штук?

[незваный гость]

Ну, есть очевидные оценки ($n$ монет, $m$ фальшивых, $k$ взвешиваний):
1) все фальшивые одинаковые, все легче: $C_n^m \le 3^k$;
2) все фальшивые одинаковые, неизвестно, легче или тяжелее: $2 C_n^m \le 3^k$;
3) каждая фальшивая может быть легче или тяжелее: $2^m C_n^m \le 3^k$.

В последних двух случаях возникает любопытный вопрос: когда это вообще можно сделать. Ответ не так-то прост, поскольку если фальшивых ровно половина, то определить фальшивые просто невозможно.

При $m=1$ 2) и 3) совпадают, но очевидная оценка не является точной.

[maxal]

Свежая статейка по теме:

An-Ping Li "A note on the counterfeit coins problem"

и последовательность A160511 (Number of weighings needed to find lighter coins among n coins).