This week's giveaway is in the Spring forum. We're giving away four copies of REST with Spring (video course) and have Eugen Paraschiv on-line! See this thread for details.

it would depend on the specific fake coin problem you are trying to solve.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Punit Jain
Ranch Hand

Joined: Aug 20, 2011
Posts: 1012

2

posted

0

okay here is the problem....

There are n identically looking coins one of which is fake. There is a balance scale but there are no weights; the scale can tell whether two sets of coins weigh the same and, if not, which of the two sets is heavier (but not by how much, i.e. 3-way comparison). Design an efficient algorithm for detecting the fake coin. Assume that the fake coin is known to be lighter than the genuine ones.

Divide and conquer. If n is even, divide the coins into two equal stacks and put them on each side of the balance. One stack will be heavier than the other.
If n is odd, you have to add some nuance with an additional step to deal with the odd coin out, but it should be clear what must be done.

Dennis Deems wrote:Divide and conquer. If n is even, divide the coins into two equal stacks and put them on each side of the balance. One stack will be heavier than the other.

If you know the fake coin is lighter, then you can do it more efficiently than this: think groups of 3.

Even if you don't know the fake coin is lighter, you can do it more efficiently than that. And perhaps "groups of 3" should be "3 groups"?

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808

posted

0

Mike Simmons wrote:Even if you don't know the fake coin is lighter, you can do it more efficiently than that. And perhaps "groups of 3" should be "3 groups"?

I wondered about "3 groups" rather than "groups of 3". I can see that 3 part division is faster than binary, but the notion of iterating over "groups of 3" is mystifying.

Yes, I meant 3 groups - though if you go bottom-up rather than top-down it's similar (I was thinking of the 9-coin version, where it's the same thing!).

(...and n turns out to be the number of weighings.)

The algorithm for a give n is built up from the algorithm for n-1.

To find the fake coin out of 3 coins in 2 weighings...

1 <--> 2
1 <--> 3

See which side is heavier (Right, Left or Neither) and look up the results in the following table:
R R => 1 is light
R N => 2 is heavy
R L => impossible
N R => 3 is heavy
N N => no fake coin
N L => 3 is light
L R => impossible
L B => 2 is light
L L => 1 is heavy

From there, you can develop the algorithm for 12 coins in 3 weighings using the method on the site mentioned above.

Misspelling "Muphry" to add yet another layer of irony was well-played, sir.

Warning: The following post gets into just one little detail of this already-solved puzzle. If you're already bored with the thread up to this point, this post will only make matters worse.

You've been warned.

Ryan McGuire wrote:If the number of coins, c = (n^3 - 3)/2 for some positive integer value of n, then the solution can be found here.

...

To find the fake coin out of 3 coins in 2 weightings...

1 <--> 2
1 <--> 3

...

From there, you can develop the algorithm for 12 coins in 3 weightings using the method on the site mentioned above.

Actually, with a minor change to the starting c=3, n=2 strategy, the set way of getting from a given n to n+1 becomes a little more symmetric and easy to remember.

For 3 coins and 2 weightings

1 -- 2
2 -- 3

L L - impossible
L B - 1 heavy
L R - 2 light
B L - 3 light
B B - all coins equal
B R - 3 heavy
R L - 2 heavy
R B - 1 light
R R - impossible

For the sake of discussion, let's call the strategy for a give n Sn.

This way, the two "impossible" outcomes are the ones that are all R or all L.

Then use this to shift up to the next value of n:

1. For each coin, x, in Sn-1, replace it with 3x-2, 3x-1 and 3x. e.g. Replace coin 1 from Sn-1 with coins 1, 2, and 3 in Sn.

For S3 ...
1 2 3 -- 4 5 6
4 5 6 -- 7 8 9

So far we can say...
L L - impossible
L B - 1,2 or 3 heavy
L R - 4,5 or 6 light
B L - 7,8 or 9 light
B B - all coins equal
B R - 7,8 or 9 heavy
R L - 4,5 or 6 heavy
R B - 1,2 or 3 light
R R - impossible

2. Add a third weighting that separates the coins in each group of three. e.g. separate 1, 2 and 3.
Just put the first coin from each group on the left and the second on the right.

1 4 7 -- 2 5 8

L L L - impossible
L L B - impossible
L L R - impossible

L B L - 1 heavy
L B B - 3 heavy
L B R - 2 heavy

L R L - 5 light
L R B - 6 light
L R R - 4 light

B L L - 8 light
B L B - 9 light
B L R - 7 light

B B L - impossible
B B B - all coins equal
B B R - impossible

