Punit Jain

Ranch Hand

Posts: 1085

3

Punit Jain

Ranch Hand

Posts: 1085

3

posted 5 years ago

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.

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.

dennis deems

Ranch Hand

Posts: 808

posted 5 years ago

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.

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.

Matthew Brown

Bartender

Posts: 4568

9

Mike Simmons

Ranch Hand

Posts: 3090

14

dennis deems

Ranch Hand

Posts: 808

posted 5 years ago

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.

Mike Simmons wrote:Even if youdon'tknow 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.

Matthew Brown

Bartender

Posts: 4568

9

Ryan McGuire

Ranch Hand

Posts: 1143

9

posted 5 years ago

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

n=2 --> 3 coins

n=3 --> 12 coins

n=4 --> 39 coins

n=5 --> 120 coins

n=6 --> 363 coins

(...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 (

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.

n=2 --> 3 coins

n=3 --> 12 coins

n=4 --> 39 coins

n=5 --> 120 coins

n=6 --> 363 coins

(...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 (

**R**ight,**L**eft or**N**either) 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.

Ryan McGuire

Ranch Hand

Posts: 1143

9

Ryan McGuire

Ranch Hand

Posts: 1143

9

posted 5 years ago

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

You've been warned.

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:

1 2 3 10 -- 4 5 6 11

4 5 6 10 -- 7 8 9 11

1 4 7 11 -- 2 5 8 12

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):

1, 2, 3, 4, 5, 6, 7, 8, 9,28,29,30,37 -- 10,11,12,13,14,15,16,17,18,31,32,33,38

10,11,12,13,14,15,16,17,18,28,29,30,37 -- 19,20,21,22,23,24,25,26,27,31,32,33,38

1, 2, 3,10,11,12,19,20,21,31,32,33,37 -- 4, 5, 6,13,14,15,22,23,24,34,35,36,38

1, 4, 7,10,13,16,19,22,25,28,31,34,38 -- 2, 5, 8,11,14,17,20,23,26,29,32,35,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

Greg Charles wrote:Drat. Murprhey's law strikes again.

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:

1 2 3 10 -- 4 5 6 11

4 5 6 10 -- 7 8 9 11

1 4 7 11 -- 2 5 8 12

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):

1, 2, 3, 4, 5, 6, 7, 8, 9,28,29,30,37 -- 10,11,12,13,14,15,16,17,18,31,32,33,38

10,11,12,13,14,15,16,17,18,28,29,30,37 -- 19,20,21,22,23,24,25,26,27,31,32,33,38

1, 2, 3,10,11,12,19,20,21,31,32,33,37 -- 4, 5, 6,13,14,15,22,23,24,34,35,36,38

1, 4, 7,10,13,16,19,22,25,28,31,34,38 -- 2, 5, 8,11,14,17,20,23,26,29,32,35,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

Posts: 1085

3

Ryan McGuire

Ranch Hand

Posts: 1143

9

posted 5 years ago

(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:

19,20,21,22,23,24,25,26,27 -- 1,2,3,4,5,6,7,8,9

7,8,9,16,17,18,25,26,27 -- 1,2,3,10,11,12,19,20,21

3,6,9,12,15,18,21,24,27 -- 1,4,7,10,13,16,19,22,25

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

Ok,

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:

19,20,21,22,23,24,25,26,27 -- 1,2,3,4,5,6,7,8,9

7,8,9,16,17,18,25,26,27 -- 1,2,3,10,11,12,19,20,21

3,6,9,12,15,18,21,24,27 -- 1,4,7,10,13,16,19,22,25

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

Ok,

*now*I'm done with this problem.