stacking six and removing one at a time cannot be considered using the scale only once. i figured four - set any three (A) against another three (B). then compare one of those, say A, with a third set (C). if both comparisons are equal then D contains the fake coin; if neither are equal then A contains the fake coin. if only the first is equal than C contains the fake, and if only the second was equal than B contains the fake. In two uses of the scale we know which sets contain real coins and which set of three contains a fake. we can now weigh two real coins against two from the set containing the fake - if they are equal then the remaining coin is a fake, if they are not equal we must weigh a single real coin against one of the two containing the fake to determine which is different.

Theoretically this is cheating as it is giving the information- now a truly mad king would see this, and all would be killed-
you would get 60-75% bycalling

There is no guarantee that any of them would be saved. There is no known number for blue or red hats, all it would take is a random pattern (ie; r. r. r. b.b.b.b.r.bb.r.r.b.r.r.r.r.) and you would have to just guess. Statistics aren't a guarantee. Like scoop said the solution listed is cheating that the king would have heard.

100 people can be saved if the proportion of hats is equal, 99 if not. In retrospect, the question doesn't specify, but you CAN guarantee 100 if the proportion of hats is known in advance.

got it the first time in under 30 seconds but i agree with all of u

This problem requires you to spot the trick, i.e. for first to basically say the # of hats modulo 2. Effectivley the first is a parity bit. So this is easy for maths/CS students but not nesecarily for the general public, it should stay in this section. I recomend ^ to google 'three gods puzzle' if you want a logical challange. Better still prove the completness theorem for propositional calculus!

p.s. really good website :)

Or, when the men are consulting, they could say the color of the other person's hat, when pretending to guess the color of their own hat. That leaves all 100 people surviving.

99 is the most you can save for sure, just by calling the color of the wise man in front of you. The first one has a 50% chance anyways.

"99 is the most you can save for sure, just by calling the color of the wise man in front of you. The first one has a 50% chance anyways."

Actually, no.

To show this, using your logic, if you wore a blue hat and the person behind you answered blue, would you answer blue or red GIVEN that the person in front of you had a red hat?

The solution doesn't seem to work, as let's say it's the same scenario, except with 5 people who are all wearing red hats. The first person would say "red", since he sees four red hats. However, the second person would see 3 red hats, and would be forced to say "blue" in order to stick to the plan. He would be able to deduce that he had a red hat, obviously, but if he said "red", then the other three would assume that one of them had a blue hat/think that his statement was at odds with the first person. I don't see how the solution could work.

make group of 4 coins.
I] weigh 4/4, the balance tilts
ii] take 02 from heavier scale aside, put 01 from lighter scale to make 3/3 and weigh; should get it now
lii] for the other 4 if the first balances, take away 01 and weigh with 3 good coins. should get it from here...

devide the coins in half

weight the coins 6 against 6... A has 6 coins and B has 6 coins...
then determine which is a little lighter.. this means that either group A or B that is lighter would contain the fake one

then devide it again into 2
so 3 against 3 coins.... then the group that is lighter would contain the fake one

since u cant devide the coins by half...
weight the 2 coins... if one of the 2 coins is lighter then it is the fake.. if its equally balanced then the one u didnt weight is the fake one

Just separate the coin to other coin...

step 1. Divide all the coins among 6-6 group "A" & "B" & put them on two side of the weight machine. One side must be lighter then the other, say "A" coz of all real coins.
Step 2. Divide the "B" group in 3-3 each coins say "C" & "D". one side must be lighter again, say "C" coz of all real coins.
Step 3. Divide the "D" group in 1-1 each & keep the one coin spare. If the sides of the weight machine are not equal, you know which one is the fake one. If both the sides are equal, then the coin that you have kept aside is the fake one.

So in just 3 steps you have the answer. Cheers

Dividing coins 6-6 will not work. All the variant lead to garantied solution on 4 measurments. King is right, you must divide coins on 4 groups by 3, but he only miss the conclusion whether the fake coin is ligther or heavier. This is what is left for me...it is in my solution

