8
$\begingroup$

Following my previous question: Lots of Gold Stacks and a Balance Scale

You are given 10 stacks, each stack consisting of N golden 10g-coins and a digital scale with perfect precision that shows exact amount of weights you put on.

You know that some stacks may have only 9 gram golden coins and you are supposed to find these stacks with only one try. The only problem here is that you do not know how many stacks and which stacks have lighter ones and you have only one chance to weigh on a digital scale.

So you have only 1 try on the digital scale, what should the minimum amount of golden coins be for each stack that guarantee to find the lighter stacks?

Note: You can take/put back any amount of coins from/to any stack.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

You are looking for 10 numbers such that no two subsets of the numbers sum to the same amount, such that the largest number is minimal. This is conjectured to correspond to sequence A005318 in OEIS, which gives the 10th element as 309. A096858 provides the corresponding amount of coins from each pile as 148, 225, 265, 285, 296, 302, 305, 307, 308, and 309.

The subset sum problem has come up before in this question.

Improve this answer
$\endgroup$
2
  • $\begingroup$ ...and the set works - 1024 distinct sums $\endgroup$
    – Jonathan Allan
    Aug 14, 2016 at 16:35
  • $\begingroup$ +1. I had a feeling my answer would prove to be a little naive. $\endgroup$
    – IanF1
    Aug 14, 2016 at 18:58
10
$\begingroup$

edit: while the algorithm in this answer works, it is not optimal. See f"'s answer for one which provides a lower, and probably optimal, bound.

I think you need

$2^9 = 512$

coins per stack.

Explanation:

To determine in one weighing which stacks comprise 9g coins rather than 10g coins, use 1 coin from the first stack, 2 from the second, then 4, 8, 16 etc from the subsequent stacks. Weigh these and see how far below the expected weight (if all were 10g) the total is. Then express this difference in binary. If the lowest bit is 1 then the first stack is of 9g coins and so on.

The total number of coins weighed is

1023 (512+256+...+2+1)

so the expected total weight is

10230g.

So if for example the scales measured these as

9717g,

Then

the missing weight is 513g = 512 + 1

So the underweight stacks are

the first and 10th stacks.

By extension, the number of coins per stack required to detect cheating in M stacks is

$2^{M-1}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks to whoever edited in the spoiler tags, i was in a rush. $\endgroup$
    – IanF1
    Aug 14, 2016 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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