math.luga.ru : Форум

Есть 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 взвешивания. Надо выяснить, есть ли фальшивая монета, а если есть, узнать, какая именно и легче она или тяжелее.

bot писал(а):Слишком легкая. Зачем нужны двое весов, тоже не понятно.

Видимо, стоит прочитать условие задачи ещё раз и заметить в нём предложение о том, что весы ломаются , если одна чаша перевешивает другую. Так что, bot решил другую задачу, которая, согласен, очень лёгкая и широко известная.

Опаньки, и в самом деле вот это пропустил:

Весы ломаются, если одна чаша на них перевесит другую.

То-то я недоумевал,

(возможно, поломав в итоге весы)

Хм, подумать надо. По Холмсу эта задачка не на одну трубку

Не, не так уж и сложно - не больше, чем на две трубки.

Вот взвешивания:

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 максимально возможное число монет.

bot писал(а):Не, не так уж и сложно - не больше, чем на две трубки.

Разумеется!