9
$\begingroup$

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

$\endgroup$

5 Answers 5

7
$\begingroup$

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\}$

$\endgroup$
2
  • 2
    $\begingroup$ Good find. On the other hand, $K>220$ by A201052 $\endgroup$ Commented Sep 20, 2023 at 6:31
  • 1
    $\begingroup$ Can you explain why this works and how this sequence is related to the problem. I will believe that this solution works but so far this is only a collection of 10 numbers and not a solution. $\endgroup$
    – quarague
    Commented Sep 26, 2023 at 17:14
5
$\begingroup$

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.

Summary

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ While $2^n$ may seem intuitive, it's not optimal, and 512 isn't the minimum. $\endgroup$
    – Pumbaa
    Commented Sep 18, 2023 at 12:43
  • $\begingroup$ @Pumbaa I'm looking forward to seeing better solutions. I don't see how. $\endgroup$
    – quarague
    Commented Sep 18, 2023 at 18:38
  • 1
    $\begingroup$ E.g. in a simplified 4-box scenario, 3, 5, 6, 7 is better than 1, 2, 4, 8. $\endgroup$
    – Pumbaa
    Commented Sep 19, 2023 at 9:30
  • 1
    $\begingroup$ I am giving this an upvote because it is the only one to describe the weighing explicitly - that you take a different number of pearls from each box and distinguish them somehow. The other answers all assume you know that and talk person-who-knows to person-who-knows, which happens pretty often when the mathematical notation comes out, and works against the joy of understanding puzzles in my opinion $\endgroup$ Commented Sep 26, 2023 at 15:44
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Well done. This seems to use a 2:8 partition where I cowardly use 5:5, and you invested more work to keep the "offset" for the big ones small $\endgroup$ Commented Sep 20, 2023 at 6:14
1
$\begingroup$

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

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.