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

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

Только что разбиралась Помогите найти радиоактивные мячи- всего 15, 2 плохие, 7 опыта. Могу привести еще одну классическую задачу: За три взвешивания на равноплечных весах без гирь найти одну фальшивую монету (неизвестно, она легче или тяжелее) из двенадцати. Вроде, такие задачи относятся к комбинаторике.

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

[PAV]

Мне известны следующие факты:

1. Пусть дано n монет, среди них не более одной фальшивой (может не быть ни одной), причем неизвестно - легче или тяжелее фальшивая монета, требуется разрешить ситуацию за k взвешиваний. Тогда n и k связаны следующим соотношением: $n\le\frac{3^k-3}{2}$, причем эта оценка достигается.

Этот результат описывает как раз задачу с 12 монетами и 3 взвешиваниями. Большее число монет тремя взвешиваниями обработать нельзя.

2. Пусть в условиях предыдущей задачи мы имеем (помимо данных n) еще одну контрольную (заведомо настоящую) монету. Тогда соотношение между параметрами имеет вид $n\le\frac{3^k-1}{2}$, причем эта оценка достигается.

Таким образом, если у нас есть 13 неизвестных монет плюс одна настоящая, то эту ситуацию можно также разрешить тремя взвешиваниями. Большее число монет тремя взвешиваниями разрешить нельзя.


Думаю, что есть и другие результаты подобного рода.

[Capella]

Типовых решений таких задач на самом деле очень много, просто все они находят своё примененние в информатике. Алгоритмы, которые делают поиски или сортировку по array и stack, представляют собой как раз общии решения таких вот задач на переборы... MergeSort, например, очень близок к моему решению. Формула вычисления - это примерный расход времени на перебор.

[Star]

Вообще можно 13 монет проверить за три взвешивания:)

[PAV]

Star писал(а):

Вообще можно 13 монет проверить за три взвешивания:)

Это если известно, что фальшивая среди них точно есть. И при этом мы ее находим, но не всегда можем сказать - легче она или тяжелее.

А если фальшивой монеты может не быть, тогда 13 за три попытки не разрешить.

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

ψυ& писал(а):

Типовых решений таких задач на самом деле очень много, просто все они находят своё примененние в информатике. Алгоритмы, которые делают поиски или сортировку по array и stack, представляют собой как раз общии решения таких вот задач на переборы... MergeSort, например, очень близок к моему решению. Формула вычисления - это примерный расход времени на перебор.

А можно пример таких алгоритмов из информатики? Все, что я могу вспомнить, основано на попарном сравнение, а все подобные задачи - на групповом сравнении, или измерении. Соответсвенно и результаты - $n-1$ супротив $\log_3 {(2 n + 1)}$.

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

Еще одна сходная в чем-то проблема - игра "быки и коровы" (mastermid и иже с ним). Кое-что разобрано в "Этюды для программистов" Уэзерелла. Но единственный способ, который я знаю, для построения оптимальной игровой программы требует заметной памяти и полных переборов. Не оптимально, я бы пытался решить эту задачу методами эволюционного программирования (по крайней мере, для построения автоматического партнера).

[Capella]

Привет!

Вообщем-то Вы конечно правы, но можно ведь сделать и сортировку (хотя в случае с монетами это выглядет туповато). На самом деле я сейчас так на вскидку не смогу сказать, но различные алгоритмы имеют различные complexity. К тому-же надо различать между time и place complexity.. Мой совет: прочитать книгу Вирта (по моему она есть в библиотеке), она хоть и старовата, но там более менее всё подробно описано (хотя конечно есть и более современные и хорошии)

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

ψυ& писал(а):

но можно ведь сделать и сортировку

Конечно можно, но не за четыре взвешивания. Кроме того, окончив сортировку, еще надо решить, которая из монет фальшивая - первая или последняя.

ψυ& писал(а):

... различные алгоритмы имеют различные complexity. К тому-же надо различать между time и place complexity..

Ах, как Вы правы. В данном классе задач речь идет, несомненно, о вычислительной сложности, то есть количестве необходимых операций. Похоже, ресурсы не играют.

ψυ& писал(а):

Мой совет: прочитать книгу Вирта

Непременно посмотрю. И "Алгоритмы + структуры данных = программы", и "Алгоритмы и структуры данных". Я их читал давно, забыл все. Если Вы сможете вспомнить место более точно, Вы мне очень поможете.

[billi]

PAV писал(а):

Мне известны следующие факты:

1. Пусть дано n монет, среди них не более одной фальшивой (может не быть ни одной), причем неизвестно - легче или тяжелее фальшивая монета, требуется разрешить ситуацию за k взвешиваний. Тогда n и k связаны следующим соотношением: $n\le\frac{3^k-3}{2}$, причем эта оценка достигается.

Этот результат описывает как раз задачу с 12 монетами и 3 взвешиваниями. Большее число монет тремя взвешиваниями обработать нельзя.

2. Пусть в условиях предыдущей задачи мы имеем (помимо данных n) еще одну контрольную (заведомо настоящую) монету. Тогда соотношение между параметрами имеет вид $n\le\frac{3^k-1}{2}$, причем эта оценка достигается.

