Cool Folders ® :: Форум Игротека :: И еще одна задача о монетах

И еще одна задача о монетах

Дата : 06-12-06, Срд, 02:30:53

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

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

Можно ли каким-то образом найти хотя бы одну настоящую монету, которая 100%-но осталась бы у нас?

Only those who attempt the absurd will achieve the impossible.. (Escher)

И еще одна задача о монетах

№ 2

Феликс

Дата : 06-12-06, Срд, 08:51:05

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

И еще одна задача о монетах

№ 3

Большой Грызь

Дата : 06-12-06, Срд, 08:55:54

А, если из четырех?

Only those who attempt the absurd will achieve the impossible.. (Escher)

И еще одна задача о монетах

№ 4

Феликс

Дата : 06-12-06, Срд, 09:36:45

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

И еще одна задача о монетах

№ 5

Большой Грызь

Дата : 06-12-06, Срд, 09:38:07

А для 128 монет?

Only those who attempt the absurd will achieve the impossible.. (Escher)

И еще одна задача о монетах

№ 6

Феликс

Дата : 06-12-06, Срд, 09:45:46

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

И еще одна задача о монетах

№ 7

Большой Грызь

Дата : 06-12-06, Срд, 09:47:18

Хороший ответ

Но не в общем виде.

Итак вопрос: для какого кол-ва монет возможно то, что требуется в первом постинге? С доказательством, разумеется

Only those who attempt the absurd will achieve the impossible.. (Escher)

И еще одна задача о монетах

№ 8

Феликс

Дата : 06-12-06, Срд, 10:20:48

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

И еще одна задача о монетах

№ 9

Krasnaja Shapka

Дата : 06-12-06, Срд, 11:16:02

но-но... индукция не доказана... доказано только что если это можно для 2n-1 то можно и для 2n... а вот что делать для нечетных?

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

И еще одна задача о монетах

№ 10

Феликс

Дата : 06-12-06, Срд, 11:27:42

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

И еще одна задача о монетах

№ 11

Большой Грызь

Дата : 06-12-06, Срд, 11:30:53

Феликс, ты давай без подсказок

Давай решение

Потому что мне кажется, что ты совершаешь ту же ошибку, которую я совершил вначале

Only those who attempt the absurd will achieve the impossible.. (Escher)

И еще одна задача о монетах

№ 12

Феликс

Дата : 06-12-06, Срд, 11:45:29

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

И еще одна задача о монетах

№ 13

Большой Грызь

Дата : 06-12-06, Срд, 12:01:04

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

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

Допустим были монеты весом 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

Феликс

Дата : 06-12-06, Срд, 12:05:35

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

И еще одна задача о монетах

№ 15

Большой Грызь

Дата : 06-12-06, Срд, 12:07:00

Так в моем примере n как раз четное

Там 4 пары и еще одна монета.