Coin problem

[Wizard]

2nd problem can be continued in various ways, here's one, divide the 6 coins into 2 stacks of 3, weigh 1 stack vs 3 coins from known good coins...resulting sub-problem is find unknown defective coin among 3 coins...which is my "simple" case above and requires 2 weighings.

Except you have additional knowledge as well. If the defective coin is within these 6, then you've got a stack of coins you know to be good. Find a way to use them, and the whole problem will be easier

[WILL]

I have one more interesting problems^^ ( I think it's easy but fun )
Two students found a scale in the garden. They try to put their bags on the scale. Scale shows that A student's bag is 3g and B student's bag is 2g. Then they put both bags on the scale, now scale pointers show 6g.
A : what the hack, how 3 + 2 = 6 ?
B : you're dump, don't you see the scale pointer is inclined ?

What's the real mass of A and B ?

[Alvaro]

3+x + 2+x = 6+x => x=1
So their masses are 4g and 3g respectively.

That was way too easy. The one with the 12 coins is better. Are there people still thinking about it?

[WILL]

haha ! Bravo Alvaro ^^ !
This one is interesting!

Cut this picture into smaller picture ( must be parallel ) and then put them together so that it will become a square with all the stars are on the same diagonal.

[WILL]

The sum is of yellow area = ?

[Darryl]

No, it has to be 4.

You need to prove a statement like that. What you explained is how the things that you thought of don't lead to a solution in 3, but not that one cannot be achieved.

Just think harder. Hint: Can you do it for 4 coins in 2?

Yes, I can find the coin from 4 coins in 2 weighings, but it's impossible to go from 12 to 4 coins with only 1 weighing so I'd still be at 4.

As far as proving it can't be done in three, I don't really know how to go about proving it other than enumerating all the possibilities which would be a bit tedious...let me think about it some more


...


Ok I've thought about it some more and although again I don't know how to prove it, I will make the hypothesis that no matter how you divide your initial stacks and weigh, you can't even positively identify the stack with the defective coin in less than 2 weighings and even then may still not know if it is heavier or lighter. Then once you identify the stack, it will take you 2 weighings to identify the coin.


...

Well, I decided to just look up the answer and found this neat way using base 3 of doing it... http://www.cut-the-knot.org/blue/weight1.shtml

[Alvaro]

I didn't think of anything fancy to do it in 3 steps. I just listed all the possibilities and tried to always perform a weighing that would divide the possibilities left in three groups of about the same size.

Initially, there are 24 possibilities: 1 is heavy, 2 is heavy, ..., 12 is heavy, 1 is light, 2 is light, ..., 12 is light.

If we weigh {1,2,3,4} -vs- {5,6,7,8}, we have three possible outcomes:
1) {1,2,3,4} is heavier than {5,6,7,8}. This corresponds to cases 1H, 2H, 3H, 4H, 5L, 6L, 7L and 8L.
2) {1,2,3,4} is lighter than {5,6,7,8}. This corresponds to cases 1L, 2L, 3L, 4L, 5H, 6H, 7H and 8J.
3) {1,2,3,4} is exactly as heavy as {5,6,7,8}. This corresponds to cases 9H, 10H, 11H, 12H, 9L, 10L, 11L and 12L.

Now, you already solved the sub-problem (3) in two additional weighings, and sub-problems (1) and (2) are symmetrical, so you only have to solve one of them.

In the sub-problem (1), the next weighing could be something like {1,2,5}-vs-{3,4,6}, which subdivides the 8 cases into these subproblems:
1.1) {1,2,5} is heavier than {3,4,6}: 1H, 2H, 6L.
1.2) {1,2,5} is iighter than {3,4,6}: 5L, 3H, 4H.
1.3) {1,2,5} is as heavy as {3,4,6}: 7L, 8L.

1.1) can be resolved by weighing {1} -vs- {2}, and the rest of the cases are equally trivial.

[Darryl]

Is this you in disguise Alvaro?

[Alvaro]

Is this you in disguise Alvaro?

No, that's not me. I can't do computations in my head better than anyone else. I wouldn't even know where to start computing the 13th root of a number...

[ventsyv]

This kind of problem is kind of weird for me to think about, because it is asking for the best case scenario. Usually you consider either worst case or average case, not best case.

Anyways, I think my solution was right. I'll try to explain it again, this time starting with 4 coins at step 2.

We take coin1 and coin 2. Assuming coin1 != coin2 we know either 1 or 2 is fake and all of the rest are OK.

We take coin4 (which we know for sure is OK) and compare it with coin1. If the coins weight the same we know the fake is coin2. If they do not weight the same the fake is coin1.
Thats 3 steps.

Now if in step 2 coin1 == coin2 -> coin3 or coin4 are fake. We can measure either coin with coin4 (which is OK). Lets say we take coin4 and coin2. If the two weight the same the fake is coin3. If they weight different the fake is obviously coin2.
Still 3 steps.

[ventsyv]

Is this you in disguise Alvaro?

No, that's not me. I can't do computations in my head better than anyone else. I wouldn't even know where to start computing the 13th root of a number...

Come on Al, I had such big hopes for you

No seriously, while impressive, I don't think much of such an achievement. Nothing a computer can't do. I think humans should focus on creative thinking, not number crunching. We have computers that are much better at that, but awful creating creative ideas (yeah, yeah I know about the recombinational design computer).

It is like, caring a big luggage around instead of putting it in the trunk of your car and driving to wherever you are supposed to go.
Even if you get there faster, then anyone before you, you'll still be slower then a car ...

[Alvaro]

This kind of problem is kind of weird for me to think about, because it is asking for the best case scenario. Usually you consider either worst case or average case, not best case.

But we *are* minimizing the amount of weighings required in the worst case...

Anyways, I think my solution was right. I'll try to explain it again, this time starting with 4 coins at step 2.

We take coin1 and coin 2. Assuming coin1 != coin2 we know either 1 or 2 is fake and all of the rest are OK.

We take coin4 (which we know for sure is OK) and compare it with coin1. If the coins weight the same we know the fake is coin2. If they do not weight the same the fake is coin1.
Thats 3 steps.

Now if in step 2 coin1 == coin2 -> coin3 or coin4 are fake. We can measure either coin with coin4 (which is OK). Lets say we take coin4 and coin2. If the two weight the same the fake is coin3. If they weight different the fake is obviously coin2.
Still 3 steps.

But when you say "the fake is coin3", you still don't know whether it's too light or too heavy, so you haven't solved the problem.

In order to finish the case where 4 coins are left after the first step of the 12-coin problem (case 3 in my previous discussion, but renaming the coins to 1,2,3,4), we only have 8 cases to distinguish: 1H, 2H, 3H, 4H, 1L, 2L, 3L and 4L.

Remember that we are at step 2 of the process, which means that we have 8 other coins lying around that are known to have the standard weight.

Compare {1,2} to {3,5} (5 has standard weight).

If {1,2} > {3,5} we can be in cases 1H, 2H or 3L.
If {1,2} < {3,5} we can be in cases 1L, 2L or 3H.
If {1,2} == {3,5} we can be in cases 4L or 4H.

Now it's easy to finish off each case with one more weighing. Actually, comparing {1,3} to {4,5} works for all three cases.