Взвешивание за плату.
Модераторы: Азарапетыч, Администрация
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Взвешивание за плату.
Предудыщие две задачи оказались не очень сложными. А вот теперь (имхо) посложнее. Из той же базы.
У нас есть куча монет. Известно, что настоящих среди них больше, чем фальшивых, все настоящие монеты весят одинаково. Любая фальшивая монета отличается по весу от настоящей, но фальшивые монеты могут иметь разный вес. Мы можем пользоваться чашечными весами, владелец которых после каждого взвешивания забирает себе (в качестве нашей платы) любую выбранную им монету из взвешенных. Докажите, что можно выделить хотя бы одну настоящую монету, которая останется у нас.
У нас есть куча монет. Известно, что настоящих среди них больше, чем фальшивых, все настоящие монеты весят одинаково. Любая фальшивая монета отличается по весу от настоящей, но фальшивые монеты могут иметь разный вес. Мы можем пользоваться чашечными весами, владелец которых после каждого взвешивания забирает себе (в качестве нашей платы) любую выбранную им монету из взвешенных. Докажите, что можно выделить хотя бы одну настоящую монету, которая останется у нас.
Начинаем взвешивать все монеты парами по одной монете на каждой чашке весов.
Монеты из тех взвешиваний, где одна чашка перевесит другую, отбраковываем ( по одной настоящей и по одной фальшивой или по две фальшивых. Что заберёт весовщик, неважно).
После этого по-прежнему имеем настоящих монет больше, чем фальшивых. Это значит:
Уравновесившихся чашек фальшь=фальшь меньше, чем настоящая=настоящая или
Есть ещё одна невзвешивавшаяся настоящая монета.
Поэтому, после того, как весовщик взял причитающееся, замечаем, что по-прежнему имеем настоящих монет больше, чем фальшивых.
Взвешиваем парами оставшиеся монеты по тому же алгоритму, пока не останется три или четыре монеты.
Если три, значит, минимум две настоящие. Взвешиваем две любых. Весы в равновесии = обе настоящие, весовщик берёт одну, мы другую. Если равновесия нет, настоящая - третья, забираем её.
Если четыре, значит, минимум три из них - хорошие. Взвешиваем две любых. Весы в равновесии = обе настоящие, весовщик берёт одну, мы другую. Если равновесия нет, настоящая - любая из оставшихся двух.
Монеты из тех взвешиваний, где одна чашка перевесит другую, отбраковываем ( по одной настоящей и по одной фальшивой или по две фальшивых. Что заберёт весовщик, неважно).
После этого по-прежнему имеем настоящих монет больше, чем фальшивых. Это значит:
Уравновесившихся чашек фальшь=фальшь меньше, чем настоящая=настоящая или
Есть ещё одна невзвешивавшаяся настоящая монета.
Поэтому, после того, как весовщик взял причитающееся, замечаем, что по-прежнему имеем настоящих монет больше, чем фальшивых.
Взвешиваем парами оставшиеся монеты по тому же алгоритму, пока не останется три или четыре монеты.
Если три, значит, минимум две настоящие. Взвешиваем две любых. Весы в равновесии = обе настоящие, весовщик берёт одну, мы другую. Если равновесия нет, настоящая - третья, забираем её.
Если четыре, значит, минимум три из них - хорошие. Взвешиваем две любых. Весы в равновесии = обе настоящие, весовщик берёт одну, мы другую. Если равновесия нет, настоящая - любая из оставшихся двух.
Что-то меня терзают смутные сомнения, что реншение неверно.
Конкретно из-за вот этого недоказанного утверждения:
Возможен, например, вариант три пары настоящих, две пары фальшивых (равных по весу) и одна фальшивая непарная монета. После расплаты с весовщиком фальшивых и настоящих становится по 3 штуки => нарушение условия.
Обратно, если мы будем отбраковывать непарную монету, то возможен вариант равенства пар и одной настоящей непарной.
И т. д.
Конкретно из-за вот этого недоказанного утверждения:
Невзвешивавшаяся монета может быть и фальшивой.Уравновесившихся чашек фальшь=фальшь меньше, чем настоящая=настоящая или Есть ещё одна невзвешивавшаяся настоящая монета.
Возможен, например, вариант три пары настоящих, две пары фальшивых (равных по весу) и одна фальшивая непарная монета. После расплаты с весовщиком фальшивых и настоящих становится по 3 штуки => нарушение условия.
Обратно, если мы будем отбраковывать непарную монету, то возможен вариант равенства пар и одной настоящей непарной.
И т. д.
Упс, ошибсяVersus писал(а):Что-то меня терзают смутные сомнения, что реншение неверно.
Конкретно из-за вот этого недоказанного утверждения:
Невзвешивавшаяся монета может быть и фальшивой.Уравновесившихся чашек фальшь=фальшь меньше, чем настоящая=настоящая или Есть ещё одна невзвешивавшаяся настоящая монета.
Возможен, например, вариант три пары настоящих, две пары фальшивых (равных по весу) и одна фальшивая непарная монета. После расплаты с весовщиком фальшивых и настоящих становится по 3 штуки => нарушение условия.
Обратно, если мы будем отбраковывать непарную монету, то возможен вариант равенства пар и одной настоящей непарной.
И т. д.
Утверждение в цитате верно; а следующая моя фраза
ошибочна. Надо ещё подумать.Поэтому, после того, как весовщик взял причитающееся, замечаем, что по-прежнему имеем настоящих монет больше, чем фальшивых.
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Да, кажется, поторопился говорить "верно"... Сам решал давно (задачку нашел еще "давнее" и сохранил у себя, и решения к ней не прилагалось).
Upd. На коленке набросал решение... Оно есть, будьте уверены.
Подсказка. Мы умеем не только делить монеты на пары и пользоваться весами, но и считать.
Возможен Но выход есть.Versus писал(а):Обратно, если мы будем отбраковывать непарную монету, то возможен вариант равенства пар и одной настоящей непарной.
Upd. На коленке набросал решение... Оно есть, будьте уверены.
Подсказка. Мы умеем не только делить монеты на пары и пользоваться весами, но и считать.
-
- Писатель на заборах
- Сообщения: 132
- Зарегистрирован: 06 фев 2007, 12:20
- Пол: Женский
- Откуда: БОМЖ
- Контактная информация:
мой вариант решения:
НАЧАЛО:
Пусть изначально монет чётное число. Взвешиваем монеты попарно (1 vs 1)
1) если веса разные, монету выбрасываем. (фальшивых либо 2 либо 1. настоящих не больше 1-й. Выбрасывая, настоящих монет в куче попрежнему больше фальшивых).
2) если веса одинаковые, монету откладываем. (пар фальшивая-фальшивая не больше пар настоящая-настоящая по условию задачи, поэтому, после обработки _всех_ таких равных пар, соотношение фальшивых и настоящих не изменится или усугубится)
3) оставшуюся монету кладём ко всем отложенным
Результат: осталось несколько монет. При этом число настоящих монет больше фальшивых. Если осталась одна монета, то она настоящая, если нет, то идём на НАЧАЛО.
Пусть изначально монет чётное число. Взвешиваем монеты попарно (1 vs 1)
1) см. выше
2) см. выше (наличие таких пар гарантируется тем, что настоящих больше и хотябы одна пара будет, а следовательно новая кучка будет не пуста).
Результат: см. выше
Итого: постепенно уменьшаем общее число монет сохраняя соотношение настоящих>фальшивых пока не останется одна единственная.
должно работать.
НАЧАЛО:
Пусть изначально монет чётное число. Взвешиваем монеты попарно (1 vs 1)
1) если веса разные, монету выбрасываем. (фальшивых либо 2 либо 1. настоящих не больше 1-й. Выбрасывая, настоящих монет в куче попрежнему больше фальшивых).
2) если веса одинаковые, монету откладываем. (пар фальшивая-фальшивая не больше пар настоящая-настоящая по условию задачи, поэтому, после обработки _всех_ таких равных пар, соотношение фальшивых и настоящих не изменится или усугубится)
3) оставшуюся монету кладём ко всем отложенным
Результат: осталось несколько монет. При этом число настоящих монет больше фальшивых. Если осталась одна монета, то она настоящая, если нет, то идём на НАЧАЛО.
Пусть изначально монет чётное число. Взвешиваем монеты попарно (1 vs 1)
1) см. выше
2) см. выше (наличие таких пар гарантируется тем, что настоящих больше и хотябы одна пара будет, а следовательно новая кучка будет не пуста).
Результат: см. выше
Итого: постепенно уменьшаем общее число монет сохраняя соотношение настоящих>фальшивых пока не останется одна единственная.
должно работать.
На основе своей же поправки вывел следующий алгоритм:
В случае, если у нас есть непарная монета, а число уравновешанных пар чётное, то мы эту монету не трогаем, так как, даже будучи фальшивой она не меняет основного соотношения, настоящих остаётся больше.
Если же число пар нечётное, то непарную монету надо выкинуть, так как даже, если она настоящая, то соотношение обратно не меняется.
В остальном решение team55 верно. Продолжаем попарно взвешивать, пока не останется 1 монета (в некоторых случаях можно оставить себе две монеты, но описывать в каких именно меня ломает, так как на общее решение это не влияет)
В случае, если у нас есть непарная монета, а число уравновешанных пар чётное, то мы эту монету не трогаем, так как, даже будучи фальшивой она не меняет основного соотношения, настоящих остаётся больше.
Если же число пар нечётное, то непарную монету надо выкинуть, так как даже, если она настоящая, то соотношение обратно не меняется.
В остальном решение team55 верно. Продолжаем попарно взвешивать, пока не останется 1 монета (в некоторых случаях можно оставить себе две монеты, но описывать в каких именно меня ломает, так как на общее решение это не влияет)
Итого после взвешиваний у нас на руках осталось 4 монеты. Так как число пар было нечётное (3), то невзвешенную монету мы тоже выкидываем. В результате имеем либо 3 настоящих монеты, либо 2 настоящих и одну фальшивую.Dendr писал(а):А если дано (ну, чтобы не перегружать рассуждения) 9 монет?
Пусть так вышло: четыре взвешивания, из них: три раза было равновесие, один раз - неравновесие.
Если расписать поштучно получается так:
1) Допустим, из 9 у нас была 1 фальшивая монета. Дальше, как ни взвешивай, всё равно останутся только настоящие.
2) Допустим, фальшивых было 2. Одна неуравновесилась, вторую выкинули, как непарную. Готово.
3) 3 монеты. Одна неравная, и одна пара фальшивых. После взвешивания осталась одна фальшивая из пары и две настоящие из других пар.
4) 4 монеты. Обратно одна неравная, 1 пара и одна фальшивая без пары, которую мы выкинули. После взвешиваний остаётся 2 настоящих и одна фальшивая из пары.
Re: Взвешивание за плату.
кажется, что для случая трёх монет решения нет:
пусть при первом взвешивании одна чаша перевесила и хозяин весов забрал тяжелую
если оставшаяся от взвешивания фальшивая и при втором взвешивании хозяин опять возьмет тяжёлую, то мы проиграли
скажите, если я где-то ошибся
пусть при первом взвешивании одна чаша перевесила и хозяин весов забрал тяжелую
если оставшаяся от взвешивания фальшивая и при втором взвешивании хозяин опять возьмет тяжёлую, то мы проиграли
скажите, если я где-то ошибся
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Взвешивание за плату.
А зачем делать второе взвешивание?savoyard писал(а):кажется, что для случая трёх монет решения нет:
пусть при первом взвешивании одна чаша перевесила и хозяин весов забрал тяжелую
если оставшаяся от взвешивания фальшивая и при втором взвешивании хозяин опять возьмет тяжёлую, то мы проиграли
скажите, если я где-то ошибся
При трех монетах мы знаем, что настоящих строго больше, чем фальшивых. Значит, фальшивка ровно одна. При первом взвешивании становится ясно, что фальшивка точно среди этой пары. Какую забрал хозяин весов - неизвестно. Но та, что не взвешивалась - точно настоящая.
Монету, которая участвовала во взвешивании, но ее не забрал хозяин, просто выбросим в мусорное ведро - мы нежадные.
У нас осталась ровно одна монета, и она точно настоящая. Значит, задача решена.