You have 24 coins. 23 coins are the same weight, but 1 coin is either heavier or lighter. All you are given is a set of BALANCE scales, which can compare the weight of any two sets of coins out of the total set of 24 coins.

What is the minimum number of weighings required to identify the coin, and why?

EMBED:

Can you figure out what is odd about this paragraph? | **Back – Next** | How long did Christopher live?

Posted by Doug Fred E.I.
on Jun 15th, 2009 and filed under Discussions.
You can follow any responses to this entry through the RSS 2.0.
You can skip to the end and leave a response. Pinging is currently not allowed.

Step 1: weigh 3 against 3 –> either weigh the same in which case dud is in remaining group of 6 or weigh different, then dud is in group weighed. Either way: end up w 2 groups one suspicious, one ruled out.

Step 2: out of suspicious group weigh 3 against 3 of ruled out.

2 possibilities:

A. weigh different, i.e. either lighter or heavier = gives 2 pieces of info: suspicious one in group of 3 and know if is lighter/heavier –>

A Step 3 = final step: weigh 1 against 1; if same then 3rd is dud, if different then know which is dud based on which is lighter/heavier as was determined in step 2. [FINISHED: ONLY 3 STEPS NEEDED]

B weigh same –> have less info, only know dud is in group of 3 that was not in balance.

B Step 3: weigh 1 to 1, if same, then FINISHED: ONLY 3 STEPS NEEDED

B Step 4: if different: weigh 1 against other 1 of 22 which are all ok: this is either same in case dud is 3rd not in balance or different in which case dud is in balance [FINISHED IN 4 STEPS]

The guys that say 4 are wrong. They say in step one “weight 12 vs. 12 with 12 dropping out”. How do 12 drop out? All you know is that one group is different than the other, you don’t know which group has the dud. I can do it in 5 weighings:

A. Divide the coins into 4 groups of 6

1. Weigh Group 1 vs. group 2

2. If “weigh 1″ is equal replace group 2 with group 3 and weigh

If “weigh 2 is equal then dud is group 4 (go to step B)

If “weigh 2″ is not equal then dud is group 3 (go to step B)

2a If “weigh 1″ is not equal replace group 2 with group 3

if “weigh 2a” is equal then dud is 2

if “weight 2a” is not equal then dud is 1

B. Divide Dud group into 3 groups of 2

3. Weigh group 1 and group 2

If “weigh 3″ is equal then dud is in group 3

4a If “weigh 3 is not equal then replace group 2 with group 3 and weigh again

if equal then dud is group 2

if not equal then dud is group 1

C. Select one of the dud group and one of the 22 discarded coins

5. Weigh dud vs. discard

if equal then unweighed coin in group is dud

If not equal then weighed coin in group is dud.

I could not figure this out earlier, but after reading the above answers (and not agreeing with them) I had a brainstorm. It goes like this:

1.) divide (not weigh) the 24 coins into 3 groups

2.) Weigh 2 of the three groups (1st Weighing), if they are equal then the screwy coin is in the 3rd unweighed group.

3.) If they are unequal, then take the 3rd group and weigh it against one of the two previous groups. If equal then the removed group is the screwy one, if unequal then the group which was kept for both weighings is the screwy one. (2nd weighing if required)

4.) Take 4 coins from the screwy group, and 4 coins from one of the previous OK groups of 8 and compare them. If unbalanced, the screwy coin is in the group you placed on the scale, if not its in the group of 4 scewy coins you did not weigh. (Either 2nd or 3rd weighing-depending on previous)

5.) Using the same logic as with #4, divide the 4 screwy into 2 groups (2 coins apiece) and compare to 2 “good coins. (either 3rd or 4th weighing)

6.) Same logic again, use 1 of 2 screwy coins and compare against an identified good coin. If equal, the single screwy coin is the one you did not weigh, if unequal it is the screwy coin you did weigh. (either 4th or 5th weighing).

-So the answer is either 4 or 5 weighings depending on how lucky you were on #2.

You say you don’t agree with my answer of 4. Show me where my logic is wrong? Although what I wrote is correct, I did find an improvement I can make to mine. This improvement give a chance for knowing in three weighings plus after 4 weighings you will know “X” AND if it is heavy or light. For PATH “B” modify as follows:

PATH “B” (4 candidates, relative weight unknown)

-STEP 3: Weigh 3 candidates vs 3 normal. If not balanced, you know “X” is one of the 3 candidates AND if it is heavy or light – move to STEP 4. If balanced, the coin not weighed is “X” and you have found this in just 3 weighings – a 4th will tell you if light or heavy (which is not required to know by puzzle).

