Найти n как на чашечных весах

2019-04-29   

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

б) Известно, что среди $n$ монет есть одна фальшивая, более легкая, чем остальные, имеющие все одинаковый вес. Каково наименьшее число $k$ такое, что $k$ взвешиваниями на чашечных весах без гирь всегда можно выделить фальшивую монету?

Решение:

а) Разделим наши монеты на три группы: две группы по 27 монет и одну в 26 монет. При первом взвешивании поместим на чашки весов группы по 27 монет. Если весы не уравновесятся, то фальшивая монета находится на более «легкой» чашке. Если же весы окажутся в равновесии, то фальшивая монета содержится в группе из 26 монет. Таким образом, нам достаточно научиться решать задачу: тремя взвешиваниями выделить фальшивую монету из группы в 27 монет (задача выделить фальшивую монету из группы в 26 монет может быть сведена к этой задаче, например, добавлением к группе из 26 монет еще одной произвольной монеты из числа остальных 54).

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

Разделив группу из 9 монет, одна из которых фальшивая, на три группы по 3 монеты, мы третьим взвешиванием выделим тройку монет, в которой содержится фальшивая.

Наконец, тем же путем при четвертом взвешивании найдем фальшивую монету.

б) Пусть $k$ – натуральное число, удовлетворяющее неравенствам $3^{k-1} < n leq 3^k$. Покажем, что это число $k$ удовлетворяет условиям задачи.

Прежде всего покажем, что при помощи $k$ взвешиваний всегда можно определить фальшивую монету. Разделим наши монеты на три группы так, чтобы в двух равных группах было по $3^{k-1}$ (или меньше) монет, а число монет в третьей группе было бы не больше $3^{k-1}$ (это возможно, ибо $n leq 3^k$). Положив на чашки весов две группы из равного числа монет, мы определим, в какой из трех групп содержится фальшивая монета (ср. с решением задачи а)). Таким образом, после первого взвешивания мы выделим группу из $3^{k-1}$ монет, среди которых содержится фальшивая- (если окажется, что фальшивая монета находится в группе, содержащей меньше $3^{k-1}$ монет, то мы можем дополнить эту группу монет произвольными монетами до $3^{k-1}$). При каждом последующем взвешивании будем делить наши монеты на три равные группы и определять, в какой из них находится монета. Таким образом, после $k$ взвешиваний мы придем к группе из одной монеты, т. е. выделим фальшивую монету.

Теперь остается показать, что $k$ есть минимальное число взвешиваний, с помощью которых всегда можно выделить фальшивую монету, т. е. что при любых способах взвешивания результаты взвешиваний могут сложиться таким неблагоприятным для нас образом, что после $k – 1$ взвешиваний фальшивая монета не будет выделена.

При каждом взвешивании монеты распадаются на три группы: монеты, попавшие на одну чашку, попавшие на другую чашку и не попавшие ни на одну из чашек. Если на чашки весов было положено одинаковое число монет и весы уравновесились, то фальшивая монета заведомо находится в группе монет, не попавших при взвешивании ни на одну чашку. Если одна из чашек перетянет (при равном числе монет на чашках), то фальшивая монета находится на второй чашке. Наконец, если на чашки весов было положено разное число монет, то в случае, когда перетянула чашка, где монет больше, фальшивая монета может оказаться в любой из трех групп и такое взвешивание вообще не даст нам никаких сведений о местонахождении фальшивой монеты. Пусть теперь при произвольно производимых взвешиваниях результат взвешивания каждый раз оказывается наиболее неблагоприятным, т. е. фальшивая монета каждый раз оказывается в той из трех групп, которая содержит наибольшее число монет. Тогда при каждом взвешивании число монет группы, содержащей фальшивую монету, убывает не более чем в 3 раза (ибо при делении некоторого числа монет на три группы всегда по крайней мере одна из трех групп содержит не менее чем треть от общего числа монет); поэтому после $k – 1$ взвешиваний число монет группы, содержащей фальшивую монету, остается не меньшим чем $frac {n}{3^{k-1}}$ и так как $n > 3^{k-1}$, то после $k-1$ взвешиваний фальшивая монета не будет выделена.

Примечание. Можно коротко записать ответ задачи в такой форме: минимальное число взвешиваний, необходимое для выделения фальшивой монеты из группы в $n$ монет, есть $left [ log_{3} left ( n – frac{1}{2} right ) right ] + 1$, где прямые скобки обозначают целую часть числа.

Ответ: а) При первом взвешивании поместите на каждую чашку по 27 монет, б) Число $k$ определяется неравенствами $3^{k-1} < n leq 3^k$.

Как найти фальшивую монету двумя взвешиваниями – логическая задача

Загадки на логику

Похожие новости