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

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

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

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

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

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

2. Пусть в условиях предыдущей задачи мы имеем (помимо данных n) еще одну контрольную (заведомо настоящую) монету. Тогда соотношение между параметрами имеет вид , причем эта оценка достигается.

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


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

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

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

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

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

А можно пример таких алгоритмов из информатики? Все, что я могу вспомнить, основано на попарном сравнение, а все подобные задачи - на групповом сравнении, или измерении. Соответсвенно и результаты - супротив .

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

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

Привет!

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

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


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


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

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

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

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

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

3. Рассмотрим вспомогательную задачу. Пусть монеты разбиты на две группы A и B: . Пусть фальшивая точно имеется, причем известно, что если она в группе A, то она легче настоящей, а если в группе B - то тяжелее. Тогда число состояний и общая теоретико-информационная оценка имеет вид .

Покажем, что эта оценка достигается. Используем индукцию по k. Основание легко проверить непосредственно. (Примечание: если , то для решения требуется одна настоящая монета. Если мы используем индукцию, то эта монета появится после первого же шага.) Далее, для произвольного k мы делим все монеты на три группы G1, G2 и G3 так, чтобы объемы , , и так чтобы в G1 и G2 было поровну монет из групп A и B. Взвешиваем G1 и G2. Если они равны, то фальшивая монета в группе G3 и по индукции мы находим ее за взвешиваний. Если G1 весит меньше G2, то берем монеты из групп и (если G1 весит больше G2, то наоборот). В новой группе ровно монет и по индукции мы находим фальшивую за взвешиваний.

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

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

Вот и все.

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

Ответ типа :

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

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

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

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