|
|
 |
Условие
Известно, что среди нескольких купюр, номиналы которых – попарно различные натуральные числа, есть ровно $N$ фальшивых. Детектор за одну проверку определяет сумму номиналов всех настоящих купюр, входящих в выбранный нами набор. Докажите, что за $N$ проверок можно найти все фальшивые купюры, если а) $N = 2$; б) $N = 3$.Решение
Можно считать, что детектор выдаёт сумму номиналов фальшивых купюр в проверяемом наборе. Первая проверка – весь набор – даст сумму $S$ номиналов всех фальшивых.а) Вторая проверка – все купюры, меньшие $\frac{S}{2}$, – даст число $X$. В этом наборе ровно одна фальшивая, поэтому купюры с номиналами $X$ и $S - X$ фальшивые.
Замечание. Во вторую проверку можно было взять по купюре из каждой пары с суммой $S$.
б) Назовём купюры и числа, меньшие $\frac{S}{3}$, мелкими, а остальные – крупными.
Вторая проверка – все мелкие купюры – даст число $M$. Теперь известна и сумма номиналов $K = S - M$ крупных фальшивых купюр. Заметим, что фальшивые есть и среди мелких, и среди крупных купюр. Поэтому возможны два вида троек фальшивых купюр: $(M_1, M_2, K)$, где числа $M_1$ и $M_2$ мелкие с суммой $M$, и $(M, K_1, K_2)$, где $K_1$ и $K_2$ крупные с суммой $K$, а $M$ мелкое.
Третья проверка – все купюры, меньшие $\frac{M}{2}$, и все крупные, меньшие $\frac{K}{2}$, – даст число $X$. Видно, что в этом наборе ровно одна фальшивая купюра. Поэтому, если число $X$ мелкое, то тройка фальшивых – это $(X, M - X, K)$, а если крупное, то $(M, X, K - X)$.
Замечание. Во вторую проверку можно взять наименьшую купюру от каждой тройки с суммой $S$. В третью проверку можно взять по одной купюре из каждой пары мелких с суммой $M$ и из каждой пары крупных с суммой $K$.
Вариация решения пункта б).
Первая проверка – все купюры. После неё мы узнаем сумму номиналов всех настоящих купюр, а значит, и сумму номиналов всех фальшивых. Обозначим эту сумму через $S_1$. Построим таблицу, в которой три столбца, а в строках записаны в порядке возрастания все возможные тройки чисел, равные номиналам купюр, которые дают в сумме $S_1$.
Вторая проверка – все купюры, номиналы которых попали в первый столбец таблицы. После этой проверки мы будем знать сумму номиналов некоторых купюр в «фальшивой» тройке. Пусть эта сумма равна $S_2$. В неё точно входит число из первого столбца, так как соответствующая купюра участвовала в проверке. Также в неё может входить число из второго столбца. А вот числа из третьего столбца в ней точно нет, поскольку все числа первого столбца меньше $S_1/3$, а третьего – больше $S_1/3$, поэтому ни одно из чисел третьего столбца не может присутствовать в первом. Удалим из таблицы все строки, в которых ни первое число, ни сумма первого и второго не равны $S_2$.
Третья проверка – все купюры, номиналы которых находятся во втором столбце оставшейся таблицы. Заметим, что в каждой строке либо первое число равно $S_2$ и тогда второе число больше $S_2$, либо сумма первого и второго числа равна $S_2$ и тогда первое число меньше $S_2/2$, а второе – больше $S_2/2$, но меньше $S_2$. Значит, никакое число из первого столбца не может стоять во втором столбце. Кроме того, из этого следует, что все числа во втором столбце различны, иначе соответствующие тройки полностью совпадали бы.
Докажем, что и числа из третьего столбца не могли попасть во второй столбец. Предположим, что это не так, и в тройках $(a_1, a_2, a_3)$ и $(b_1, b_2, b_3)$ совпадают числа $a_3$ и $b_2$. Тогда $a_1 < a_2 < a_3 = b_2 < b_3$, а так как $a_1 + a_2 + a_3 = b_1 + b_2 + b_3 = S_1$, то $b_1 < a_1 < b_1 + b_2$ и $a_1 + a_2 > b_1 + b_2 > b_1$. Это противоречит тому, что в обеих тройках есть числа с суммой $S_2$.
Таким образом, результатом третьей проверки является номинал второй купюры в «фальшивой» тройке. А так как мы уже доказали, что во втором столбце нет равных чисел, то мы однозначно определим эту тройку.
