Нестандартные взвешивания

[maxal]

Задача 1. Имеется 13 одинаковых по виду и попарно различных по весу монет и прибор "Медиатор-5", умеющий из пяти монет определять среднюю по весу. Как с помощью 15-кратного применения этого прибора можно определить монету, среднюю по весу из всех монет? (задача Сергея Берлова via К. Кноп)

[TOTAL]

За 9 взвешиваний выявляем 9 претендентов, из которых за 5 взвешиваний оставляем 5 претендентов, из которых за 1 взвешивание получаем ответ.

[maxal]

Устройство "трехчашечные весы" имеет три чашки, на каждую из которых можно класть грузы (имеет форму буквы $Y$ с попарными углами $120^{\circ}$, опора в центре). Если на каждую из чашек положено по $N$ монет, то результат взвешивания позволяет понять, на какой из чашек лежит вес, равный сумме весов $N$ настоящих монет, на какой - более легкий вес (если такой есть), а на какой - более тяжелый (если есть).

Задача 2. Среди $N$ монет есть две фальшивых - одна более лёгкая и одна более тяжелая, причем в сумме они равны по весу двум настоящим. Для какого наибольшего $N=N(K)$ вы сумеете определить обе фальшивые монеты за $K$ взвешиваний на трехчашечных весах при а) $K=2$; б) $K=3$; в) $K=5$ ?

[MMyaf]

а)$N = 7$
б)$N=10$

[General]

Итак, данное взвешивание разбивает все возможные $C\limits_N^2$ вариантов расположения фальшивых монет на 13 групп, однако, распределяет неравномерно. Найдём, какое количество Х монет нужно класть на чашки весов для первого взвешивания.



В самом неблагоприятном случае, когда все 3 тарелки будут в равновесии, мы будем иметь 3x(x-1) (обе монеты на каком-либо из тарелок)+(n-3x)(n-3x-1) (обе монеты не попадали на взвешивание) вариантов. Рассмотрев это как функцию от х, найдём, что минимум будет при $x=\frac{n}{4}$. С учётом целого числа монет, можно показать, что при
n=4k и n=4k+1, x=k;
n=4k+2, x=k или x=k+1, всё равно, количество вариантов останется одинаковое;
n=4k+3, минимум будет достигаться в x=k+1.

Чтобы управиться за 2 измерения, после первого необходимо доставить не более 13 вариантов. Такое возможно при N=9, если на чаши весов положить по 2 монеты. Однако, в случае равновесия всех трёх чаш, вторым взвешиванием определить фальшивые монеты невозможно (невозможно указать, какая из них тяжёлая, а какая лёгкая, найти пару фальшивых, кстати, возможно. Уточните этот момент условия, пожалуйста - нужно ли определять, где лёгкая, а где тяжёлая фальшивая).

Пусть монет 8. Тогда кладём на чаши весов по 2 монеты.
(1,2) (3,4) (5,6)
Если будет иметь место хотя бы одно неравновесие, у нас будет 4 варианта, которые вторым взвешиванием можно разделить. Если же чаши окажутся в равновесии, то вариантов 8. Распределяем во втором взвешивании монеты так:
(1,3) (4,6) (5,7)
Тогда:
Если первая чаша тяжелее всех, то если остальные в равновесии, это пара 1+2-.
Если первая чаша тяжелее всех, а вторая – легче всех, то это пара 3+4-
Если самая тяжёлая вторая, а самая лёгкая – первая, то это 4+3-
Если самая тяжёлая вторая, а самая лёгкая – третья, то это 6+5-
Если самая тяжёлая третья, а остальные в равновесии, то это 7+8-
Если самая тяжёлая третья, а самая лёгкая – вторая, то это 5+6-
Ну и, наконец, ещё несколько правил получим, заменив везде слова «лёгкая» и «тяжелая» и «+» и «-»

Итак, N(2)=8. Буду думать над N(3)

[MMyaf]

General писал(а):

Тогда:
Если первая чаша тяжелее всех, то если остальные в равновесии, это пара 1+2-.
Если первая чаша тяжелее всех, а вторая – легче всех, то это пара 3+4-
Если самая тяжёлая вторая, а самая лёгкая – первая, то это 4+3-
Если самая тяжёлая вторая, а самая лёгкая – третья, то это 6+5-
Если самая тяжёлая третья, а остальные в равновесии, то это 7+8-
Если самая тяжёлая третья, а самая лёгкая – вторая, то это 5+6-
Ну и, наконец, ещё несколько правил получим, заменив везде слова «лёгкая» и «тяжелая» и «+» и «-»

А, если все три чаши будут показывать один вес (т.е. на одной чаше будут лежать две фальшивые или же на всех чашах будут лежать правильные монеты, а обе фальшивые в стороне)?

[General]

А во второй раз на одной чаше не могут оказаться 2 фальшивые, т.к. мы после первого взвешивания их перемешали.
Я тут смотрю, что за 3 взвешивания можно и из 16, и даже из 20, кажется, фальшивые найти, сейчас опишу алгоритм

Добавлено спустя 51 минуту 31 секунду:

