Взвешивание за плату.

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

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

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

Взвешивание за плату.

Сообщение Dendr »

Предудыщие две задачи оказались не очень сложными. А вот теперь (имхо) посложнее. Из той же базы.

У нас есть куча монет. Известно, что настоящих среди них больше, чем фальшивых, все настоящие монеты весят одинаково. Любая фальшивая монета отличается по весу от настоящей, но фальшивые монеты могут иметь разный вес. Мы можем пользоваться чашечными весами, владелец которых после каждого взвешивания забирает себе (в качестве нашей платы) любую выбранную им монету из взвешенных. Докажите, что можно выделить хотя бы одну настоящую монету, которая останется у нас.

Аватара пользователя
team55
Популярный автор
Популярный автор
Сообщения: 1086
Зарегистрирован: 18 апр 2006, 16:49

Сообщение team55 »

Начинаем взвешивать все монеты парами по одной монете на каждой чашке весов.

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

После этого по-прежнему имеем настоящих монет больше, чем фальшивых. Это значит:

Уравновесившихся чашек фальшь=фальшь меньше, чем настоящая=настоящая или
Есть ещё одна невзвешивавшаяся настоящая монета.

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

Взвешиваем парами оставшиеся монеты по тому же алгоритму, пока не останется три или четыре монеты.

Если три, значит, минимум две настоящие. Взвешиваем две любых. Весы в равновесии = обе настоящие, весовщик берёт одну, мы другую. Если равновесия нет, настоящая - третья, забираем её.

Если четыре, значит, минимум три из них - хорошие. Взвешиваем две любых. Весы в равновесии = обе настоящие, весовщик берёт одну, мы другую. Если равновесия нет, настоящая - любая из оставшихся двух.

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

Сообщение Dendr »

Быстро вы... :)
Доказательство немного путаное в середине, но все верно.

Кузнец
Читатель
Читатель
Сообщения: 1
Зарегистрирован: 14 мар 2007, 11:43
Пол: Мужской
Контактная информация:

Сообщение Кузнец »

интересный вопрос, а верный ответ (не запутанный:) будет?

Аватара пользователя
Versus
Литератор-любитель
Литератор-любитель
Сообщения: 404
Зарегистрирован: 12 май 2006, 13:36

Сообщение Versus »

Что-то меня терзают смутные сомнения, что реншение неверно.
Конкретно из-за вот этого недоказанного утверждения:
Уравновесившихся чашек фальшь=фальшь меньше, чем настоящая=настоящая или Есть ещё одна невзвешивавшаяся настоящая монета.
Невзвешивавшаяся монета может быть и фальшивой.

Возможен, например, вариант три пары настоящих, две пары фальшивых (равных по весу) и одна фальшивая непарная монета. После расплаты с весовщиком фальшивых и настоящих становится по 3 штуки => нарушение условия.

Обратно, если мы будем отбраковывать непарную монету, то возможен вариант равенства пар и одной настоящей непарной.

И т. д.

Аватара пользователя
team55
Популярный автор
Популярный автор
Сообщения: 1086
Зарегистрирован: 18 апр 2006, 16:49

Сообщение team55 »

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

Возможен, например, вариант три пары настоящих, две пары фальшивых (равных по весу) и одна фальшивая непарная монета. После расплаты с весовщиком фальшивых и настоящих становится по 3 штуки => нарушение условия.

Обратно, если мы будем отбраковывать непарную монету, то возможен вариант равенства пар и одной настоящей непарной.

