Ответ на задачу 49

Июль 4, 2009

49.1.    Если длина одного плеча равна 1, а другого А, то при взвешивании на одной чашке покупатель’получает А кг, а чгри взвешивании на другой 1/Акг. Но по известной школьной теореме о среднем А+1/А>2, причем равенство имеет место лишь при А=1. Значит, как ни странно, в выигрыше остается покупатель.

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

49.3.    Занумеруем наши монеты числами от  1  до 12

Алгоритм (ветвящийся) следующий:

1-е взвешивание. Кладем на чаши наборы   1, 2, 3, 4 и  5, 6, 7, 8.

Возможны два случая:

1-й случай. Весы в равновесии.

Это значит, что фальшивая среди оставшихся с 9 до 12 монет. Этот случай достаточно прост.

Сравниваем монеты 9 и 10 с 1 и 2. Если равновесие, фальшивая одна из двух – 11 и 12.

За одно взвешивание она легко находиться. Если равновесия нет, то ещё проще. Фальшивая – одна из 9 и 10, причем известно даже, легче она или тяжелее настоящей.

2-й случай (основной).

Чаша А легче. Фальшивая среди взвешиваемых.

2-е взвешивание. Кладем на чаши наборы 9, 10, 11, 4 и 1, 2, 3, 8. Возможны три случая.

1-й. Чаша А по прежнему легче. Тогда фальшивая одна из двух монет: 4 или 8 (их положение не менялось). И достаточно 1-го взвешивания для её обнаружения.

2-й. Весы уравновесились. Фальшивая одна из монет 5, 6, 7, причем она тяжелее настоящей. Остальное понятно.

3-й случай. Легче стала чаша Б. Фальшивая одна из монет 1, 2, 3, и она легче.

49.4. Обозначим массы булыжников А, Б, В, Г и Д..

Первые два взвешивания сделаем следующие: сравниваем А и Б, затем В и Г. Можно считать, что обозначения таковы, что А<В, В<Г.

Третье взвешивание — сравниваем Б и Г. Поскольку обе возможности равноправны, то будем считать, что Б<Г. Итак, после трех взвешиваний мы знаем, что А<Б<Г и В<Г.

Четвертое взвешивание. Сравниваем Д и Б. Возникает два случая:

а)         Б<Д. Без учета В булыжники А, Б, Г и Д распо

лагаются в порядке возрастания или АБГД или АБДГ.

А про В мы знаем лишь, что В<Г.

Пятым взвешиванием сравниваем В и Б. Если В<Б, то шестым и седьмым взвешиванием сравниваем А с В и Г с Д. Если же В>Б, то шестым взвешиванием сравниваем В с Д, а седьмым (если потребуется) Г с Д.

б)         Б>Д. Возможны случаи АДБГ и ДАБГ и В<Г.

Здесь сравниваем В и Д. Если В>Д, то шестым и седь

мым взвешиванием сравниваем В и Б, А и Д. Если же

В<Д, то сравниваем А и Д, затем В и А.

Комметирование закрыто now!