2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Классика - взвешиваем монетки
Сообщение06.08.2016, 08:26 
Аватара пользователя


11/02/15
1720
VAL в сообщении #1131175 писал(а):
Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

Может, мне просто повезло, но придумалось даже несколько решений. Одно из них распишу чуть позже.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение06.08.2016, 11:48 
Аватара пользователя


11/02/15
1720
Извиняюсь, пока расписывал ответ, обнаружил, что в одном месте мне необходимо будет четвёртое взвешивание... Так что напрасно потряс воздух громким заявлением :oops:
Надо будет снова подумать над решением.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение06.08.2016, 22:50 


01/11/14
195
Достаточно 3-х взвешиваний. Задача легко решается на основе подсчета диаметра разбиений (см. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=1310&option_lang=rus). В качестве примера в указанной статье решается задача нахождения до 2-х фальшивых монет из 11-ти тестируемых при условии, что веса фальшивых монет могут отличаться от настоящих в большую или меньшую сторону на одну и ту же величину. Построен алгоритм, который за 5 взвешиваний находит фальшивые монеты (если они есть) и определяет их относительные веса.
Попробуйте для интереса построить алгоритм, который за 5 или менее взвешиваний находит эти монеты без определения их относительных весов.
Общий подход и конструкции этой работы использованы в https://arxiv.org/pdf/1606.04170.pdf, однако здесь не показан принцип построения взвешиваний, который может быть использован для сформулированной VAL задачи.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 11:24 


31/05/11
28
Решение под спойлером, на случай если кто-то ещё сам хочет подумать.

(Ответ)

I. Взвешиваем две золотые монеты.
1. Если одна легче, то она фальшивая, а вторая настоящая. Остаётся 4 серебрянных и две золотых, из которых одна фальшивая.
2. Если монеты одинаковые, то либо они обе фальшивые, либо обе настоящие. Откладываем по одной монете из двух взвешенных золотых и двух невзвешенных, запоминая из какая где. Остаётся, как и в первом случае, 4 серебрянных и две золотых, из которых одна фальшивая.

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

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


VAL в сообщении #1131175 писал(а):
Если нужно, могу предложить еще массу вариаций.

Спасибо за эту, и нужно ещё, конечно.
А вы их сами придумываете?

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 13:19 
Аватара пользователя


11/02/15
1720
HungryLion в сообщении #1142545 писал(а):
II. Кладем в каждую чашку весов золотую и серебрянную монетки.
1. Если одна чашка легче, то в ней фальшивая золотая монета, а в другой чашке настоящая серебрянная.

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

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 14:58 
Аватара пользователя


11/02/15
1720
Чувствуется, что здесь дедовским способом (методом проб и ошибок) решить будет практически невозможно. Скорее всего необходимо будет применить запутанную комбинаторику, которую в уме представить и сообразить окажется очень сложным занятием.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 15:07 


31/05/11
28
A.Edem в сообщении #1142553 писал(а):
HungryLion в сообщении #1142545 писал(а):
II. Кладем в каждую чашку весов золотую и серебрянную монетки.
1. Если одна чашка легче, то в ней фальшивая золотая монета, а в другой чашке настоящая серебрянная.

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

Так, вроде, пункт II.2. про это. К этому моменту одна золотая монета из взвешиваемых точно фальшивая, так что указанной вами ситуации возникнуть не может.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 16:07 
Аватара пользователя


11/02/15
1720

(Оффтоп)

