Монетки.
Модератор: модераторы
-
- Администратор сайта
- Сообщения: 7188
- Зарегистрирован: Вс, 28 дек 2003, 11:47
- Откуда: Луга
- Контактная информация:
Монетки.
Есть 33 монеты, из которых одна фальшивая и весит легче настоящих, а все настоящие весят поровну. Имеются также двое двухчашечных весов. Весы ломаются, если одна чаша на них перевесит другую. Можно ли за 4 взвешивания определить фальшивую монету (возможно, поломав в итоге весы)?
Слишком легкая.
Зачем нужны двое весов, тоже не понятно. Вместо 33 берем любое число N, не превосходящее 81.
Например так:
1) Пусть n = [N/3]. Кладем на две чаши по n монет. В любом случае (равновесие есть или нет) локализуем фальшивку в не более чем 27 монетах. Для простоты добавим к ним настоящих, чтобы их стало 27.
2) 9 vs 9. Локализуем фальшивку в 9 монетах.
3) 3 vs 3. Локализуем фальшивку в 3 монетах.
4) 1 vs 1. Определяем фальшивку.
А давайте усложним:
Даны 36 монет. Возможно, одна фальшивая, хотя может быть и все настоящие. Фальшивая отличается по весу, но в какую сторону --- неизвестно. Есть чашечные весы. Можно произвести 4 взвешивания. Надо выяснить, есть ли фальшивая монета, а если есть, узнать, какая именно и легче она или тяжелее.
Зачем нужны двое весов, тоже не понятно. Вместо 33 берем любое число N, не превосходящее 81.
Например так:
1) Пусть n = [N/3]. Кладем на две чаши по n монет. В любом случае (равновесие есть или нет) локализуем фальшивку в не более чем 27 монетах. Для простоты добавим к ним настоящих, чтобы их стало 27.
2) 9 vs 9. Локализуем фальшивку в 9 монетах.
3) 3 vs 3. Локализуем фальшивку в 3 монетах.
4) 1 vs 1. Определяем фальшивку.
А давайте усложним:
Даны 36 монет. Возможно, одна фальшивая, хотя может быть и все настоящие. Фальшивая отличается по весу, но в какую сторону --- неизвестно. Есть чашечные весы. Можно произвести 4 взвешивания. Надо выяснить, есть ли фальшивая монета, а если есть, узнать, какая именно и легче она или тяжелее.
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего.
-
- Администратор сайта
- Сообщения: 7188
- Зарегистрирован: Вс, 28 дек 2003, 11:47
- Откуда: Луга
- Контактная информация:
Видимо, стоит прочитать условие задачи ещё раз и заметить в нём предложение о том, что весы ломаются , если одна чаша перевешивает другую. Так что, bot решил другую задачу, которая, согласен, очень лёгкая и широко известная.bot писал(а):Слишком легкая. Зачем нужны двое весов, тоже не понятно.
Последний раз редактировалось PSP Вт, 08 фев 2005, 9:24, всего редактировалось 1 раз.
Не, не так уж и сложно - не больше, чем на две трубки.
Вот взвешивания:
1) 7 vs 7 и 19 в сторонке
Исход а) Весы сломались. У нас одни весы, 7 монет и три попытки.
2) 1 vs 1 и 5 в сторонке. Либо определяем фальшивку либо
3) 1 vs 1 и 3 в сторонке. Либо определяем фальшивку либо
4) 1 vs 1 и 1 в сторонке и определяем фальшивку.
Исход б) После первой попытки весы не сломались. У нас двое весов, 19 монет и три взвешивания.
2) 5 vs 5 и 9 в сторонке. Если фальшивка в 9 монетах, то за два оставшихся взвешивания на двух весах определяем фальшивку (как уже замечено - это хорошо известная классика: 3 vs 3 и 3 в сторонке, 1 vs 1 и 1 в сторонке) В противном случае мы имеем одни весы, 5 монет и две попытки, как уже было при исходе а).
ЗЫ. Двигаясь от конца (собственно так и найден этот алгоритм) легко понять, что 33 максимально возможное число монет.
Вот взвешивания:
1) 7 vs 7 и 19 в сторонке
Исход а) Весы сломались. У нас одни весы, 7 монет и три попытки.
2) 1 vs 1 и 5 в сторонке. Либо определяем фальшивку либо
3) 1 vs 1 и 3 в сторонке. Либо определяем фальшивку либо
4) 1 vs 1 и 1 в сторонке и определяем фальшивку.
Исход б) После первой попытки весы не сломались. У нас двое весов, 19 монет и три взвешивания.
2) 5 vs 5 и 9 в сторонке. Если фальшивка в 9 монетах, то за два оставшихся взвешивания на двух весах определяем фальшивку (как уже замечено - это хорошо известная классика: 3 vs 3 и 3 в сторонке, 1 vs 1 и 1 в сторонке) В противном случае мы имеем одни весы, 5 монет и две попытки, как уже было при исходе а).
ЗЫ. Двигаясь от конца (собственно так и найден этот алгоритм) легко понять, что 33 максимально возможное число монет.
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего.
Вернуться в «Доска математических объявлений»
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 109 гостей