2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Нестандартные взвешивания
Сообщение06.06.2008, 08:19 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение06.06.2008, 09:32 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Трехчашечные весы
Сообщение06.06.2008, 10:38 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение06.06.2008, 19:45 


24/05/06
72
а)$N = 7$
б)$N=10$

 Профиль  
                  
 
 
Сообщение06.06.2008, 21:45 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Итак, данное взвешивание разбивает все возможные $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)

 Профиль  
                  
 
 
Сообщение07.06.2008, 10:57 


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


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

 Профиль  
                  
 
 
Сообщение07.06.2008, 11:49 
Аватара пользователя


17/05/08
358
Анк-Морпорк
А во второй раз на одной чаше не могут оказаться 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.

 Профиль  
                  
 
 Re: Нестандартные взвешивания
Сообщение05.11.2015, 17:29 


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

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

 Профиль  
                  
 
 Re: Нестандартные взвешивания
Сообщение08.11.2015, 20:38 


01/11/14
195
maxal в сообщении #124840 писал(а):

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gevin Magnus


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group