9 монет

Логические задачи

Модераторы: Азарапетыч, Администрация

9 монет

Сообщение Dendr » 15 авг 2014, 13:53

Нашел на одном сайте головоломок. Ответ еще не приведен, но я, вроде, нашел решение - сравнимся?

Даны 9 монет, среди них одна настоящая, еще четыре - одинакового веса легче настоящей, и последние четыре - одинаковые тяжелее ее.
Как за 6 взвешиваний на чашечных весах без гирь найти настоящую?
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: 9 монет

Сообщение Юляша » 18 авг 2014, 09:50

Что-то вариантов многовато получается.

Пойду рассуждать по ходу. Пусть монеты помечены как АБВГДЕЖЗИ

1 взвешивание. АБ-ВГ
2 взвешивание. ДЕ-ЖЗ

Если в обоих случаях равновесие, то настоящая монета - И.

I. АБ=ВГ, ДЕ>ЖЗ

АБВГ - все фальшивые.

3 взвешивание. Д-Е
4 взвешивание. Ж-З

Если есть равновесие, то останется 2 взвешивания на три монеты, хотя и неизвестно, легче или тяжелее настоящая. Это легко.

Пусть Д>Е и Ж>З. И - фальшивая

5 взвешивание. Д-Ж

При Д>Ж, Ж - настоящая, при равенстве взвешиваем (6) Е-З, более тяжелая - настоящая.

В этом варианте все.

II. АБ>ВГ, ДЕ>ЖЗ.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3136
Зарегистрирован: 15 янв 2009, 12:32

Re: 9 монет

Сообщение Dendr » 18 авг 2014, 11:40

Небольшой комментарий: решение начать со сравнения весов пар любопытно, но, как по мне, усложняет задачу. Чисто комбинаторно.

Первично у нас 9!/1!4!4!=630 комбинаций. (<3^6=729)

Если взвешивать первым ходом две монеты (т.е. по одной на чашку), то при равенстве выйдет, что либо это Л-Л (и 7!/1!2!4!=105 комбинаций остальных), либо Т-Т, и в сумме - 210 комбинаций, или ровно треть. При неравенстве, соответственно, тоже 210. (<3^5=243)

Если же брать четыре монеты, то при равенстве будет либо ЛЛ-ЛЛ (и всего лишь 5 комбинаций), либо ТТ-ТТ (5), либо ЛТ-ЛТ (5!/1!2!2!=30 комбинаций остальных монет и х4, поскольку внутренний состав пар неизвестен пока) всего - 130. Это меньше 243, но вот неравенство уже даст 250 комбинаций, что больше 243. То есть задача усложняется: возникнет неопределенность. Это не критично: нам не надо разделять тяжелые и легкие монеты, но на первых порах я решил этого избежать (взвешивая монеты попарно). И вполне успешно, как мне кажется.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: 9 монет

Сообщение Юляша » 20 авг 2014, 08:57

Мне как-то хотелось уйти от шаблонного подхода.

Но, похоже, действительно - шаблонный подход работает.

Первые 4 взвешивания - 4 пары разных монет.

1. 4 равновесия - оставшаяся монета настоящая

2. 3 равновесия - хватит еще 1 взвешивания

3. 2 равновесия.
5 взвешивание - сравниваем 2 "легкие" монеты и без проблем дожимаем последним взвешиванием.

4. 1 равновесие.
5 взвешивание - сравниваем 2 "легкие" монеты с третьей легкой и и девятой монетой. Независимо от результата на последнее взвешивание остается 3 монеты, причем известно, тяжелее настоящая или легче.

5. 0 равновесий.
5 взвешивание - сравниваем T1, Т2, Л3 c T3, T4, Л2. Независимо от результата на последнее взвешивание остается 3 монеты, причем известно, тяжелее настоящая или легче.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3136
Зарегистрирован: 15 янв 2009, 12:32

Re: 9 монет

Сообщение Dendr » 20 авг 2014, 10:26