-STEP 4: Weigh 1 candidate vs 1 candidate. Balanced says the candidate not on scale is “X”. Unbalanced tells you which on scale is “X” because you know if “X” is heavy or light from STEP 3.

Of course I agree with Robert, that the answer is two if you had to find that coin ASAP and you life depended on it (see my response to Jack above). But we likely want guarantees, and I believe there are two methods to guarantee you will find a solution in 4 weighings. Here is the one I like best: (for brevity, I will name the unique coin “X”)

-STEP 1: Weigh 6 coins vs 6 coins. This will narrow down to 12 coins, but will not tell you if “X” is heavy or light

-STEP 2: As strange as it sounds, weight 8 of the 12 coins containing “X” vs 8 of the coins now know to be normal (as identified in Step1). If “X” happens to be one of the 8 selected, your scale will be imbalanced and you now know “X” if one of the 8 and if it is light or heavy – we will call this path “A”. If your scale is balanced, then “X” is one of the 4 candidates not placed on scale, you have narrowed it down to those 4 but do not know if light or heavy – we will call this path “B”

PATH “A” (8 candidates, relative weight is know)

-STEP 3: Weigh 3 of the 8 candidates vs 3 of the 8 candidates. If balanced, you have narrowed down to the 2 candidates not on the scale. In unbalanced, you have narrowed down to 3 since you know if “X” is heavy or light from Step 2.

-STEP 4: If down to 2 candidates, weigh one vs a normal coin, balanced means the one not on scale is “X”, if unbalanced the candidate on scale is “X”. If down to 3 candidates, weigh 1 candidate vs 1 candidate – balanced says the one not on scale is”X”, if unbalanced you know which on the scale is “X” since you know if “X” is heavy or light from Step 2..

PATH “B” (4 candidates, relative weight unknown)

-STEP 3: Weigh 1 candidate vs 1 candidate. If balanced, you have narrowed to 2 candidates (the ones not on scale). If unbalanced, one of the two on the scale is “X” but don’t know which since relative weight is not yet known.

-STEP 4: Weigh 1 of the remaining 2 candidates vs normal coin. Balanced says the candidate not on scale is “X”. Unbalanced says the candidate on the scale if “X”.

I agree with four tries but maybe less complcated.

1st 12 vs 12 with 12 dropping out, 12 left

2nd 4 vs 4 , if even 8 drop out with 4 left

3rd 2 vs 2, 2 drop out

4th 1 vs 1, one drops out

or

1st 12 vs 12 with 12 dropping out, 12 left

2nd 4 vs 4, if uneven, 4 from here and the other 4 of 12 drop out = 4 left

3rd 2 vs 2, 2 drop out

4th 1 vs 1, 1 drops out

Either way gives you one with more or less weight.

Modification to my calculation !

Among 24 coins, 23 coins are of equal weight and one coin differs in weight from the rest of others. This weight could be heavier or lighter.

The answer is 7 times weighing.

The steps are as follow:

Step 1

Make 2 groups of 12 coins each.

Weighing # 1

Weigh first group making 6 & 6 coins on each pan of the balance.

Weighing # 2

Weigh second group similarly.

Step 2

Weighing # 3

Weigh the coins making 3 & 3 on each side, taken from one pan of the unbalanced group of 6 coins.

If it is balanced then

Make 2 groups containing 4 & 2 coins from another pan. Name as AB & C

Weighing # 4

Weigh the group of 4 coins (AB) making 2 & 2 each side. Name as A & B.

Step 3

If the weighing shows unbalanced then take 1 coin from (A pan) for further action, name it as A1.

Take another coin from the group of 2 coins of step 2, pan C.

Weighing # 5

Weigh one coin each on either side, A1 & C.

Step 4

If the weighing is balanced then take another coin from A1 pan, name it as A2.

Weighing # 6

Weigh one coin each on either side, A2 & C.

Step 5

If the weighing is balanced then take one coin from pan B, name it as B1.

Weighing # 7

Weigh one coin each on either side, B1 & C.

Step 6

If the weighing is balanced then the coin(B2) left from pan B group is the interested one.

If the weighing is unbalanced then coin B1 is the interested one.

Hence, the minimum number of weighing required to find the coin that is heavier or lighter than the rest of other 23 coins is 7.

However, if the weighing of A & B at stage 2 is balanced, then the number of weighing will be less.

Reply