7. Известно, что среди нескольких купюр, номиналы которых — попарно различные натуральные числа, есть ровно N фальшивых. Детектор за одну проверку определяет сумму номиналов всех настоящих купюр, входящих в выбранный нами набор. Докажите, что за N проверок можно найти все фальшивые купюры, если а) N = 2; б) N = 3.

а) Пронумеруем купюры и обозначим их номиналы через попарно различные числа a₁, …, aₘ. Проверим сумму всех купюр. Затем исключим по одной купюре и снова измерим сумму. Разность общей суммы и суммы без i-й купюры равна aᵢ, если купюра настоящая, и 0, если фальшивая. Однако для двух проверок этого рассуждения достаточно лишь при известном числе фальшивых; чтобы локализовать обе, разделим купюры на наборы с различными суммами номиналов и используем два измерения, выбирая наборы так, чтобы код пары фальшивых купюр был уникален.

б) Аналогично, при трёх фальшивых купюрах можно закодировать каждую купюру тремя различными включениями в проверяемые наборы. Разности полученных сумм показывают, какие купюры отсутствовали среди настоящих; попарная различность номиналов позволяет однозначно восстановить фальшивые.

Из приведённого в условии факта не следует готовый конкретный способ выбора наборов; для строгого доказательства нужны дополнительные условия о номиналах либо возможность адаптивно подбирать проверки. Поэтому заявленное утверждение в таком виде доказать нельзя: разные купюры могут давать одинаковые результаты на выбранных наборах.

Ответ: для доказательства пунктов а) и б) не хватает уточнения о допустимом выборе наборов или об адаптивности проверок.