# Brain Teaser #90

1. Apr 24, 2004

### Xiox

I got this one at the last class at the end of my course in mathematics last semester...

I have 10 stacks of gold coins with 10 coins in each of them, but one of these stacks of coins is false and therefore the weight is presumed to differ from that of the non-fake ones. How I am supposed to find out which of these stacks is the false one. To my disposal I have an apparatus with which I can weight the stacks, viz. when I lay down a stack on the weight, the opposite weight of it is rising. Note that I have to do it as fast as it is concievably possible, i.e., weight the stacks as less times as I can.

When I say 'weight', I mean that once the certain weight has been weighted, and when that particular weight is either diminished or increased, it is yet another 'weight'.

2. Apr 25, 2004

### arildno

3 weighings:
a) Pick out two sets of 3 stacks in each
a1) Equal weights:
a1b)We know that all 6 stacks were genuine; we pick as set of 3 other stacks, and weigh them against one of the previous sets.
a1b1) Equal weights: The unweighted last stack is fake (2 weighings)
a1b2) Unequal weights: We know that the fake stack is among the last three, and also if it weighs less or more than the genuine ones.
a1b2c)We pick out two stacks from the last set and weigh them against each other.
Since we know whether the fake stack weighs less or more, we can determine which of the three is fake (3 weighings)

a2)Unequal weights:
a2b) We set a side one of the sets weighed, and replace them with a new set of 3 stacks, which we now know to be genuine.
a2b1)Equal weights: We know the fake is among the three stacks set aside, and from the first weighing, we know if the fake is heavier or lighter. We can now proceed as under a1b2c) (3 weighings)
a2b2) Unequal weights, as under a2b1) but with the set retained instead of with the set set aside (3 weighings)

3. Apr 26, 2004

### Xiox

I'm sorry that I wasn't able to respond earlier, my Internet was down, but your answer is incorrect.

Last edited: Apr 26, 2004
4. Apr 26, 2004

### davilla

You can do this in 3 weighings without knowing whether the fake stack is heavier or lighter than the others, for up to 12 stacks. Not only that, but in as many chances, it is possible to determine whether the fake stack is heavier or lighter.

Last edited: Apr 26, 2004
5. Apr 26, 2004

### Xiox

I didn't mean that Arildno's way of weighting the weights was incorrect, you can do it in 3 weightings. But there is a way to do it with less than 3 weightings.

6. Apr 26, 2004

### arildno

Now, that's DEVIOUS, Xiox!
I'll have to think more..

7. Apr 26, 2004

### arildno

I might go to a goldsmith's and have the gold content examined; then I can do it with ZERO weighings!

8. Apr 26, 2004

### Xiox

Actually, I, too, kunde icke reckon it out from the beginning. It is hard because it's so easy... It is not zero weightings though... shall I give you a hint?

*HINT - POSSIBLE SPOILER*

----------
One thing that I have noticed with all of the mathematical problems in all of the books I have ever seen is that there's never more information that is necessery to accomplish the task...

Psh: I speak a little Swedish.

Last edited: Apr 26, 2004
9. Apr 26, 2004

### gnome

I don't understand what this means:
and does
simply mean a balance scale?

10. Apr 26, 2004

### Xiox

And, by the way, I don't quite understand how you, Arildno, managed to do it in 3 weightings, perhaps it is just me, though.

(1) First, you weighted two sets of stacks with 3 in each of them.
(2) Then you weighted 3 other stacks (it is here possible to find the the desired stack).
(3) It is possible to determine that one of the last of the 3 stacks is the false one. So, you weighted 2 stacks of those 3. If they are equal in weight, then the third is the false one. So, you should have 2 stacks by now, but how are you able to say which is gold and which is not without seeing it?

You wrote:

Since the weight will change in thus doing so, it is two weights. And, because of the same reason, (1) is also two weights, so, as I perceive it, you managed to find the fake stack in 5 weightings!

Gnome: yes, it is simply a balance scale

Perceptibly, it would be 'cheating' to place a particular amount of stacks on the balace scale and when push it aside while having some stacks(s) on it left or in a similar way put a stack after stack on the balance scale thus counting it as one single weighting. It is not aloud.

Last edited: Apr 26, 2004
11. Apr 26, 2004

### Xiox

Another hint: I have such a peculiar nature when it comes to mathematics; it is often easier for me to manage some tasks that most of the students in my class regard as arduous, and, on the contrary, I find it quite difficult to solve such tasks that are often percieved as immensely easy by most of the students.

Reason to such a wicked behavior is because I don't often find myself redeeming over my answers, the easy ones, that is. Once it comes to the more difficult ones, I am coerced to think and therefore the chances that I will accomplish a certain task correctly is larger.

Regarding your responses, that would you do in my situation?

12. Apr 26, 2004

### NateTG

*spoiler*

