83 replies to this topic

[Prime]

... You can distinguish among 3**N cases in N weighings. ...

I’ll take up an issue with that statement. I’d say it depends on the kind of possibilities that you are trying to distinguish. The puzzle required to find the counterfeit coin AND tell whether it is heavier or lighter. While you can definitely solve 27 in 4 weighings, I don’t see how you can solve 40 in 4. Although, there are only 80 possibilities (less than 3**4). You can find one counterfeit coin out of 40 in 4 weighings, but not necessarily tell whether it is heavier, or lighter.
For the sake of saving space, solve 13 coins in 3 weighing. I can see how you can find counterfeit coin there, but I can’t ensure determining whether it is heavier, or lighter.

[Prime]

In fact the answer is 2!!!!

You need a minimun of 2 weighs to find the bad coin IF YOU ARE LUCKY!

1- You take 2 coins, you weight them and you get an unbalanced situation.
2- You take one of them and you compare to an outside coin and you still find an unbalanced situstion ==> The bad coin is X and its 9g or 11g

So the minimum ways needed are 2.

First, I’d like to complement the clever redundant use of the factorial sign. (2!!!! = 2).
However, your answer is wrong. The original question was: “… how many minimum ways …”. Whereas, you pointed out only one such way. Indeed, the minimum number of weighings to determine counterfeit coin is 2, if you get lucky. But there are 27!/(25!*2!)=351 ways to compare 2 coins out of 27. And then there are 25*2 ways to compare one of those two to the 25 on the side. Or you could choose to drop 13 coins onto one side of the scale and 13 onto another, and get lucky finding that they weigh the same. And there are C(27,13)*C(14,13) ways, or 27!/(14!*13!)*14 of doing that. Then there are 26 ways to compare the counterfeit coin with one of the true ones. Simplified, the correct answer is: 27! / 24! + 27! * 26 / (13! * 13!). That seems like a very large number, which may not fit into the space allotted by this forum.
(Also, see my previous post for further discussion of the puzzle as it was meant.)

[Prime]

For an in-depth discussion and a maximized version of weighing problem, see my "Ultimate weighing problem" topic on this forum.

[Niraj Ram]

Actually 3 weighs are enough.. Its very simple..

[Niraj Ram]

First split it into 3 parts of 9-9-9 each.. weigh any two, if they weigh same other part of 9 contains faulty one, else the one which weighs different contains faulty ball..
so
first step--> 9-9-9.
second step-->3-3-3.
thord step--> 1-1-1.

[gdell]

The answer is 4 times. split the pile into two piles of 13 if the scale is even than you have the light coin in your hand. if one side is light than you split that side into two piles of six. If the scale is even than the light one is in your hand. If one side is light than you split that side into two piles of 3 if the scale is even than the one in your hand is the light one. if the scale is light on one side than you take two of the 3 coins left and weigh them. If the scale is even than the coin you have in your hand is the light one. if one side is light than you have your light coin

[Blasphemer]

4 tries, after which I can also tell you whether the coin is heavier or lighter than the other coins...

Here's an interesting variation. Suppose there were two odd coins and that one odd coin weighs half as much as an ordinary coin, and the other odd coin weighs half again more than a regular coin (e.g., regular coins weigh 10, the lighter odd coin weighs 5, and the heavier odd coin weighs 15).

If I had more time I'd write you a shorter description of the solution.

Spoiler for my solution

I think the knee jerk reaction is to forget that scales can also balance in addition to showing one side heavier than the other. Thus creating 3 possible outcomes; equal, left heavier, & right heavier. The only obvious way to exploit this is to split the coins into 3 groups. Conversely, since we aren't told heavier/lighter in advance we have to spend a scale measurement to figure that out.

For the first weighing split the 27 coins into 3 piles of 9 coins each; for reference assign each pile a letter: A, B, & C. In this case, I'll let C sit out and place A & B on the scales.

CASE 1 (A = B):
If A = B, that means the odd coin is in C. I don't know if the coin is heavier or lighter yet, I could postpone figuring this out now or I could determine heavier or lighter at this time by another weighing of C against A. Taken to it's logical end, I could get lucky and find the coin in 3 weighings 1/27th of the time but we wouldn't know heavier/lighter then. For sake of consistency with the other two inequality cases, I would do the weighing and note whether C (the one with the odd coin) is heavier or lighter than A.

