Question

Вмузее города красноярска имеется коллекция из 96 одинаковых золотых монет, лежащих в ряд. однажды милицией был пойман известный вор, у которого обнаружили 19 монет из этой коллекции. на следствии он показал, что два года назад заменил 19 лежащих подряд монет на фальшивые, которые легче настоящих, но внешне от них неотличимы. следователь немедленно отправился в музей, чтобы изъять фальшивые монеты. по дороге он вспомнил, что он не спросил у вора, где именно они лежат. но, найдя в музее чашечные весы, он понял, что сможет отыскать все фальшивые монеты сам. за какое наименьшее количество взвешиваний ему удастся это сделать? с нормальным объяснением, не с тем, что в интернете

Answer 1

Здесь в условии самое главное, что монеты лежат подряд.
Следователь берёт 19 монет с одного края и 19 монет со второго края и кладёт их на разные чашки весов. Если чашки уравновешены, значит все 38 монет настоящие. Следователь их откладывает и берёт опять по 19 монет подряд с каждого края. Если и на этот раз чашки уравновешены, то и эти 38 монет настоящие. Следователю остается найти оставшуюся настоящую монету среди 20 оставшихся монет. Для этого он должен взвесить 2 крайние монеты - одна из них настоящая, т.к. фальшивые лежат подряд. Это найпростейший случай, если заменены монеты посредине.

1. Рассмотрим случай, когда при одном из взвешиваний оказалось, что одна чашка легче, т.е. на одной чашке есть фальшивые монеты, но не известно, сколько их. Это может появиться как при 1-м так и при втором взвешивании, описанном выше. Тогда с того края, где монеты оказались легче, необходимо к уже взятым монетам взять еще 18 монет (это следует из того, что на чашке, которая легче, могла оказаться только 1 фальшивая монета, т.е. следующие 18 за ней тоже могут оказаться фальшивыми). У нас оказывается 37 монет. При этом средняя монета точно фальшивая. Нужно найти 18 фальшивых монет.
2. Берем по 9 монет, отсчитывая от средней монеты, и кладем их на чашки весов. Если чашки уравновешены, то значит все эти монеты фальшивые. Если чашки неуравновешены, то все монеты на более легкой чашке фальшивые, также а также фальшивая и следующая монета по направлению от средины, а все монеты с противоположного края, которые еще не взвешивали, настоящие, также настоящая и 10-я монета по направлению к средине.  Осталось найти 8 монет из оставшихся 16.
3. Взвешиваем по 4 монеты, отсчитывая от средины. Если вес монет одинаков, они фальшивые. Т.е. все фальшивые монет найдены. Если чашки неуравновешены, то на той чашке, которая легче, все монеты фальшивые + еще одна, если считать дальше от средины. С противоположного края все монеты, которые не взвешивали, настоящие, + еще одна монета, если считать по направлению к средине. Те. нашли еще 5 фальшивых монет, всего 16. Осталось найти 3 фальшивые монеты из 6 оставшихся.
4. Здесь просто взвешиваем по одной монете, начиная со средины. Если же при взвешивании средних получилось, что только одна монета фальшивая, то фальшивые и остальные 2 монеты с той же стороны. Если вес средних монет одинаков - они фальшивые. Значит нужно еще одно взвешивание от средины.
5. Следующее взвешивание укажет на еще одну фальшивую.  
Получилось минимум 3 взвешивания, максимум 6 взвешиваний.
Где-то так...