B R L - 7 heavy
B R B - 9 heavy
B R R - 8 heavy

R L L - 4 heavy
R L B - 6 heavy
R L R - 5 heavy

R B L - 2 light
R B B - 3 light
R B R - 1 light

R R L - impossible
R R B - impossible
R R R - impossible

(Remember that c = (3^n - 3)/2)

3. With just c-3 (i.e. 9) coins, there are eight "impossible" outcomes. Use those slots for the three additional coins. Put coin c-2 (10) on the left and coin c-1 (11) on the right for the first n-1 (2) weightings. For the last weighting, put coin c-1 on the left and coin c (12) on the right. That new set of weightings will fill in six of the eight "impossible" slots in the lookup table:

L L L - impossible
L L B - 10 heavy <--
L L R - 11 light <--

L B L - 1 heavy
L B B - 3 heavy
L B R - 2 heavy

L R L - 5 light
L R B - 6 light
L R R - 4 light

B L L - 8 light
B L B - 9 light
B L R - 7 light

B B L - 12 light <--
B B B - all coins equal
B B R - 12 heavy <--

B R L - 7 heavy
B R B - 9 heavy
B R R - 8 heavy

R L L - 4 heavy
R L B - 6 heavy
R L R - 5 heavy

R B L - 2 light
R B B - 3 light
R B R - 1 light

R R L - 11 heavy <--
R R B - 10 light <--
R R R - impossible

The added bonus here is that the LLL and RRR rows still represent the "impossible" outcomes. This is in contrast to the iwriteiam.com page I linked to earlier, where the impossible rows were the RL and LR ones for c=3 and RLL and LRR for c=12.

I can easily grind through the steps to create the list of weightings for S4 (c=39):

I'll leave it as an exercise for the interested reader to generate the outcome table. (...because contrary to what Tom Petty would have us believe, the weighting is not the hardest part.)

Punit Jain
Ranch Hand

Joined: Aug 20, 2011
Posts: 1012

2

posted

0

Thanks to all of you..
i don't know why, but i was not getting any email update for this post therefore i was not getting updated weather anyone replying for this post or not.
thank you all for explanation.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1042

4

posted

0

Ryan McGuire wrote:
Warning: The following post gets into just one little detail of this already-solved puzzle. If you're already bored with the thread up to this point, this post will only make matters worse.

(Same warning as before.)

Someone pointed out to me that my previous message solved the classic "either heavier or lighter" problem, as opposed to the "lighter only" problem that Punit actually posed. Of course, the general solution I provided will work, but it certainly isn't optimal.

Can we do use the same basic method to solve the general "lighter only" problem?

Starting solution:
c=3, n=1

3 -- 1

L - 1 is lighter
B - 2 is lighter
R - 3 is lighter

(I picked an initial weighting of 1 vs 3 just so that the results would have the coins in numeric order.)

To go up to the next value of n (number of weightings)...

1. Do the same substitution as with the "heavier or lighter" problem. That is wherever the strategy for n-1 coins had coin x, replace it with coins 3x-2, 3x-1 and 3x:

7,8,9 -- 1,2,3

L - one of 1,2,3 is lighter
B - one of 4,5,6 is lighter
R - one of 7,8,9 is lighter

2. Then add one more weighting to separate the coins in each group of three: include all coins 3x on the left and 3x-2 on the right:

7,8,9 -- 1,2,3
3,6,9 -- 1,4,7

L L - 1 is lighter
L B - 2 is lighter
L R - 3 is lighter
B L - 4 is lighter
B B - 5 is lighter
B R - 6 is lighter
R L - 7 is lighter
R B - 8 is lighter
R R - 9 is lighter

(Again the exact distribution of coins was chosen just so that results table would be in order.)

Since there are no "impossible" results, as there were in "heavier or lighter" problem, there are no places to insert additional coins. This yields results of...

c(1) = 3
c(n) = c(n-1) * 3 for n > 1

or c(n) = 3^n

Just as an exercise, let's show the weightings for n=3:

L L L - 1 is lighter. That makes sense since coin 1 is on the right for all three weightings.

I'll leave the rest of the result table to anyone who cares enough.

If you recall, for the "heavier or lighter" problem, c(n) = (3^n - 3)/2. If we know that the counterfeit coin is necessarily lighter than the rest, then we can have a coin population is more than twice as large as the "heavier or lighter" problem for a given number of weighting:

n=1 --> c = 3 vs 0
n=2 --> c = 9 vs 3
n=3 --> c = 27 vs 12
n=4 --> c = 81 vs 39