Gold puzzle

[Ghost Post]

I have not looked at anyone elses solutions. This is one I believe to be correct.

1/Take 1 bar from vault 0, 2 from vault 1, 4 from vault 2, etc (yes number the vaults starting with 0 rather than 1, it doesn't make any difference to the solution, just easier to work with)

2/Add the number of bars together and multiply this by 10.

3/Weigh all the bars together

4/Calculate the difference between the previous multiplication and the weighed value
call this number xa

5/subtract the highest power of 2 less than or equal to xa from xa. Call this number xb.

6/repeat step 5 until there is nothing left, recording the powers every time

7/the powers are the numbers of the vaults.

eg:
7 vaults,
you take 1 bar from vault 0, 2 from vault 1, etc giving you 127 bars for 7 vaults

127*10=1270

say you find the weight to be 1263, ie 27 missing kilos. Do 27 = 16+8+2+1 so the vaults tampered with were vaults 0,1,3 and 4.

This works becuase any value has to have a unique combination of powers of 2 that sum to that value (this work because we are doubling the number of possible missing kilos with every extra vault).
It is the least number of blocks because using powers of 2 results in the smallest number of blocks you can use and keep unique values which some to any given difference.

[QuikSand]

M, it might be time to look at the other solutions. I believe you'll find satisfactory answers that use fewer bricks than your does. The difference lies in the fact that you are not using the fact that we know exactly how many vaults have fake bricks (3). When one takes into account this fact, it's possible to reach a more economical solution. (Yours is a solution which would generate a unique answer for any number of fake vaults, which is not necessary in this problem)


Check the long thread...

[This message has been edited by QuikSand (edited 03-08-2001).]