Таким образом, если у нас есть 13 неизвестных монет плюс одна настоящая, то эту ситуацию можно также разрешить тремя взвешиваниями. Большее число монет тремя взвешиваниями разрешить нельзя.


Думаю, что есть и другие результаты подобного рода.

А вы не подскажите, как эти неравенства получить ?

[PAV]

Доказательство приведенных мною неравенств состоит из 5 шагов. Я узнал его от В.Лебедева на одном семинаре в Институте Проблем Передачи Информации.

1. Общая теоретико-информационная оценка. Пусть некоторая система может находиться в одном из S состояний. Требуется определить состояние системы с помощью серии проверок, каждая из которых дает один из q возможных результатов. Тогда если эта задача решается за k проверок, то должно выполняться неравенство $S\le q^k$, поскольку число всех возможных результатов проверок не может быть меньше числа состояний.

2. Рассмотрим задачу с n монетами, среди которых не более одной фальшивой, причем фальшивая может быть как легче, так и тяжелее. В этой задаче $S=2n+1$, $q=3$. Отсюда следует, что теоретико-информационная оценка имеет вид $n\le\frac{3^k-1}{2}$.

3. Рассмотрим вспомогательную задачу. Пусть монеты разбиты на две группы A и B: $n=a+b$. Пусть фальшивая точно имеется, причем известно, что если она в группе A, то она легче настоящей, а если в группе B - то тяжелее. Тогда число состояний $S=n$ и общая теоретико-информационная оценка имеет вид $n\le 3^k$.

Покажем, что эта оценка достигается. Используем индукцию по k. Основание $k=1$ легко проверить непосредственно. (Примечание: если $a=b=1$, то для решения требуется одна настоящая монета. Если мы используем индукцию, то эта монета появится после первого же шага.) Далее, для произвольного k мы делим все монеты на три группы G1, G2 и G3 так, чтобы объемы $|G_1|=|G_2|=3^{k-1}$, $|G_3|\le 3^{k-1}$, и так чтобы в G1 и G2 было поровну монет из групп A и B. Взвешиваем G1 и G2. Если они равны, то фальшивая монета в группе G3 и по индукции мы находим ее за $k-1$ взвешиваний. Если G1 весит меньше G2, то берем монеты из групп $A\cap G_1$ и $B\cap G_2$ (если G1 весит больше G2, то наоборот). В новой группе ровно $3^{k-1}$ монет и по индукции мы находим фальшивую за $k-1$ взвешиваний.

4. Покажем, что если в основной задаче (пункт 2) имеется еще одна настоящая монета, то приведенная там оценка достигается. Также используем индукцию по k. Основание k=1 тривиально. Шаг индукции. Отбираем $m=\frac{3^{k-1}-1}{2}$ монет. Остается $n-m\le 3^{k-1}$ монет. Если это число нечетное, то добавляем имеющуюся в наличии настоящую монету, затем делим пополам и взвешиваем. Если получилось равенство - то фальшивая находится среди отобранных m, и мы по индукции находим ее за k-1 проверок. Если же не равны, то подозрительные $\le 3^{k-1}$ монет оказываются разделенными на две группы и согласно результату вспомогательной задачи мы также найдем фальшивую за k-1 взвешиваний.

5. Покажем, что если в основной задаче нет дополнительной правильной монеты, то оценку можно улучшить: $n\le\frac{3^k-3}{2}$. Допустим, что k проверок достаточно. Первая проверка всегда заключается в том, что сравниваются между собой две группы по x монет. Если в результате получилось равенство, то за оставшиеся k-1 проверок должны решить исходную задачу с n-2x монетами. Согласно общей оценке тогда должно выполняться неравенство $n-2x\le\frac{3^{k-1}-1}{2}$. Заметим, что это условие не только необходимое, но и достаточное (согласно пункту 4), так как дополнительные настоящие монеты уже имеются. Если же в результате первого взвешивания получили неравенство, то находимся в условиях пункта 3. Необходимым и достаточным условием для этого является неравенство $2x\le 3^{k-1}$. Заметим, что левая часть четная, а правая начетная, поэтому можно усилить неравенство следующим образом: $2x+1\le 3^{k-1}$. Складывая оба полученных неравенства получаем ровно то, что требовалось. Чтобы показать, что это неравенство достаточно, осталось показать, что всегда можно подобрать x так, чтобы оба приведенных неравенства выполнялись, а они были достаточные.

Вот и все.

[Руст]

Среди n монет одна фальшивая (различается по весу). Найти минимальное количество взвешиваний, гарантирующих нахождение фальшивой монеты при условии:
1) Фальшивая монета легче настоящей.
2) Заранее неизвестно легче или тяжелее фальшивая монета.

[C0rWin]

Ответ типа :

\[ \log _2 n ? \]

Или существуют более короткие способы?
Это правда когда мне совсем все равно какого она веса.

[Руст]

Существует метод определения покороче.

[photon]

C0rWin писал(а):

Ответ типа :

\[\log _2 n ?\]

Или существуют более короткие способы?

Делить надо на три, а не на две части - если две равны, то фальшивая в третьей

[vbn]

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