Для 16 монет за 3 взвешивания:

Кладём их на чаши весов по 4. Если будет иметь место хотя бы одно неравновесие, мы сможем определить самую тяжёлую и самую лёгкую группы монет. А из 8 монет находить 2 фальшивые за 2 взвешивания мы умеем даже без дополнительной информации.

Если все чаши в равновесии, перераспределим монеты для второго взвешивания так, чтобы любые 2 монеты, бывшие в одной группе в первом взвешивании, оказались в разных группах во втором. Тогда во втором взвешивании равновесия точно не будет, и мы найдём самую тяжёлую и самую лёгкую группы. На подозрении останутся 4 пары монет, которые при первом взвешивании оказывались в одной группе, а во втором одна из них была в тяжёлой, а другая – в легкой группе. В таком случае, найдя третьим взвешиванием самую тяжёлую из подозрительных тяжёлых монет, находим искомую пару.

Попробуем провести аналогичный алгоритм для 20 монет.
Кладём на чаши весов по 5. Если будет хотя одно неравновесие, определяем самую тяжёлую и самую лёгкую группы. Пусть это будут монеты (1,2,3,4,5) + и (6,7,8,9,10) –. Тогда для второго взвешивания перераспределяем их так:

(1,6) (2,7) (3,8) (4,5,9,10)

Если одна чаша будет самой тяжёлой, а другая – самой лёгкой, то фальшивая пара определяется сразу же. Если же одна пара самая тяжёлая(лёгкая), а две другие – в равновесии, то будет 2 варианта, которые можно разделить следующим взвешиванием.

Если же чаши в равновесии, могут быть следующие варианты:
1+6-
2+7-
3+8-
4+9-
4+10-
5+9-
5+10-

Чтобы разделить их третьим взвешиванием, нужно положить монеты на весы так:
(1,8,9) (2,4,10) (5,6,7) (3)
Тогда можно составить таблицу (самая тяжёлая чаша обозначается +, самая лёгкая -, средняя по весу или находящаяся в равновесии с другой чашей - 0)

Расположение чаш: ответ
+0-: 1+6-
0+-: 2+7-
-00: 3+8-
-+0: 4+9-
000: 4+10-
-0+: 5+9-
0-+: 5+10-

Рассмотрим теперь ветку, когда после первого взвешивания все чаши оказываются в равновесии. Перераспределим монеты для второго взвешивания так:

(1,5,9,13,17) (2,6,10,14,18) (3,7,11,15,19) (4,8,12,16,20)

Если и после этого весы окажутся в равновесии, то мы будем иметь 4 подозрительных пары, в которых неизвестно, какая монета тяжелее, а какая легче. Такая же ситуация получалась при решении задачи из 8 за 2 взвешивания при первом равновесии, и показано, что эта ситуация решается одним взвешиванием.

При любом неравновесии можно найти самую тяжёлую и самую лёгкую группы, пусть, не нарушая общности, это будут первая и вторая. Тогда у нас на подозрении 6 пар:
1+2-
5+2-
9+6-
9+10-
13+14-
17+18-
Тогда распределив монеты так:
(1,2,9) (5,13,18) (6,14,17) (10)

Получим:
000: 1+2-
-+0: 5+2-
+0-: 9+6-
+00: 9+10-
0+-: 13+14-
0-+: 17+18-

Интересно, можно ли втиснуть в эту схему 21-й шар?..
Есть такое ощущение, что можно эти распределение монет по чашам увязать с системой счисления по основанию 4, надо попробовать, прежде чем браться за k=5.

[Asvald]

Здравствуйте, друзья, помогите разобраться с задачей, она очень похожа на первую задачу в теме, но немного отличается:

Цитата:

Имеется набор из 7 одинаковых по виду и попарно различных по весу монет и прибор, умеющий из 5 монет определять среднюю по весу. За какое минимальное гарантированное количество взвешиваний с помощью этого прибора можно определить среднюю монету среди всего набора? Минимальность доказывать необязательно

Я нашел вариант за 5 взвешиваний, но есть короче.

[Iam]

maxal в сообщении #124840 писал(а):

Задача 2. Среди $N$ монет есть две фальшивых - одна более лёгкая и одна более тяжелая, причем в сумме они равны по весу двум настоящим. Для какого наибольшего $N=N(K)$ вы сумеете определить обе фальшивые монеты за $K$ взвешиваний на трехчашечных весах при а) $K=2$; б) $K=3$; в) $K=5$ ?

Задачи, включающие постановки такого типа описаны в Wikipedia (раздел «Generalizations»).
Как известно, при условии количества фальшивых монет «не более t» их нахождение (т. е. идентификация ситуации с точностью «фальшивая/не фальшивая») с необходимостью приводит к идентификации их относительных весов (больше/меньше). Для случая t=2 существует совершенный алгоритм идентификации с пятью взвешиваниями.

Примечание. При этом не требуется, чтобы 2 фальшивые монеты (если они есть) имели противоположные отклонения весов.

Посмотрел боле внимательно. Задачи очень похожи, но в указанной мной ссылке задача, по-видимому, не распространяется на трехчашечные весы.