It is known that among several banknotes of pairwise distinct face values (which are positive integers) there are exactly $N{}$ fakes. In a single test, a detector determines the sum of the face values of all real banknotes in an arbitrary set we have selected. Prove that by using the detector $N{}$ times, all fake banknotes can be identified, if a) $N=2$ and b) $N=3$. Proposed by S. Tokarev
Problem
Source: 44th International Tournament of Towns, Junior A-Level P7 & Senior A-Level P6, Fall 2022 & Kvant Magazine No. 11-12 2022
Tags: combinatorics, Tournament of Towns, Kvant
IAmTheHazard
16.02.2023 18:31
The detector equivalently tells us the sum of face values of all fake banknotes. For $N=2$, first select every banknote, which tells us that the sum of the two fake banknotes is $S$. Then consider every pair of banknotes whose values sum to $S$, say $(x_1,y_1),\ldots,(x_k,y_k)$. Clearly these pairs are pairwise disjoint, else two banknotes have the same value. For the second use of the detector, select $x_1,\ldots,x_k$, whence we learn which $x_i$ banknote is fake, and thus which $y_i$ banknote is fake as well.
Anzoteh
24.02.2023 00:36
Adding to the post above for part (b).
Like the previous part, for each query we can deduce the sum of values of counterfeit banknotes in our chosen set by subtracting the total values among our set by the answer returned by the detector (oracle).
Query 1: select all banknotes, let the sum of of counterfeit banknotes be $S$.
Query 2: select banknotes with values $v$ with $\frac{S}{3} < v < S$; let $M$ be the set. Note that there are either 1 or 2 fake banknotes in this range. Let the sum of counterfeit banknotes in this set be $T$, so $\frac{S}{3} <S<T$.
Case 1: $T \le \frac{2S}{3}$. This means we have one banknote in $M$ which we know its value, $T$. Among the rest, one has value $< \frac{S - T}{2}$ and one has value $> \frac{S-T}{2}$, so Query 3 can just be the set of those with value $< \frac{S - T}{2}$. If $W$ is the answer returned, the answer is now $(W, S-T-W, T)$.
Case 2: $T > \frac{2S}{3}$. Let $U=[0, \frac{S-T}{2})$ and $V=(\frac{S}{3}, \frac{T}{2})$.
Claim: there's exactly one fake banknote in $U\cup V$.
Subcase 2a: $M$ still consists of a single counterfeit note, this note has value $T$ (hence $V$ has no counterfeits), and the other two has values $< \frac{S - T}{2}$ and $> \frac{S - T}{2}$ respectively (hence $U$ has exactly one counterfeit).
Subcase 2b: $M$ still consists of two counterfeits with sum $T$, i.e. one with $>\frac T2$ and one with $< \frac T2$, meaning $V$ has one counterfeit. Now the third one has value $S-T$ hence not in $U$.
Therefore we can let Query 3 be $U\cup V$. Let return value be $W$. If $W < \frac S3$, it has to be subcase 2a, and we know the answer is now $(W, S-T-W, T)$. If $T > \frac S3$, it has to be subcase 2b and the answer is now $(S-T, W, T-W)$.