И еще одна задача о монетах№ 1
Большой Грызь

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

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

Можно ли каким-то образом найти хотя бы одну настоящую монету, которая 100%-но осталась бы у нас?
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 2
Феликс

Если куча состоит из 3-х монет, то можно
Профиль 

И еще одна задача о монетах№ 3
Большой Грызь

А, если из четырех?
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 4
Феликс

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

И еще одна задача о монетах№ 5
Большой Грызь

А для 128 монет?
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 6
Феликс

Для 128 монет можно, если можно для 127, потому что если настоящих больше среди 128, то их больше и среди 127.
Профиль 

И еще одна задача о монетах№ 7
Большой Грызь

Хороший ответ Но не в общем виде.

Итак вопрос: для какого кол-ва монет возможно то, что требуется в первом постинге? С доказательством, разумеется
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 8
Феликс

У меня получилось по индукции
Профиль 

И еще одна задача о монетах№ 9
Krasnaja Shapka

но-но... индукция не доказана... доказано только что если это можно для 2n-1 то можно и для 2n... а вот что делать для нечетных?
 Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
Профиль 

И еще одна задача о монетах№ 10
Феликс

Кучу из 2n+1 монет можно разбить на n пар и ещё одну монету.
Это подсказка
Профиль 

И еще одна задача о монетах№ 11
Большой Грызь

Феликс, ты давай без подсказок Давай решение
Потому что мне кажется, что ты совершаешь ту же ошибку, которую я совершил вначале
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 12
Феликс

Взвесим каждую из n пар, положив по одной монете на каждую чашу весов.
Рассмотрим только пары с равным весом. Если таковых нет, то монета без пары - настоящая.
Из каждой пары с равным весом возмём ту, которую оставил нам владелец, и рассмотрим кучу всех этих оствленных монет, присоединив к этой куче монету без пары.
Полученная, таким образом новая куча удовлетворяет условиям задачи, и к ней можно применить предположение индукции.
Профиль 

И еще одна задача о монетах№ 13
Большой Грызь

Из каждой пары с равным весом возмём ту, которую оставил нам владелец, и рассмотрим кучу всех этих оствленных монет, присоединив к этой куче монету без пары.
Полученная, таким образом новая куча удовлетворяет условиям задачи, и к ней можно применить предположение индукции.

Неа.. не всегда эта новая куча удовлетворит условию задачи.
Приведу пример, когда нет.

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

Итого после всех взвешиваний выходит так, что в куче отложены монеты 1,1,2,2. Подобная куча условию задачи не удовлетворяет. И даже еще хуже - при подобном раскладе найти настоящую монету не представляется возможным.
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 14
Феликс

Здесь есть один ньюанс, что я не всегда присоединяю к новой куче монету без пары.
Я делаю это только в случае, если n - чётное.
Профиль 

И еще одна задача о монетах№ 15
Большой Грызь

Так в моем примере n как раз четное Там 4 пары и еще одна монета.
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

И еще одна задача о монетах№ 16
Феликс

Прошу прощения, если не n - чётное, а если число пар с равным весом чётное.
Профиль 

И еще одна задача о монетах№ 17
Krasnaja Shapka

хм... тогда это решение...
 Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
Профиль 

И еще одна задача о монетах№ 18
Большой Грызь

угу, тогда да
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 


Вы не зарегистрированы либо не вошли в портал!!!
Регистрация или вход в портал - в главном меню.



 Просмотров:   005030    Постингов:   000018