Subscribe via feed.

Posted by Karl Sharman on May 13, 2011 – 11:01 am

Whilst I was away under the pretense of work, a nearby bank uncovered a plot to swap the gold in their vaults with counterfeits. It was determined that all the gold bars in three of the Bank’s seven vaults were replaced with counterfeits. The other four vaults were uncompromised. The plot was foiled through the poor math skills of the thieves: while the real gold bars weigh ten kilograms, the counterfeits all weighed nine kilograms.

I was asked to work out which was the real gold, and which was the fake. I, being really bad at maths, so Chris tells me decided to recruit your help.

Your mission, should you wish to accept it, is determining which vaults have real gold, and which are just gold-plated bars of platinum.

The Bank Director has made the following generous offer: If you can determine the counterfeits using just one weighing on a scale, you can keep one bar as a souvenir.

Here are the rules:
This is a scale, not a balance, but you can weigh as many bars together as you like.
Only one weighing!
The bars will be handled by professional guards, so you won’t have a chance to “feel” their weights.
Each vault contains several hundred bars.
The guards have requested that you try to keep the number of bars you need to a minimum.

How do you do it, and what is the minimum number of bars…?

Good luck!

Tags:
This post is under “Tom” and has 26 respond so far.

### 26 Responds so far- Add one»

1. 1. Krazeedude Said：

I don’t know about you but “which vaults have real gold, and which are just gold-plated bars of platinum.”, I think I’d keep the bars of platinum!

2. 2. Wizard of Oz Said：

Chris has put up similar problems to this one in the past.

I got them right 40% of the time. I know the trick by now so I’ll pass on this one and let someone else work it out.

3. 3. forsythe303 Said：

Sorry to interject a solution to an unstated problem which arises, I am sure, as a result of an unintentional oversight… But since I don’t know how to weigh them and get to the intended mathematical concept and since I have an insatiable need to see my name on this site once again…

I’d save the guards backs completely and make a deal with the Bank Director to solve the case without weighing them, removing the bars from their vaults or even touching them. You see, size for size platinum weighs approximately twice that of gold. So if the weight of the fake bars is only 9 kilograms as stated, then looking for bars which are a little less than half the size of others, we can safely pronounce them to be the fakes.

4. 4. Chris Said：

Hi forsythe303. A quick Google search revealed that the density of platinum is 21.45 gm/cm³ and gold is 19.3 gm/cm³. They’re too close to easily distinguish by inspection.

Wiz knows the method (unless he’s gone all binary again )

That’s got your name in lights again

5. 5. Wizard of Oz Said：

Specific gravity of gold is 19.3, platinum is 21.4. Way short of double. The bars would be close enough in size to make the differences hard to detect by just eyeballing them.

Forsythe303 has got his name on this site under false pretences. Still, everyone’s welcome here.

I believe platinum’s worth more, even at 9kg to 10kg of gold. So I agree with Krazeedude: shut up and keep the platinum.

So I’d fake the results of the weighings to get myself a free bar of platinum.

6. 6. Karys Said：

I think the answer is something like this :
Take different numbers of bars from each vault and, knowing how much a real gold bar weighs as compared to the counterfeits, immediately deduce from the difference between the expected weight (i.e. if all bars were real gold) and the measurement.

All that’s left is determine the numbers of bars to take from each vault, so that we have taken the least possible.

7. 7. Wizard of Oz Said：

That’s getting close, Karys. Now, how may bars from each vault?

How many different outcomes from vaults 1 to 7 do you need to be able to distinguish?

8. 8. SP Said：

Take 1 from 1, 2 from 2, 4 from 3, 8 from 4, 16 from 5, and 32 from 6. (None from 7.)

63 bars. Take the weight and then subtract what it would be if all were fake: 567. With that new number, convert to binary to tell you which vaults have the gold (rightmost digit representing vault 1). Since 4/7 vaults have gold you’ll then also know if #7 does or not.

9. 9. Karl Sharman Said：

SP shoots – he scores…. but disallowed by the referee. It can be done with less bars.

For those concerned about the platinum bars – this is a red herring – how do you think the less than bright criminals got caught?