О как. И более изящно, чем я решил.
Только небольшая поправка: при неравенстве в последнем случае мы не знаем про настоящую много: можем получить тройку из всех разных монет. Вот как это показать. Пусть мы взвесили 4 пары монет и разложили их так, чтобы та, что тяжелее, была левее своей напарницы.
Тривиальная комбинация - это ТЛ ТЛ ТЛ ТЛ Н.
Но нас будут интересовать вот эти три:
ТЛ ТЛ ТН ТЛ Л
ТЛ ТЛ НЛ ТЛ Т
ТЛ ТЛ ТЛ НЛ Т
Взяв, как предлагается, две тройки, получим наборы, соответственно:
ТТН-ТТЛ (экв. Н-Л)
ТТЛ-НТЛ (экв. Т-Н)
ТТЛ-ТНЛ (экв. Т-Н)
В каждом случае "выброшены" одинаковые монеты с каждой стороны, так что видно, как левая чаша перевесила. Остались комбинации НТТ, ЛНТ, ТНЛ.
Собственно, далее достаточно просто сравнить суммарный вес третьей пары (состав которой неизвестен) с весом первой пары (которая однозначно ТЛ). При равенстве настоящая - Т4, при неравенстве - уже понятно: легче - настоящая замещает более тяжелую, т.е. Т3, наоборот - Л3.

При перевешивании правой чаши - перенумерация монет решает. А равенство - вообще тривиально.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: 9 монет

Сообщение Dendr » 20 авг 2014, 14:43

Вот мое решение. Довольно мудреное в наиболее сложном случае, хотя на первых уровнях довольно удобно (имхо)
Слова "тяжелая" и "легкая" в кавычках или со словом "более" будут обозначать монеты по сравнению с другими какими-то, а без кавычек - в абсолютном смысле, т.е. точно фальшивые.

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

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

Б. Два неравновесия и последующее неравенство при третьем взвешивании означает, что настоящая монета среди этих четырех. Сравним веса "тяжелых" монет из этих пар. Более легкая - и есть настоящая. Но если они равны, то они обе - тяжелые, значит, настоящая - "легкая" из "тяжелой" пары. Попутно мы могли допустить еще и два равновесия - но даже в этом случае получилось 6 взвешиваний в сумме.

В. Два неравновесия и последующее равновесие. Это значит, что мы точно опознали 4 монеты: 2 тяжелые и 2 легкие. С пятью - неопределенность, и дальше надо разделять:

В1. Если попутно было два равновесия, то настоящая монета - однозначно последняя нетронутая.
В2. Если попутно было одно равновесие (к этому моменту сделано 4 взвешивания), то это эквивалентно трем равновесиям. Двух взвешиваний хватает, чтобы не перейти лимит.
В3. Если равновесий еще не встретилось. И тут начинается...

Вторая фаза.
Известны две тяжелые монеты и две легкие, все точно фальшивые. Сформируем эталон: пару ТЛ. Также есть пять монет с распределением ТТНЛЛ. Задача: найти настоящую за 3 взвешивания. (интересно, что число вариантов 5!/1!2!2!=30, что больше 27=3^3, однако это не помеха, как покажет схема)

Теперь берем две монеты из пятерки и сравним их веса (4-е взвешивание).
При равенстве переходим в В2, неинтересно.
При неравенстве (обозначим эти монеты по-английски для удобства записи: h-eavy и L-ight) же берем две монеты из оставшихся трех и сравним с эталоном (5-е взвешивание)

а) Равенство значит, что мы тоже взяли ТЛ. Неважен порядок, просто отлижим их в сторону. У нас остались неопознаны три монеты - ТНЛ, причем две из них уже взвешены друг с другом. Теперь возьмем их вместе и сравним с эталоном (6-е взвешивание). При равновесии настоящая - последняя, нетронутая, если же неравновесие, то работает простое соотношение: ТН>ТЛ>НЛ. Пара тяжелее эталона - настоящая легче напарницы, и наоборот.
б) Неравенство в большую сторону значит, что мы взяли либо ТТ, либо ТН, хотя порядок неизвестен. В первом случае ясно, что на 4-м взвешивании мы брали пару НЛ (больше нечего), а во втором - ТЛ. То есть, если мы возьмем только что взвешенную пару и монету h. В этой тройке две монеты одинаковы и тяжелее третьей (настоящей). За одно, шестое взвешивание, мы определяем настоящую.
в) В противном случае - ЛЛ либо НЛ, соответственно, на 4-м: ТН либо ТЛ, т.е. L - либо Н, либо Л, а значит мы получили тройку ЛЛН, которую опознаем за одно, 6-е взвешивание.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: 9 монет

Сообщение Юляша » 21 авг 2014, 11:55

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

При неравенстве - более легкая монета настоящая; при равенстве - настоящей будет "легкая" монета с тяжелой чашки пятого взвешивания.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3136
Зарегистрирован: 15 янв 2009, 12:32

Re: 9 монет

Сообщение Dendr » 21 авг 2014, 15:44

Ох ты... а так и правда проще. Это я перемудрил.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.


Вернуться в Задачки

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

Сейчас этот форум просматривают: Яндекс [Bot] и гости: 2

cron