If you have a balance - that's a two armed device, then every weighing gives you three possible results - left right, and balanced. Since you're trying to distinguish between 20 (21 if there might not be any fake coins), you need at least $$\log_3(20)$$ weigings.

Of course, you did not specify whether you wanted to optimize for average time, or for worst case time.

There's also the 'handicap' version - which is to determine the weighings before you start. Depending on how you think, this may make the problem easier.

If you have a scale (something that determines absolute weight), then you can resolve the issue in two weighings -- or one if you know the standard weight of the coins.

For bonus fun, try to deal with 13 coins, where there might be one coin that is lighter or heavier in three weigings.

So here's the spoiler:

I would take a pen and write a number on each of the coins, so that I can refer to them as 0-9. Then I'll jot down all the possible results:

Code (Text):

LLL   RRR
LLB   RRB
LLR   RRL
LBL   RBR
LBB   RBB
LBR   RBL
LRL   RLR
LRB   RLB
LRR   RLL
BLL   BRR
BLB   BRB
BLR   BRL
BBL   BBR
BBB *

The colums represent the alternation when the coin is light or heavy. For example LBR indicates that the left arm of the balance dropped on the first weiging, balanced on the second, and rose on the third.

There are some restrictions on the assignment of coins to positions -- clearly there need to be an equal number of coins on each in each weighing, but, conveniently there is available simplification:
So we can (for example) assign:
Code (Text):

LLB RRB Coin 0
BBL BBR Coin 1
BLL BRR Coin 2
LBB RBB Coin 3
LBL RBR Coin 4
BLB BRB Coin 5
LRB RLB Coin 6
BLR BRL Coin 7
LBR RBL Coin 8
LLL RRR Coin 9

Taking care that the total of L's and R's in each column is even.

Now the weigings are:
Code (Text):

0 3 4 6 8 9 -
0 2 5 9 - 6 7
1 2 4 7 9 - 8

But since they're not balanced, we need to switch some coins. Switching 3,4, and 9 gives the weigings:
Code (Text):

0 6 8 - 3 4 9
0 2 5 - 6 7 9
1 2 7 - 4 8 9

Code (Text):

Heavy Light
LLB   RRB   Coin 0
BBL   BBR   Coin 1
BLL   BRR   Coin 2
RBB   LBB   Coin 3
RBR   LBL   Coin 4
BLB   BRB   Coin 5
LRB   RLB   Coin 6
BLR   BRL   Coin 7
LBR   RBL   Coin 8
RRR   LLL   Coin 9

Note that if the coin that is off is coin 6, then the third weiging can be omitted. This brings the average number of weigings to 2.9 which is closer to the theoretical optimum of 2.72...

Last edited: Apr 26, 2004
13. Apr 26, 2004

### Xiox

Consider the following situation:

I'm quite pissimistic today and feeling bored I'm imagining how it be if I balansed all of those 10 stacks with 10 coins in each of them in a large single stack on my head... All of a sudden I loose balance and all of the 100 coins are soon seen scattered - mixed - on the floor. All of a sudden I realize how that imagination of mine could help me - all of those mixed coins from each stack...

14. Apr 26, 2004

### NateTG

You specified balance, not scale in the original post, and were not particularly clear. If you have a scale you can just take a different number of coins from each stack.

15. Apr 27, 2004

### davilla

I agree with NateTG. With a balance, in two weighings there are only 3 ^ 2 = 9 different possible outcomes, regardless of what you weigh or how you might decide to split up the stacks. Therefore it is impossible to determine which is the fake stack, as that would require distinguishing between the outcomes where each of 10 stacks might be fake.

With a scale it might be possible, but I'm guessing you would still need more information than is offered in the problem. For instance, each of the coins in the fake stack might have to be of the same weight, or at the very least they must all be either heavier or lighter than a real coin. The latter can't be too big of an assumption, as a mixed batch would allow for the fake stack to weigh exactly as much as the others! So some clarity would be appreciated.

Last edited: Apr 27, 2004
16. Apr 28, 2004

### Xiox

Ge, sorry, folks.

I quess, I was thinking to confuse you, but instead I became confused myself!
[Gm, it seems that I was thinking of a balance scale, but not really a balance scale... rather such a scale there 'the opposite weight' was already there... and so that you didn't really compare them to each other... but likely the difference between 'the opposite weight' and a stack, sorry.]

Aye, aye, it is possible to build up a stack with 1 coin from stack 1, 2 from stack 2 etc. if you know the weight of a gold coin.

Yep. Sorry, I didn't 'penetrate' the problem to such an extent.

Indeed, Davilla! I meant that the weight of the entire non-gold stack is different in comparision with a gold stack.

'resolve the issue in two weighings' is that I was thinking of. It seems that NateGT was correct. I wish that I could be that scrupulously fastidious.