Based on a quick google search on todays prices – 10kg bar of gold – \$20k, 9kg bar of Platinum – \$21k – or thereabouts (I think – probably wrong though – precious metals appear to be weighed in troy ounces, not kilo’s)

10. 10. Wizard of Oz Said：

Hi Karl,

You’ve got me thinking on this one. I had originally thought that SP’s binary approach was the way to go. I can see that there could be a more “efficient” solution, i.e. one requiring fewer bars but at the moment I can’t yet see what that would be.

There are 35 ways that the three “fake” vaults can be distributed across all seven vaults. SP’s binary approach allows for 64 possibilities, which is more than is needed.

What is needed is a selection of bars from each vault that can differentiate between 35 different possibilities and which uses (according to you) less than 63 bars.

I had thought that a Fibonacci type series might give the answer (something like 1, 2, 3, 5, 8, 13, 21, making 53 bars) might work, but it doesn’t. A weighing of these bars has to give a different result for each of the 35 possible distributions, and Fibonacci comes close but doesn’t quite do it.

That’s as far as I’ve got.

11. 11. Chris Said：

Hi Wiz, you have gone all binary again, LOL. Yes that method works, but it can be done with much less than 63 bars. You also have previously come up with a method that used cubic numbers (if my memory is correct).

Congrats Karl. I never thought this problem would have lasted so long. It must appear about once a year. However, I’m not sure if SP’s observation that you don’t need to sample vault 7 has been made before.

12. 12. Karl Sharman Said：

Chris – if as Wiz says in the Which Way? thread 0 is an integer, then you can use it as a number of bars for sampling a vault – no 7 being the one that you would use traditionally the largest number of bars from.
That didn’t appear to make sense, but publish and be damned…

13. 13. tringyokel Said：

Keeping the zero for vault 7 then the set
[ 1, 2, 4, 8, 14, 26, 0 ] uses 55 bars

Nowhere near knowing how close this is to minimal. Using these weightings I get 35 different total weights but over a range of 45 so I expect it can be beaten.

14. 14. cazayoux Said：

Why isn’t Wiz’s Fib series a winner?
While the sum may not be unique (3 versus 2 + 1), the count of assaulted vaults gives us the rest of the information, doesn’t it.

For example.
I take 21 bars from V1, 13-8-5-3-2-1 from V2-3-4-5-6-7

I weigh the 53 bars and get 504 kg, a delta of 26 from the 530 (if all bars are 10kg).

The delta is larger than 21 (bars taken from V1), so I know vault one does not hold gold.
Remaining delta to account for is 5 bars.
We took 5 bars from V4, but if this vault held fake gold, there would only be 2 vaults targeted. (we are looking for 3 vaults.)

So vault 4 is real gold and we move on.
We find that V5 (3 bars) and V6 (2 bars) hold fake gold.

I don’t yet see a solution for less than 53 bars… not sure I will.

Cheers!

15. 15. Chris Said：

Hi Karl. I’ve actually read the question now. I’d incorrectly assumed that this was the standard question. I’m not sure what you comment meant, but as we know that 3 vaults were affected, we can ignore one of the vaults. I’d ignore 7 as I rather use 1-6 than 2-7 for referencing.

16. 16. tringyokel Said：

cazayoux – When you get the delta of 26 why do you say that vault one must contain fakes?

V1 + V5 + V6 does give 21 + 3 + 2 = 26
but so does
V2 + V3 + V4, ie 13 + 8 + 5 = 26

Am I missing some way to tell these two apart?

But Fibonacci is close, isn’t it. For what it’s worth I spent some time thinking the answer might be related to markings on Golomb rulers but got nowhere with that.

17. 17. Wizard of Oz Said：

This exercise comes down to the general question of finding the smallest set of n integers such that all subsets of m integers have different sums. The binary series 0 to 2^(n-2) meets the condition, however this is not the smallest set. The minimum size of this set would be nCm, i.e. n!/m!(n-m)!. There’s sure to be a branch of mathematics that deal with such momentous issues. No doubt Slavy can fill us in on this.