HungryLion, к сожалению, мне всё равно многое непонятно, начиная со второго этапа Ваших объяснений :-(
Начнём по порядку. "Кладем в каждую чашку весов золотую и серебряные монетки". Вопрос: откуда берем для этого действия золотую монету? И почему при равновесии весов впоследствии она должна оказаться именно фальшивой, а не настоящей, к примеру, - с настоящей серебряной в противовес? - "2. Если чашки одинаковые, то в одной из них фальшивая злотая монета, а в другой фальшивая серебрянная."

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 17:36 
Заслуженный участник


27/06/08
4058
Волгоград
HungryLion в сообщении #1142545 писал(а):
VAL в сообщении #1131175 писал(а):
Если нужно, могу предложить еще массу вариаций.

Спасибо за эту, и нужно ещё, конечно.

Пожалуйста:
Имеется 6 золотых и 5 серебряных монет (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За четыре взвешивания на чашечных весах без гирь определить фальшивые монеты.

А еще одна задачка (ММ179) здесь уже пробегала.

Цитата:
А вы их сами придумываете?

Да.
Некоторые новые идеи почерпнул, общаясь с Константином Кнопом (он заглядывает на dxdy).

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 17:46 


31/05/11
28

(Оффтоп)

A.Edem в сообщении #1142591 писал(а):
Кладем в каждую чашку весов золотую и серебряные монетки". Вопрос: откуда берем для этого действия золотую монету?
Согласен, не очень понятно написал.
В каждую чашку кладём две монеты: золотую и серебрянную. Откуда берём золотые, зависит от результата первого взвешивания: если одна была легче, то берём две, которые не взвешивали; если обе одинаковые, то берём одну из взвешенных и одну из оставшихся. Таким образом гарантированно во втором взвешивании одна злотая монета фальшивая а одна настоящая.
A.Edem в сообщении #1142591 писал(а):
И почему при равновесии весов впоследствии она должна оказаться именно фальшивой, а не настоящей, к примеру, - с настоящей серебряной в противовес?
Так как точно одна золотая фальшивая а другая настоящая, то равновесие означает что одна серебрянная монета фальшивая.


-- Вс авг 07, 2016 18:51:44 --

VAL
Спасибо, буду размышлять.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение07.08.2016, 20:54 
Аватара пользователя


11/02/15
1720

(Оффтоп)

HungryLion, ах, вот теперь всё стало на свои места! Теперь я с радостью ясно вижу верность искомого решения. Благодарю за пояснения и за ответ к задаче.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение08.08.2016, 14:08 
Аватара пользователя


11/02/15
1720
Ответ на задачу про шесть золотых и пять серебряных монет:

(Оффтоп)

После приёма, показанного HungryLion, решать подобные задачи, кажется простым развлечением.
Сначала ставим на весы по две серебряные монеты. Так выявляем три настоящие и пару, в которой неизвестно где настоящая и где фальшивая. Ставим эту пару на разные чаши весов, к ним же ставим по одной золотой монете (6 золотых монет делим на три пары). Если показало равновесие, то запоминаем, как что стояло. Берём вторую пару золотых (убирая с весов первую), и ставим их к первоначальным серебряным. Если снова показало равновесие, то тогда меняем местами монеты в двух парах золотых, ставим к ним начальную пару серебряных, и взвешиваем, легко определяя, где настоящие, а где фальшивые.
Если после взвешивания второй пары золотых монет весы показали перевес, то мы узнаем таким образом, где была фальшивая и настоящая серебряные, где в первой паре золотых были фальшивая и настоящая, а также одну настоящую золотую. Останется для четвёртого взвешивания узнать, где находится фальшивая среди трёх оставшихся золотых, что сделать очень просто.
Если же после начального взвешивания первой пары золотых весы показали перевес, значит, мы узнали, где настоящая и фальшивая серебряные, а также настоящую золотую. Остались 4 золотые, среди которых одна фальшивая. Берём две настоящие серебряные на одну чашу весов, а на вторую любую пару золотых. Если покажет равновесие, значит, нам попались две золотые настоящие монеты. Если же перевесят серебряные, то это будет означать, что на весах одна фальшивая и одна настоящая золотые. Последним взвешиванием легко обнаружить, где из них какая.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение08.08.2016, 15:57 
Аватара пользователя


11/02/15
1720
Только что получилось решить немного другим способом. Потому теперь интересно: каковы авторские решения этих задач?

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение08.08.2016, 17:57 


01/11/14
195
Решение задачи 4G+4S, которое выложил выше HungryLion, неверно: при равновесии в первых двух взвешиваниях ситуация не идентифицируется.

Также ошибочно решение задачи 6G+5S, которое привел A.Edem. Чтобы убедиться, нужно просто более детально проверить возможные ситуации (расположения нормальных и фальшивых монет) после второго взвешивания, если и в первом, и во втором случаях весы неуравновешены.

Вообще и HungryLion, и A.Edem нужно корректно расписать, куда кладутся какие монеты. Взвешивания удобно представлять набором $(h_1, \dots, h_8),$ где $h_i \in \{-1.0,1\}, $ причем при $h_i=-1$ $i$-я монета кладется на левую чашу, при $h_i=1$ – на правую и при $h_i=0$ не участвует во взвешивании (см. ссылки выше). В задаче можно положить номера золотых монет $1, \dots, 4$ и серебряных $5, \dots, 8$. Далее результат взвешивания: $-1, 0, 1$ – соответственно левая чашка легче, равновесие, тяжелее.
Без нормального представления решения будет много разговоров и мало толку.

 Профиль  
                  
 
 Re: Классика - взвешиваем монетки
Сообщение09.08.2016, 00:24 
Аватара пользователя


11/02/15
1720
Iam, я могу одно сказать по этому поводу: расписать всё красиво, научно у меня, скорее всего, не получится. HungryLion же, полагаю, выложил неполный вариант решения потому, как не старался придерживаться красоты стиля изложения ответа, а писал он его для тех, кто действительно пытался своими силами решить эту задачу, для тех, кто мог бы понять его лишь потому, что сам искал ответ, кому не нужно уже подробное расписывание. Лично я лишь в одном месте не сразу уловил его мысль, но когда он поправился и уточнил свою идею, мне сразу стало ясно, что это и есть правильное решение.
Если честно, то чтобы всё подробно расписать, особенно те моменты, которые он упустил по понятной причине ненужности и так понятных объяснений, то пришлось бы использовать ещё очень много ненужных слов, или не совсем много мало кому понятных условных обозначений или чисел. В последней задаче подробное решение будет и того длиннее.
Перепроверив, я не заметил ошибки в решении.

-- 09.08.2016, 01:26 --

Хорошо было бы, если бы уважаемый VAL нас рассудил.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 54 ]  На страницу Пред.  1, 2, 3, 4  След.

Модератор: Модераторы



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

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


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

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