Решение. Весы и 13 монет (#132)

13 монет дают нам 13 х 2 = 26 исходов (так как фальшивка может быть лёгкой или тяжёлой). У любого взвешивания может быть три исхода (<, >, =), поэтому в лучшем случае после каждого взвешивания количество вариантов для поиска сокращается в три раза (но не обязательно ровно в три). Таким образом, необходимо, чтобы количество взвешиваний было не меньше [log_3 26] = 3, где [] обозначают округление до ближайшего целого числа вверх.

Покажем, что тем не менее трёх взвешиваний недостаточно:

– Пусть сначала кладём по 4 монеты на каждую чашу. Если =, то фальшивка среди оставшихся 5 монет. То есть у нас есть 5 х 2 = 10 возможных исходов, которые не получится различить за 2 оставшихся взвешивания, так как 3² = 9 < 10 (или [log_3 10] = 3).

– Если положить на чаши по 5 монет, то при неравенстве (<, >) фальшивка будет среди этих 10 монет. То есть мы опять имеем 10 исходов на оставшиеся 2 взвешивания, что недостаточно.

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

Замечание. Если вам непонятно, откуда в этой задаче взялись логарифмы по основанию 3, то рекомендуем почитать этот разбор к аналогичной задаче про 12 монет.

Условие
Telegram