И т. д.
Упс, ошибся :(
Утверждение в цитате верно; а следующая моя фраза
Поэтому, после того, как весовщик взял причитающееся, замечаем, что по-прежнему имеем настоящих монет больше, чем фальшивых.
ошибочна. Надо ещё подумать.

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

Сообщение Dendr »

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

Upd. На коленке набросал решение... Оно есть, будьте уверены.
Подсказка. Мы умеем не только делить монеты на пары и пользоваться весами, но и считать.

hilor
Писатель на заборах
Писатель на заборах
Сообщения: 132
Зарегистрирован: 06 фев 2007, 12:20
Пол: Женский
Откуда: БОМЖ
Контактная информация:

Сообщение hilor »

мой вариант решения:

НАЧАЛО:

Пусть изначально монет чётное число. Взвешиваем монеты попарно (1 vs 1)
1) если веса разные, монету выбрасываем. (фальшивых либо 2 либо 1. настоящих не больше 1-й. Выбрасывая, настоящих монет в куче попрежнему больше фальшивых).
2) если веса одинаковые, монету откладываем. (пар фальшивая-фальшивая не больше пар настоящая-настоящая по условию задачи, поэтому, после обработки _всех_ таких равных пар, соотношение фальшивых и настоящих не изменится или усугубится)
3) оставшуюся монету кладём ко всем отложенным
Результат: осталось несколько монет. При этом число настоящих монет больше фальшивых. Если осталась одна монета, то она настоящая, если нет, то идём на НАЧАЛО.

Пусть изначально монет чётное число. Взвешиваем монеты попарно (1 vs 1)
1) см. выше
2) см. выше (наличие таких пар гарантируется тем, что настоящих больше и хотябы одна пара будет, а следовательно новая кучка будет не пуста).
Результат: см. выше

Итого: постепенно уменьшаем общее число монет сохраняя соотношение настоящих>фальшивых пока не останется одна единственная.

должно работать.

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

Сообщение Dendr »

А если дано (ну, чтобы не перегружать рассуждения) 9 монет?
Пусть так вышло: четыре взвешивания, из них: три раза было равновесие, один раз - неравновесие.

Аватара пользователя
Versus
Литератор-любитель
Литератор-любитель
Сообщения: 404
Зарегистрирован: 12 май 2006, 13:36

Сообщение Versus »

На основе своей же поправки вывел следующий алгоритм:

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

Если же число пар нечётное, то непарную монету надо выкинуть, так как даже, если она настоящая, то соотношение обратно не меняется.

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

Аватара пользователя
Versus
Литератор-любитель
Литератор-любитель
Сообщения: 404
Зарегистрирован: 12 май 2006, 13:36

Сообщение Versus »

Dendr писал(а):А если дано (ну, чтобы не перегружать рассуждения) 9 монет?
Пусть так вышло: четыре взвешивания, из них: три раза было равновесие, один раз - неравновесие.
Итого после взвешиваний у нас на руках осталось 4 монеты. Так как число пар было нечётное (3), то невзвешенную монету мы тоже выкидываем. В результате имеем либо 3 настоящих монеты, либо 2 настоящих и одну фальшивую.

Если расписать поштучно получается так:

1) Допустим, из 9 у нас была 1 фальшивая монета. Дальше, как ни взвешивай, всё равно останутся только настоящие.

2) Допустим, фальшивых было 2. Одна неуравновесилась, вторую выкинули, как непарную. Готово.

3) 3 монеты. Одна неравная, и одна пара фальшивых. После взвешивания осталась одна фальшивая из пары и две настоящие из других пар.

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

Muzozavr
Читатель
Читатель
Сообщения: 11
Зарегистрирован: 07 окт 2007, 11:15
Пол: Мужской

Сообщение Muzozavr »

Не буду я у него ничего взвешивать. Обломится. Лучше пойду в аптеку и попрошу у них взвесить. Обычно аптекари не такие жадные. :P

savoyard
Читатель
Читатель
Сообщения: 2
Зарегистрирован: 27 дек 2007, 02:06

Re: Взвешивание за плату.

Сообщение savoyard »

кажется, что для случая трёх монет решения нет:

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

скажите, если я где-то ошибся

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

Re: Взвешивание за плату.

Сообщение Dendr »

savoyard писал(а):кажется, что для случая трёх монет решения нет:

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

скажите, если я где-то ошибся
А зачем делать второе взвешивание?
При трех монетах мы знаем, что настоящих строго больше, чем фальшивых. Значит, фальшивка ровно одна. При первом взвешивании становится ясно, что фальшивка точно среди этой пары. Какую забрал хозяин весов - неизвестно. Но та, что не взвешивалась - точно настоящая.
Монету, которая участвовала во взвешивании, но ее не забрал хозяин, просто выбросим в мусорное ведро - мы нежадные.
У нас осталась ровно одна монета, и она точно настоящая. Значит, задача решена.

Ответить

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