Загадали загадку

[tyomitch]

Есть традиционная загадка: даны 6 мешков монет, в каждом настоящие или фальшивые, весят 1.00 и 0.99 грамм соответственно. За одно взвешивание на точных электронных весах определить, где какие.

Её традиционное решение -- не буду его приводить -- требует, чтобы в мешках было до 32 монет. Если в каждом мешке, скажем, по 31 монете, то оно не срабатывает.

Поэтому загадка утяжеляется: как определить, где какие монеты, если в мешках их всего по 30? И какое минимальное количество монет в мешках, что если меньше, то определить за одно взвешивание уже не удастся?


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

[SLIM]

Что-то я не совсем догнал в чем задача. Можешь чуть поподробнее?

[tyomitch]

даны 6 мешков монет, в каждом настоящие или фальшивые, весят 1.00 и 0.99 грамм соответственно. За одно взвешивание на точных электронных весах определить, где какие.

Какое место пояснить?

[Zenitchik]

дубль

[Zenitchik]

Как устроены весы?
Фальшивые монеты содержатся только в одном мешке или могут быть в нескольких?
В мешках одинаковое количество монет?

[tyomitch]

Как устроены весы?
Фальшивые монеты содержатся только в одном мешке или могут быть в нескольких?
В мешках одинаковое количество монет?

1) На них кладут груз, они показывают цифру.
2) Могут быть в нескольких. Могут не быть ни в одном. Но в одном мешке либо все фальшивые, либо все подлинные.
3) В традиционной формулировке, их там неограниченно много. В утяжелённой как раз нужно узнать, сколько их там, по-минимуму, должно быть. Мешки не завязаны: можно класть на весы произвольное число монет из мешка.

[SLIM]

В мешках одинаковое количество монет?

Меня тоже интересует этот вопрос. В двух разных мешках обязательно одинаковое количество, или может быть разное?

[tyomitch]

В мешках одинаковое количество монет?

Меня тоже интересует этот вопрос. В двух разных мешках обязательно одинаковое количество, или может быть разное?

Для задачи это совершенно несущественно. Ну пусть будет поровну.

[Alec]

Не пойму, в чем подвох... Причем тут 32?
Нумеруем мешки (для простоты) от 1 до 6. (еще проще нумеровать от 0 до 5)
Ложим на весы с первого мешка - одну, со второго - две, с третьего - 3 и т.д., но с шестого не ложим.
Т.е. всего используем 15 монет, а максимальное количество монет, которые берем из мешка - 5.

Смотрим на полученный вес.
Если он точно равен 15, то все монеты настоящие, а фальшивые в шестом мешке.
Если меньше, то узнаем на сколько, эта разница поделенная на разницу в весе фальшивой и настоящей монеты (а она по условию известна) даст количество фальшивых монет, которое совпадает с номером мешка...

[tyomitch]

2) Могут быть в нескольких. Могут не быть ни в одном. Но в одном мешке либо все фальшивые, либо все подлинные.

У тебя, для примера, фальшь в 1 и 2 неотличима от фальши в 3.

[Alec]

Ага, понял. Точнее сначала не понял, а теперь понял, что количество фальшивых мешков >1... Тогда вот оно и 32...И это, я так понимаю, классическое решение...

[tyomitch]

Ага, классическое оно много кому известное.
А какие мысли про утяжелённое?

[Alec]

У меня утяжеленная мысль одна - ну нет однозначного решения. Разве только с пустыми мешками ...

[tyomitch]

Тогда попробуй сначала решить для 4 мешков, там вариантов так мало, что можно перебрать все в уме. Там тоже есть решение "экономнее" классического.
После этого идея загадки станет прозрачнее.

[tyomitch]

Загадчик признался, что не знает решения. И что загадавший ему тоже не знает.
Мы в хорошей компании

[Zenitchik]

Меньше 32 монет - это в смысле монет недостаточно для того, чтобы брать из всех мешков по степеням двух? (вообразил себе 64 мешка, гору денег и монструозные весы)

[tyomitch]

Меньше 32 монет - это в смысле монет недостаточно для того, чтобы брать из всех мешков по степеням двух? (вообразил себе 64 мешка, гору денег и монструозные весы)

Именно.