In our case n = 7 and m = 3 and the smallest theoretical size of the set is 7C3 = 35. The set of binary numbers 0 to 31 gives us 63, however tringyokel in post 13 above has got this down to 55. How did you do it, yokel, and how long did it take you?

Subsets of Fibonacci numbers don’t quite do it as there are duplicate sums of the subsets. So, is 55 the smallest, and are there sure-fire rules for finding the smallest?

Now I’m off to find my way out of the woods with truthful Chris and lying Wiz to guide me . . .

18. 18. tringyokel Said：

Wizard, I would love to show you my elegant algorithm but this reply box is too small to contain it. Actually, I used brute force.

I set up a small spreadsheet to calculate the sum of each of the possible 35 sets and put in a bit of conditional formatting to colour cells red when two sums are equal. Very primitive.

Playing like this often gives me an insight into finding an algorithm, or a proof that an answer is minimal, but not this time I’m afraid. I don’t suppose it would take very long to check all possible combinations but I’d prefer a different way. I spent about half an hour trying the most likely combinations (starting 0,1,2 : 0,1,3 : 0,2,3 : 1,2,3 etc). It doesn’t take long for the total number of bars to exceed 55in most of these cases.

19. 19. Chris Said：

Hi tringyokel, the box is a large as you need. The thumb scroller will turn on when there is enough text to require it.

I could eaily have messed up, but I’ve got 1,2,3,6,11,20. A total of 43 sample bars. I haven’t fully checked it yet, so don’t be surprised if I revise those numbers (LOL, I’ve already changed it 3 times since posting). I haven’t come up with a really neat explanation of how I found them. I did use a fairly methodical strategy (or two) to get there. Note, no sample taken from vault 7.

Wiz you are right in thinking that Fibonacci is buried in there somewhere. My current favourite set is 1,2,3,6,11,20 which I found after multiple incremental amendments using a trial and error strategy, is a variation of the Fibonacci series based on summing the previous three (rather than two) numbers (using 0,1,2 as the seed).

If I’ve not goofed, then no two pairs add up to the same sum, no two triples add up to the same sum, and no triple has the same sum as any pair.

**** Later: I’ve goofed ****

20. 20. Chris Said：

A set that works, but I suspect can be improved is 1,2,4,7,13,24. It’s oddity is that it can’t produce 4,23,36,40,42,43. That limtation is due to only being able to add a minimum of two and a maximum of three of the numbers.

The number of bars required is 51.

By not including the seventh vault, we might have two or three fake samples. C(6,2)+C(6,3) = 35 as Wiz expected.

The set started 1,2,4 (after realising the problem with my previous best guess) and then the subsequent terms are the sum of the three previous terms.

21. 21. Karl Sharman Said：

Best I’ve got – I’ll post the mechanics of it tommorrow when I get out of the pub where I am being forcibly detained against my will…

22. 22. cazayoux Said：

1,2,3,6,11,20 has ambiguity with the following sums: 9(1:2:6, 3:6), 14 (1:2:11, 3:11), and 23 (1:2:20, 3:20).
I think I’ll keep playing with brute force methods to see what I can find.

Fun!!

23. 23. cazayoux Said：

I kept your thought of a Fib using three previous, but seeded with only 0,1. So the series is …
0,1,1,2,4,7,13,24

ignore the 0,1 that starts it, we have 1,2,4,7,13,24 which totals 51 and gives a unique sum across two or three vaults of false gold.

Sum:coins from vault
3:1,2
5:1,4
6:2,4
7:1,2,4
8:1,7
9:2,7
10:1,2,7
11:4,7
12:1,4,7
13:2,4,7
14:1,13
15:2,13
16:1,2,13
17:4,13
18:1,4,13
19:2,4,13
20:7,13
21:1,7,13
22:2,7,13
24:4,7,13
25:1,24
26:2,24
27:1,2,24
28:4,24
29:1,4,24
30:2,4,24
31:7,24
32:1,7,24
33:2,7,24
35:4,7,24
37:13,24
38:1,13,24
39:2,13,24
41:4,13,24
44:7,13,24

24. 24. Chris Said：

I’m sticking with 1,2,4,7,13,24.

