ЗАДАЧА 3

Дано п одинаковых с виду монет двух разных весов. Чему равно минимальное число взвешиваний, с помощью которых можно найти искомое распределение весов монет?

Решение:

Каждая монета или тяжелая, или легкая.

Поскольку у нас имеется п монет, число возможностей равно 2^n.

Как и в задаче 1, из этого числа нужно исключить два распределения, когда все монеты оказываются легкими или все они — тяжелые. Таким образом, остается 2^n — 2 возможностей.

Пусть m таково, что

3^(m-1) < 2^n — 2 <= З^m С помощью (m — 1) взвешиваний можно в лучшем случае выбрать одну из З^(m-1) возможностей Поэтому в нашем случае потребуется не менее m взвешиваний. Снова заметим, что речь идет о минимуме; если 2^n — 2 достаточно близко к З^m, то пг взвешиваний может и не хватить. В самом деле, нельзя быть уверенным, что найдется способ взвешивания, позволяющий на каждом этапе разбивать множество остающихся возможностей на три равные по численности группы.



Это не спам.

 

На нашем сайте собраны задачи занимательной арифметики, математики, геометрии;
задачи на смекалку и логику, головоломки, логические загадки, игры, ребусы и многое другое
2017 © Самый умный - математическая смекалка