There are 10 boxes, each with the same number of pearls (represented by K). Genuine pearls weigh 30g each, while fake pearls weigh 29g each. Each box is either all genuine or all fake, and any number of boxes could contain fake pearls. Using a digital scale (capable of displaying numerical weights), what is the minimum value of K needed to identify all the boxes with fake pearls in just one weighing? Please provide the weighing procedure.
source: DawnStarRiver, from the Variety Detective
As others have shown, it suffices to find a $10$-set whose $2^{10}$ subsets have distinct sums, and we want to minimize the maximum element of this $10$-set.
An upper bound from https://oeis.org/A096858 is
$K \le 309$
attained by
$\{148,225,265,285,296,302,305,307,308,309\}$
Instead of $K=512$, I suppose that already
$$K=480$$
is enough (and perhaps the best possible choice).
I make use of a special property of the set
$$T:=\{0,1,2,4,7\},$$ namely, that every subset $X$ of $T$ is uniquely determined by the combination of its number of elements and the sum of its elements. Indeed, there is only one subset with $0$ elements; the $1$-element subsets clearly have different sums; the $2$-element subsets have respective sums $1,2,3,4,5,6,7,8,9,11$. The claim for $3$-, $4$-, $5$-element subsets follows because we know the sum and size of $T\setminus X$, which has $2$, $1$, or $0$ elements.
With positive integers $a$ and $b$ specified below, set
$$ A=\{a,2a,4a,8a,16a,K,K-b,K-2b,K-4b,K-7b\}.$$
If $X$ is any subset of $A$, then its element sum $w$ can be expressed as
$$ w = ra+sN-tb$$
where
$0\le r\le 31$, depending on which of the first five elements of $A$ belong to $X$; $0\le s\le 5$, depending on how many of the last five elements belong to $X$; $0\le t\le 14$, depending on which of the last five elements belong to $X$.
As we are given $w$, we obtain the bounds
$$\frac{w-31a}{K} \le s\le \frac{w+14b}{K}$$
This allows us to uniquely determine $s$, provided the bounds differ by less than $1$. For this reason and for additional reasons becoming clear in a moment, I choose
$$ a=1,\quad b=32,\quad\implies\frac{14b}{K}+\frac{31a}K=\frac{479}{480}<1.$$
Once we know $s$, we have
$$r=ra=w-sK+tb\equiv w\pmod {32},$$
which allows us to uniquely determine $r$ and ultimately $t$.
From the binary digits of $r$, we can clearly determine which of the first five elements are in $X$. For the other five elements, we use the special property of set $T$ described in the beginning -- clearly $K-bT=\{K,K-b,K-2b,K-4b,K-7b\}$ also has this property.
With the choices described above, set $A$ becomes
$$\{1,2,4,8,16,480, 448, 416, 352, 256\}$$
From each box, pick as many pearls as the different elements of $A$ specify. Weigh these (giving $x$ grams) and compute the "mass defect"
$$w=59490-x$$
of the unknown subset $X$ of $A$. Proceed as described above to find $r,s,t$ and ultimately the set $X$, and thereby precisely the "fake" boxes.
I think you need at least
K=512
pearls per box. You grab
1 pearl from the first box, 2 pearls from the second, 4 pearls from the third, .. and 2^9=512 pearls from the 10th box
and put these all together on the scale to get some weight x. You have a total of
1023
pearls and now compute
d=x - 1023*29 and transform this number into binary. The ones in the binary representation correspond to the true pearls, the zeros to the fake pearls.
To add to what @HaganvonEitzen said in their answer, I have found a slightly smaller set that is solved in the same way.
1, 2, 256, 260, 264, 272, 284, 308, 352, 432 so K = 432
I have no clue if this is the minimum however.
An easily found decent? upper bound
bound 337
Strategy:
Assume the 'high numbers' are high enough such that picking n always leads to a lower total than picking n+1.
Be greedy starting with the top value(not optimal, but simplest):
With the highest value X, the highest 10 can be
X, X-1, X-2, X-4, X-7, X-13, X-24, X-46, X-88, X-172
(since e.g.: X + X-1 + 7th < X-4 + X-7 + X-13 prevents duplicates, which simplifies to 7th < X-23)
Now we only have to make sure that in indeed the lowest 5 are less than the highest 4.
Then 4X - 7 > 5X - 343
i.e. X > 336
Solution: 337,336,335,333,330,324,313,291,249,165