I’ve used three rules to obtain the result.
1. All the numbers must be unique.
2. No three can sum to a sum of two.
3. No three can sum to the sum of another three.

Notes: It is OK if three sum to a single. There is no need to say that no two can sum to the sum of another two (even though it is obviously true).

Starting with 1, the most obvious choice is 2 next (if you try other values, you’ll end up taking more samples than necessary). The next available number is 3. But that’d break rule 2 as x+1+2=x+3. 4 is the next candidate, and it doesn’t break any of the rules. So that’s 1,2,4 so far. 5 is out as x+1+4=x+5. 6 is out as x+2+4=x+6. 7 has no issues. So that’s 1,2,4,7 so far. x+8=x+1+7, x+9=x+2+7, x+10+1=x+7+4, x+11=x+7+4, 12+1 = 7+4+2. 13 has no problem. So 1,2,4,7,13 so far, that’s one more to go. 14+2=13+2+1, 15+1=13+2+1, 16+2+1=13+4+2, 17+2=13+4+2, 18+1=13+4+2, 19+1=17+2+1, 20+1=13+7+1, 21+1=13+7+2, 22+1=13+7+2, 23+1=13+7+4. 24 has no problem. That gives us 1,2,4,7,13,24.

Notice that the series started with the first three powers of 2, then became a Fibonacci like sum over the previous three variables. It’s pretty obvious that isn’t just a coincidence. The biggest triple sum for a give set (so far) is the sum of the highest three terms so far, and so the next number can be equal to that without fear of breaking any of the rules. That leads me to speculate that if we had n dodgy vaults, then we’d start with 1,2,4,8,16,…,2n-1, sum of the previous n, sum of the previous n,… We don’t need a sample from the “last” vault.

e.g. 4 dodgy vaults => 1,2,4,8,15,29,56,108,208,401,…

25. 25. Karl Sharman Said：

You’ll need a total of 51 “gold” bars taken from the seven vaults as follows:

1 bar from the first vault,
2 bars from the second vault,
4 bars from the third vault,
7 bars from fourth vault,
13 bars from the fifth vault,
24 bars from the sixth vault,
0 bars from seventh vault.

51 gold bars should weight 510 kilograms, but they’ll inevitably weigh less than that, because three vaults contain counterfeits. Depending on which vaults contained fakes, you’ll see different deficits. For example, the heaviest the scale could read would be 507. And if it did, it’s light 3 pounds. The only combination that could yield that amount is 0 + 1 + 2, or the first, second and seventh vaults.

Below are all the possible vault permutations, proving that each combination is unique:

3 = 0 + 1 + 2
5 = 0 + 1 + 4
6 = 0 + 2 + 4
7 = 1 + 2 + 4
8 = 0 + 1 + 7
9 = 0 + 2 + 7
10 = 1 + 2 + 7
11 = 0 + 4 + 7
12 = 1 + 4 + 7
13 = 2 + 4 + 7
14 = 0 + 1 + 13
15 = 0 + 2 + 13
16 = 1 + 2 + 13
17 = 0 + 4 + 13
18 = 1 + 4 + 13
19 = 2 + 4 + 13
20 = 0 + 7 + 13
21 = 1 + 7 + 13
22 = 2 + 7 + 13
24 = 4 + 7 + 13
25 = 0 + 1 + 24
26 = 0 + 2 + 24
27 = 1 + 2 + 24
28 = 0 + 4 + 24
29 = 1 + 4 + 24
30 = 2 + 4 + 24
31 = 0 + 7 + 24
32 = 1 + 7 + 24
33 = 2 + 7 + 24
35 = 4 + 7 + 24
37 = 0 + 13 + 24
38 = 1 + 13 + 24
39 = 2 + 13 + 24
41 = 4 + 13 + 24
44 = 7 + 13 + 24

26. 26. Chris Said：

Hi Karl. Good problem. Thanks for posting it. I just wish that I could prove that the binary/Fibonacci trick is always the best that can be done; no matter how many vaults or dodgy goods are specified.

I also learnt that platinum is denser that gold – I didn’t know that before. They’re beaten by Osmium (22.4 gm/cm³) and Iridium (22.5 gm/cm³).

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0