Взвешивание монет

Во всех задачах с монетами предлагается некоторое число одинаковых с виду монет. Одна или несколько из них отличаются по весу от остальных. Разумеется, разность в весе слишком мала, чтобы ее возможно было обнаружить, просто взяв монету в руку.

Как же следует поступить, чтобы определить самую тяжелую или самую легкую монету? Вероятно, боль­шинство людей просто стало бы сравнивать попарно вес монет, пока не обнаружится монета, отличная по весу от остальных.

Но Жанно, орудуя на своем солнечном чердаке со старыми весами, не собирается торопиться — он хочет отыскать способ, позволяющий определить нужную монету с помощью минимального числа взвешиваний.

ЗАДАЧА 1

Имеется 21 монета, одна из которых несколько тяжелее других, однако с виду они все одинаковы. Какое наименьшее число взвешиваний на чашечных весах без гирь потребуется произвести, чтобы определить эту тяжелую монету?

ЗАДАЧА 2

Имеется 200 одинаковых по виду монет, одна из которых тяжелее остальных. За сколько взвешиваний можно определить эту самую тяжелую монету?

ЗАДАЧА З

Теперь рассмотрим более общую задачу Имеется п одинаковых с виду монет, одна из которых тяжелее остальных. Какое число взвешиваний нам придется произвести, чтобы отыскать эту монету?

ЗАДАЧА 4

Имеется 8 одинаковых с виду монет На каждую чашу весов кладут по четыре монеты. Одна чаша весов перевешивает, ибо одна из монет отличается по весу от остальных семи. С помощью какого числа дополни­тельных взвешиваний можно обнаружить монету, отличную по весу от других?

ЗАДАЧА 5

Имеется 9 одинаковых с виду монет, одна из которых отличается по весу от остальных восьми. Как и с по­мощью какого числа взвешиваний можно найти эту мо­нету, пользуясь чашечными весами без гирь?

ЗАДАЧА 6

На каждую чашу весов кладут по 40 одинаковых с виду монет.

ЗАДАЧА 7

Месье Мартен имеет 15 одинаковых с виду монет, одна из которых по весу отличается от остальных четырнадцати. При этом на одной из этих 14 монет «нормального» веса имеется царапина, позволяющая ее опознать.

Месье Мартен предложил трем своим друзьям сле­дующую задачу: как найти отличающуюся по весу монету с помощью чашечных весов не более чем за три взвешивания? После пятиминутного размышления один из трех друзей, месье Бертран, видный математик, показал месье Мартену, что эта задача неразрешима.

Как рассуждал месье Бертран?

ЗАДАЧА 8

Несмотря на аргументы месье Бертрана, месье Мартен настаивал, что отыскать монету, отличную по весу от других, всегда возможно с помощью только трех взвешиваний. Кто же прав — месье Бертран или месье Мартен? Если прав месье Мартен, то как отыскать монету, отличную по весу от других, с помощью только трех взвешиваний?

Какую ошибку допустил в своих рассуждениях месье Бертран?

ЗАДАЧА 9

Имеются чашечные весы и некоторое количество одинаковых с виду монет, одна из которых отличается по весу от остальных. При каком наиболь­шем возможном количестве рассматриваемых монет отличную по весу от других монету можно найти не бо­лее чем за четыре взвешивания?

ЗАДАЧА 10

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

ЗАДАЧА 11

После всех этих подготовительных операций мы можем попытаться решить интересующую нас задачу в общем виде.

Имеется х_п монет одинакового внешнего вида, одна из которых отличается по весу от остальных. Далее, как и в задаче 7, одна из «дополнительных» монет, одинаковых по весу с х_п—1 «стандартными» монетами, слегка поцарапана.

Чему должно равняться х_п, чтобы

можно было обнаружить отличную по весу монету

среди наших х_п монет не более чем за п взвешиваний и при этом нельзя было бы ее обнаружить среди

Хп + 1 монет не более чем за п взвешиваний, т. е. в некоторых случаях определить искомую монету из х_п + 1 «подозрительных» монет можно было бы лишь с помощью (п + 1)-го взвешивания?

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

ЗАДАЧА 12

Имеется у_п одинаковых с виду монет, одна из которых отлична по весу от остальных. Кроме того, имеется еще одна, заведомо нормальная по весу монета, которую мы можем считать поцарапанной (если хотите, считай­те, что мы поцарапали ее нарочно).

Чему должно быть равно у_п, чтобы отличную по весу монету с помощью не более п взвешиваний можно было обнаружить среди у_п монет и нельзя среди у_п + 1 монет? Эта задача в основном совпадает с предыдущей: единственное различие состоит в том, что теперь уже не требуется при первом взвешивании обязательно помещать на весы все «сомнительные» монеты.

Впрочем, в качестве дополнительного условия здесь можно поставить требование определить, легче или тяжелее остальных искомая «особая» монета.

ЗАДАЧА 13

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

За сколько взвешиваний можно отыскать эту монету и определить, легче она или тяжелее остальных? Отличие этой задачи от предыдущих заключается в том, что теперь в нашем распоряжении нет заве­домо стандартной (помеченной или поцарапанной) монеты.

ЗАДАЧА 14

Имеется п одинаковых по внешнему виду монет, одна из

которых отлична по весу от остальных. За сколько бзвешиваний на чашечных весах без гирь можно обнаружить эту монету?