CASE 2 (A < B):
If A < B, then the odd coin is contained by A or B, but I don't know if it is heavier or lighter yet. I can determine heavier or lighter as well as whether the coin is in A or B with one more weighing of A against C. If A = C, then I know that B contains the odd coin, and that the odd coin is heavier than normal coins. If A < C, then I know that A contains the coin and that it is lighter. Irony has it that A > C isn't really a possibility at this point because it would imply that A has the odd coin and that it is heavier; however by definition C and B weigh identical weights and which contradicts the original weighing result that A < B.

CASE 3 (A > B):
If A > B, I can again weigh A against C and determine which pile has the coin as well as whether the coin is heavier/lighter with similar logic as the last paragraph.

At this point, in two weighings I know two things: 1) whether the coin is heavier/lighter than the rest, and 2) I know which group of 9 coins contains the odd coin.

For the remaining 3rd & 4th weighings I proceed by similarly splitting the group with the coin into 3 groups for the next weighing and leaving one group off the scales. I already know heavier vs lighter, so I'm really just looking for two outcomes: 1) equality, which implies the odd coin is in the third pile, or 2) unbalance, in which case I'm looking for the side with the coin (which I know based on heavier/lighter determined in the second weighing.) Thus the 9 is split out into 3 groups of 3 yielding just one of those groups with the coin. Doing this one more time takes a group of 3 coins and yields the odd coin in 4 weighings, and we know whether it is heavier or lighter.

I find it interesting/amusing that adding anywhere from 1 to 54 more coins would only increase it to 5 weighings.

[NintendoMad]

I got a minimum of 4 and maximum of 7

Spoiler for Minimum and Maximum

Minimum
1. Spilt into 3 groups of 9 (let's call the a, b and c respectively, for reference) and weigh A and B. For a minimum number of weighings, these must equal, making the different coin in C
2. spilt C into 3 groups of 3 (let's call them C1, C2 and C3 respectively for reference) and weigh C1 and C2. For a minimum number of weighings, these must equal, making the different coin in C3.
3. C3 will contain 3 coins (let's call them 1,2 and 3 respectively for reference) and weigh 1 and 2. For a minimum number of weighings, these must equal, making 3 the different coin.
4. You then weigh this coin against any other coin and see whether it goes down, so weighs more, or goes up, so weighs less.

Maximum
1. Weigh A and B. Now, if they are unbalanced, then you weigh A with C.
2. If A and C is balanced, the B holds the different coin (dc)If they are unbalanced then A holds the dc. Lets say A=C so B
3. Spilt B - 3 groups of 3 (B1, B2, B3) weigh B1 and B2. Unbalanced, so you weigh B1 and B3.
4. If they are balanced then B2 holds the dc. If they are unbalanced, then B1 holds the dc. Lets say B1 = B3, so B2 holds dc.
5. 3 coins in B2 (1, 2 and 3). Weigh 1 and 2. If they are unbalanced, then you weigh 1 and 3.
6. If they are balanced then 2 holds the dc. If they are unbalanced, then 1 hold the dc. Let's say that 1 = 3, so 2 is the dc.
7. Then you measure 2 with any coin to see whether it ways more or less, so whether it is heavier or lighter.

[Scarr]

I got it in 4, a different way, and with some optimism, possibly 2.

27 coins.

Split into two groups. Remainder 1. Weigh the two groups of 13 against eachother. If they balance, the remainder is the coin. (be that the case, remove 1 coin out of one of the groups weighed, and replace it with the remainder coin to determine heavier or lighter)

13 and 13 narrows down to one heavier or lighter group

Split it into two, and take another remainer.

6 and 6 remainder 1

Continue the process

3 and 3 no remainder

1 and 1 remainder 1 <- in this case, you are down to the last 3 coins. If they balance, the remainder is the one. If not, the one that is heavier or lighter, depending on what was determined earlier, is the one.

So the weighing is:

13 v 13
6 v 6
3 v 3
1 v 1 4 times.

[lovinduke]

You can get it in 3... every time... and its not hard.

First, divide the 27 into 3 piles of 9. Put 9 on one half of the scale and 9 on the other. If one of these groups of 9 weighs less, you will continue with these 9. If they are even, you will continue with the last group of 9 not yet weighed. So at these point we have it narrowed to 9.

Second, divide these 9 into 3 piles of 3. Put 3 on one half of the scale and 3 on the other. If one of these groups of 3 weighs less, you will continue with these 3. If they are even, you will continue with the last group of 3 not yet weighed. Now we have it narrowed down to 3.

Third and last, divide these 3 into 3 piles of 1. Put one on one half of the scale and 1 on the other. If one is lighter you have found your answer. If they are even it must obviously be the last one not weighed.

Solved in 3.