2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему
 
 Задача об 11 мешках с монетами, найти фальшивые за 2 взвешив
Сообщение16.06.2011, 14:55 


01/10/10

2116
Израиль (племянница БизиБивера)
Имеется 11 мешков монет. В 10 из них монеты настоящие, а в одном — все монеты фальшивые. Все настоящие монеты одного веса, все фальшивые монеты — также одного, но другого веса. Имеются весы, с помощью которых можно определить, какой из двух грузов тяжелее и на сколько. Двумя взвешиваниями определить, в каком мешке фальшивые монеты.

Моё решение:

(Оффтоп)

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

Второе взвешивание:
Кладём 55 монет из 11-го мешка (уже известно, что они - настоящие) на левую, а на правую одну из первого, две из второго, три из третьего, ... , десять из десятого.
Стрелка покажет вес, больший модуля разности между настоящей и фальшивой монетами ровно в число раз, равное номеру "фальшивого" мешка.

Решение "из книжки":
http://problems.ru/view_problem_details ... p?id=78572

1. Не ошибочно ли моё решение?
2. А что если в каждом мешке не более 54 монет?

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 15:06 


26/12/08
1813
Лейден
1. Ваше решение правильно
2. Вообще они затем и мешки, чтобы в них было "столько монет, сколько понадобится" и не факт, что при другой трактовке решение существует.

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 15:14 


01/10/10

2116
Израиль (племянница БизиБивера)
Gortaur в сообщении #458681 писал(а):
1. Ваше решение правильно
2. Вообще они затем и мешки, чтобы в них было "столько монет, сколько понадобится" и не факт, что при другой трактовке решение существует.

Уже нашла, как обойтись 45-ю монетами.
Во втором взвешивании кладём 45 из 11-го и с 1 по 9 из мешков с первого по девятый. Если равноденствие, то фальшивый мешок - десятый.

А моё решение точно правильное?

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 15:20 


26/12/08
1813
Лейден
При первом взвешивании определяете паршивый ли мешок номер 11 - а если нет, то узнаете разницу в весах между монетами. При повторном взвешивании Вы эту разницу используете, чтобы определить паршивый мешок. В чем ошибку подозреваете-то?

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 15:27 


01/10/10

2116
Израиль (племянница БизиБивера)
Gortaur в сообщении #458690 писал(а):
При первом взвешивании определяете паршивый ли мешок номер 11 - а если нет, то узнаете разницу в весах между монетами. При повторном взвешивании Вы эту разницу используете, чтобы определить паршивый мешок. В чем ошибку подозреваете-то?

В том, что моё решение разнится с "книжным".

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 15:44 


26/12/08
1813
Лейден
Xenia1996
Ваше решение через 45 монет тоже разнится с Вашим через 55.

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 15:44 


01/10/10

2116
Израиль (племянница БизиБивера)
Хотелось бы ещё и доказать, что одним взвешиванием обойтись нельзя...

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение16.06.2011, 16:10 


26/12/08
1813
Лейден
Попробую... пусть $k_i$ где $i = 1,2,...,11$ - сколько монет мы положили на весы из $i$-го мешка. $k_i>0$ значит что мы положили на правую чашу, $k_i<0$ - значит, что на левую. Обозначим $K = \sum\limits_i k_i$Предположим, что в $j$-ом мешке находятся фальшивые монеты. Тогда результат на весах будет
$$
S = \sum\limits_{i\neq j}k_i G+k_j B
$$
где $G,B$ - массы настоящих и фальшивых монет соответственно. Все, что мы знаем - так это то, что
$$
S  = (K-n)G+nB,
$$
где $n\in \mathbb{N}_0$. Нужно найти решение данного уравнения относительно $n$, причем оно должно быть единственно, потому что это необходимое условие для определения мешка с фальшивыми монетами. Все, что мы можем менять - это $k_i$. Легко видеть, что если $S = 0$ и $K=0$ - то это как раз случай, когда решение единственно: а именно, мы не взвешивали фальшивые монеты. В любом другом случае решение будет неединственным, потому что $G,B$ для нас неизвестны.

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение17.06.2011, 07:20 


14/01/11
3017
Xenia1996 в сообщении #458686 писал(а):
Уже нашла, как обойтись 45-ю монетами.

Достаточно и 9-ти монет.

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение17.06.2011, 09:14 
Заслуженный участник
Аватара пользователя


23/08/07
5486
Нов-ск
Sender в сообщении #458966 писал(а):
Xenia1996 в сообщении #458686 писал(а):
Уже нашла, как обойтись 45-ю монетами.

Достаточно и 9-ти монет.

Достаточно 30 монет всего (побывавших на весах)

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение17.06.2011, 12:03 


14/01/11
3017
TOTAL в сообщении #458988 писал(а):
Достаточно 30 монет всего (побывавших на весах)

Что-то мне кажется, что такое возможно, только если заранее известно, легче фальшивая монета настоящей или тяжелее.

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение17.06.2011, 12:17 


01/10/10

2116
Израиль (племянница БизиБивера)
TOTAL в сообщении #458988 писал(а):
Sender в сообщении #458966 писал(а):
Xenia1996 в сообщении #458686 писал(а):
Уже нашла, как обойтись 45-ю монетами.

Достаточно и 9-ти монет.

Достаточно 30 монет всего (побывавших на весах)

Почему?

 Профиль  
                  
 
 Re: Задача об 11 мешках
Сообщение17.06.2011, 12:27 
Заслуженный участник
Аватара пользователя


23/08/07
5486
Нов-ск
Xenia1996 в сообщении #459061 писал(а):
TOTAL в сообщении #458988 писал(а):
Достаточно 30 монет всего (побывавших на весах)
Почему?
Потому что из 4-х мешков достали по 4 монеты, из 3-х по 3 и т.д.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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