3 measurements. First you divide the 12 coins in 4 groups of 3 (1,2,3 / 4,5,6 / 7,8,9 / 10,11,12).

1. Measurement you take 1,2,3 and 4,5,6 . The outcomes are 2: even weight or scale tilts.
a. > (< ) not even, then fake is among 1,2,3,4,5,6
2. Measurement compare 1,2,3 and 7,8,9 ( 7,8,9 are known good coins already )
a. = fake is in 4,5,6 and is lighter (heavier). Depends on the result of Measurement 1
b. > ( 2 is fake
b. = 3 is fake
c. < 1 is fake , because is lighter as determined is second measurement
b. = then fake coin is in other 2 groups. Do rest of the procedure symmetrically.

I tryed to explane something up there but the cut and paste from Word didn't work. I start thinking again and now I think that there is no solution in 3 measurements. First of all, guys, WE DON"T KNOW WHETHER THE FAKE COIN IS LIGHTER OR HEAVIER! This by itself adds one more measurments for most of you. With luck some of you may get it in 3 times by THERE IS NO GARRANTY THAT YOU ALWAYS NEED ONLY 3 MEASURMENTS. Dividing 6-6 is dosn't hold any scrutany, non the less becouse what you measure with the first measurment? Of course scale will till on some direction, but we already know that we have fake coin and it must be in one of the 2 halves. Same time we cannot determine if the fake is lighter of hevier. Just wasted try. Sorry guys this logical problem is beyond the simplified solutions of most of you . It is much deeper. King is very close, but... lets say you have first measurment equal (meant you have good coins on scale), then second measurment where you replace one of the group x3 with third group and you have equal again. Now you will know again like in all the other variants in which group of 3 the fake is but YOU WILL NOT KNOW IF IT IS LIGHTER OR HEAVIER and if the third measurment turns not to be equal, then you don't know if the ligther side or heavier side is fake. I chalange anybody, go deeper, explore all routes... THERE IS NO SOLUTION WITH GARANTIED 3 MEASURMENTS.

The first weigh:
Put four coins on one side of the scale and four on the other side.
case 1:
The scale balances. An easy solution folows.
case 2:
We have just created three piles which I will call clean, heavy, and light.

The second weigh:
Put two heavy coins and one light coin on each side of the scale.
case 1:
The scale balances. An easy solution follows.
case 2:
I'll give you a hint. The two heavy coins on the heavy side and the light coin on the light side are the only possibly fake coins.

hey i think u can generalise it for any number of coins with one fake coin is mixed in the following way..
first divide x into 3 equal parts..

measure 1 and 2.
if equal, measure 3 wit 1 or 2( tis is to find whether the 3rd group is lighter or heavier which ll in turn say if the fake coin is lighter or heavier).

then keep dividing it into 3 until u reach a number lesser than 3 in a group.
this will do in log x to the base 3.

now find the number of times you divided.
that is the first power of 3 greater than equal to x.
suppose it is n.

then n+1 will be the answer

(n comparisons at each step + 1 extra comparison in first step to determine if the fake coin is lighter or heavier).

"measure 1 and 2"
i mean 1st and 2nd group.
then measure 3rd group with either 1st or 2nd group.
** n case the 1st and 2nd are itself not equal(now 3rd group is confirmed to ve all as good coins) then the comparison with the 3rd group will say if the fake coin is lighter or heavier..

hope tis works..

Thanks, Warren!
Your Second measurment is 3 coins on each side. On each side 2 "heavy" + 1 "light".
Thirth measurement:
- If the scale tilts on second measurement the 2 "heavy" coins from the heavy side of the second measurment are compared.
- If equal the "light" coin on other side of second measurement is fake, light. If it tilts the heavy side of the thirth measurment is the fake becouse it is supposed to be "heavy".
Of course logic can do mirrored Heavy-Light.

Step one: Divide the coins into 3 piles of 4, call the piles A,B,C. 2 of these piles weigh the same.

First measurement: A-B.
Outcome 1: equal
Outcome 2: unequal

If Outcome 1, then Second measurement: 2 from C and 2 from A (we know A has all real coins)
Outcome 3: equal
Outcome 4: unequal

If Outcome 3, then Third measurement: Replace one of the coins from the scale with one of the remaining coins from C. If the scales balance, then the last coin is fake. If the scales don't balance, then the last coin added is fake.

If Outcome 4, then Third Measurement: Replace one of the two coins from C with another coin from A. If the scales remain balanced, then the last coin removed is fake. If the scales don't balance, then the remaining coin from C on the scale is fake.

If Outcome 2, then Second Measurement: We know that all of C are real. Replace two coins from A with two coins from C
Outcome 5: Equal
Outcome 6: Unequal

If Outcome 5, then Third measurement: One of the coins removed in the second measurement was fake. Replace one of the coins on the scale with one of the coins that was removed. If the scales don't balance, then the last coin added was fake. If the scales balance, then the coin that wasn't added is the fake.

If Outcome 6, then Third measurement: One of the two coins on the scale from A is the fake. Replace one of the coins from A with a coin from C. If it balances, then the coin you removed is the fake. If it doesn't balance, then the last coin on the scale from A is fake.

my post is wrong

First divide the coins into 3 groups of 4, OOOO OOOO OOOO
Pick two groups and place one on each side of the scale.

For the following,
L=the coins that could possibly be light and are not heavy
H=the coins that could possibly be heavy and are not light
G=the coins that are known to be the correct weight
LH=the coins that could possibly be light or heavy

Measurement 1
Outcome 1: OOOO < OOOO
Label the coins 1,2,3,4 < 5,6,7,8 (L=1,2,3,4, H=5,6,7,8, G=9,10,11,12)
Label the unused group 9,10,11,12
Outcome 2: OOOO = OOOO
Label the coins 1,2,3,4 = 5,6,7,8 (LH=9,10,11,12, G=1,2,3,4,5,6,7,8)
Label the unused group 9,10,11,12

Measurement 2
If outcome 1, then compare 1,7,9 with 5,6,3
Outcome 3: 1,7,9 < 5,6,3 (L=1, H=5,6, G=2,3,4,7,8,9,10,11,12)
Outcome 4: 1,7,9 > 5,6,3 (H=7, L3, G=1,2,4,5,6,8,9,10,11,12)
Outcome 5: 1,7,9 = 5,6,3 (L=2,4, H=8, G=1,3,5,6,7,9,10,11,12)

If outcome 2, then compare 1,2 with 9,10
Outcome 6: 1,2 not equal 9,10 (LH=9,10 G=1,2,3,4,5,6,7,8,11,12)
Outcome 7: 1,2 = 9,10 (LH=11,12, G=1,2,3,4,5,6,7,8,9,10)

Measurement 3
If outcome 3, then compare 1,5 with 11,12
Outcome 8: 1,5 < 11,12; (L=1)
Outcome 9: 1,5 > 11,12; (H=5)
Outcome 10: 1,5 = 11,12; (H=6)

If outcome 4, then compare 7,10 with 11,12
Outcome 11: 7,10 > 11,12; (H=7)
Outcome 12: 7,10 = 11,12; (L=3)

If outcome 5, then compare 2,8 with 11,12
Outcome 13: 2,8 < 11,12 (L=2)
Outcome 14: 2,8 > 11,12 (H=8)
Outcome 15: 2,8 = 11,12 (L=4)

If outcome 6, then compare 1,2 with 3,9
Outcome 16: 1,2 not equal 3,9; (HL=9)
Outcome 17: 1,2 = 3,9; (HL = 10)

If outcome 7, then compare 1,2 with 3,11
Outcome 18: 1,2 not equal 3,11; (HL=11)
Outcome 19: 1,2 = 3,11; (HL=12)

This is the correct solution.

The first step as everyone one said is to divide by three.
NOTE YOU HAVE TO EXPECT THE WORSE AS THE QUESTION REQUIRES

To determine the Group that contains the fake coin and whether if its lighter or heavier you need to do at least two measurments not less.

THERE ARE TWO POSSIBLE WAYS THE OUTCOME COULD BE FOR THE FIRST 2 MEASURMENTS:

1- GROUP1=GROUP2 so then measure GROUP1 and GROUP3, if GROUP3 is heavier then so is the fake coin and verse-versa.

2- GROUP1#GROUP2 (THIS IS WORST):

SO LETS PRETEND GROUP1 IS HEAVIER THEN GROUP2. NOW I JUST NEED TO DO ONE MORE MEASUREMENT, AND WHICHEVER GROUP I MEASURE WITH GROUP3 I CAN DETERMINE THE GROUP THAT CONTAINS THE FAKE COIN AND IF ITS LIGHTER OR HEAVIER.
a)if you use GROUP1:
-If GROUP1=GROUP3 then GROUP2 has the fake and it
is lighter.
-If GROUP1#GROUP3 so GROUP1 has it and it's heavy
(because GROUP1 has to be heavier than GROUP3)
b)if you use GROUP2:
-If GROUP2=GROUP3 then GROUP1 has the fake and it
is heavier.
-If GROUP2#GROUP3 so GROUP2 has it and it's
lighter(because GROUP2 has to be lighter than
GROUP3.

NOW I AM ALMOST DONE, AND AT THIS STEP I KNOW WHTHER THE FAKE COIN IS LIGHTER OR HEAVIER. SO TO CONTINUE I WANT TO PICK THAT IT IS LIGHTER( YOU CAN CHOOSE THAT IT IS HEAVIER AND FOLLOW THE FOLLOWING STEPS AND YOU WILL GET TO THE ANSWER)

3rd measurement:
split the group that has the fake into two so each group will have 2 coins and measure. you will get one group lighter then the other.

4rth measurement and the last one:
you are left with two coins measure them and you get the fake wich is the lighter one.

NOTE IF YOU CHOOSE IT TO BE HEAVIER THE ONLY DIFFERENCE IS THAT U HAVE TO TRACK THE HEAVIER GROUP AND THEN THE HEAVIER COIN.

I've worked out two separate solutions, so if this first one doesn't look like what you're expecting it might be because the other solution is more familiar.

12 coins, A B C D E F G H I J K L

1st Measurement
ABCD vs EFGH: if they balance, loose coin is in IJKL, SO....
2nd Measurement
ABC vs IJK: if they balance, loose coin is L, SO....
3rd Measurement
A vs L: we now know whether L is heavier or lighter

If...
2nd Measurement
ABC < IJK: coin is heavier and in IJK, SO.....
3rd Measurement
I vs J: if balanced, K is heavier, if unbalanced, heavier coin known

If....
2nd Measurement
ABC > IJK: coin is lighter and in IJK, SO.....
3rd Measurement
I vs J: if balanced, K is lighter, if unbalanced, lighter coin known

This all obtains for different coin being in IJKL

If (after 1st measurement)
ABCD < EFGH: discard IJKL - will not be needed again
2nd Measurement
ABE vs CDF: if balanced, coin is in G or H, SO......
3rd Measurement
G v H: Lighter coin is the rogue

If..
2nd Measurement
ABE < CDF, there has been no change in direction of scale by swapping CD and E, so loose coin is A,B,F, SO......
3rd Measurement
A v B: if balanced, F is lighter coin, if unbalanced, lighter of A or B is rogue

If ABE > CDF, there has been a change of direction of scale by swapping CD and E, so loose coin is in C,D,E, SO......
3rd Measurement
C v D: is balanced, E is lighter coin, if unbalanced, lighter of C or D is rogue

Repeat above (reversing as appropriate) for if
1st Measurement
ABCD > EFGH

The important feature here:
If the first 8 balance, you will need to use three of the "safe" coins to weigh against 3 of the remaining 4

If the first 8 do not balance, you can safely discard the other 4 as "safe", and simply do some inter-weighing from among the 8 remaining coins.

there is a much simpler solution than what all of u have proposed.
Hint: divide 12 coins into 4 groups of 3 coins. you should be able to get the answer from here.