I think it might be bad for peoples health.(Original post by James Gregory)
It's quite an interesting puzzle, even though I failed. It's cool the way there are far more possible approaches than you would first imagine, and that seemingly correct solutions can in fact be wrong.
I'm assuming fat_hampster's method works in that it makes the effort to account for every possibility, though it's not written in a very easy to follow fashion. RupertTheBear's method is quite cool, but it's very complex  I have my doubts that anyone could come up with that just off the top of their head without having first studied some higherlevel discrete maths, or at least having done several similar problems before.

 Follow
 61
 07122010 15:04

 Follow
 62
 07122010 15:04
(Original post by shamim2k9)
Explain please , im baffled
Start off by putting 4 coins on each side of the scales and measure.
If the 4 coins balance then proceed to (A) if not proceed to (B).
(A) Add one coin to either side of the scales. Either the scales stay balanced (i) or they become tipped (ii). (i) The scales are balanced therefore the bad coin is one of the two coins not on the scales. Measure one of these remaining coins against a real one. If balanced the last coin is bad, if unbalanced the coin on the scale is bad. (ii) The bad coin is amongst the last 2 remaining coins. Measure one against a good coin. If balanced the last coin is bad, if not the coin on scale is bad.
(B) With the 4 coins on either side of the unbalanced scale, swap the top two coins to the other side. The scales will either stay unbalanced tipped to one side (i) or fall to the other side(ii). (i) The bad coin is amongst the bottom two coins on each side. The bad coin is either heavy and one of the coins on the lower side of the scale, or is lighter and among the bottom two coins on the higher side of the scale. Fix the scale in place before changing the coins around: Remove the top two coins on each side of scale. Replace one of the potential heavy coins from the lower side with a proven gold coin. Put one of the coins from the lighter side onto the heavier side and then put one of the proven gold coins onto the lighter side. There will be three possible outcomes. Either the scales are balanced, tipped to one side or the other, proving which coin is of different weight. (ii) Do the same thing with the top two coins which have been proven to contain the fake coin. 
francescarella
 Follow
 13 followers
 15 badges
 Send a private message to francescarella
 PS Helper
Offline15ReputationRep: Follow
 63
 07122010 15:24
wait, am I being crazy or are the scales some sort of red herring? surely if you're picking up the weights and putting them on the scales...you can feel their weight yourself anyway...?
I think i am actually going mad. 
 Follow
 64
 07122010 15:30
(Original post by francescarella)
wait, am I being crazy or are the scales some sort of red herring? surely if you're picking up the weights and putting them on the scales...you can feel their weight yourself anyway...?
I think i am actually going mad. 
 Follow
 65
 07122010 15:50
The problem most people have with this solution is that they try and solve it by elimation in three steps and by dividing the coins into groups of 3,4 or 6
The easiest way to solve it is to come up with three weighings the coins to narrow it down, looking at it, you have three possible results  L left heavier, R right heavier, E both even, so if you number each coin (in washable black marker so that they can wash out) 112 and weigh 8 at a time you can create a list of results ELR LER etc etc that will identify which coin is the fake, regardless of whether or not it's heavier or lighter
I could work this out, but knowing TSR I'll be accused of cheating and googling the answer, so there's no point, all I'll say is if you google the answer i bet the three weighings look something like
{1,2,3,4}{5,6,7,8}
{1,2,8,9}{5,6,10,12}
{1,7,9,11}{2,6,8,10}
and with a list of results that each correspond to a particular coin being fake
NOTE THAT THE ABOVE, UNLESS I'VE BEEN INCREDIBLY LUCKY AT GUESSING IS NOT THE CORRECT SOLUTION.
But with this method in mind maybe some of you that are really keen can work it out, I'm gonna do it but I probably won't post my solution since it'll no doubt be the exact same as google's and thus i'll be wasting my time 
The Cornerstone
 Follow
 5 followers
 2 badges
 Send a private message to The Cornerstone
Offline2ReputationRep: Follow
 66
 07122010 16:01
th;dr guess what that means

WhatIsAUsername?
 Follow
 0 followers
 10 badges
 Send a private message to WhatIsAUsername?
 Visit WhatIsAUsername?'s homepage!
Offline10ReputationRep: Follow
 67
 07122010 16:08
(Original post by HistoryRepeating)
Divide the coins in half, 6 coins in pile A and 6 in pile B
1) Split Pile A in half and weigh 3 on each side of the scale. If they weigh the same they are all gold and the fake is in B, if they weight differently the fake is in A. Lets say the fake is in B, so A is all gold (note: this doesnt make a difference to the proof, if the fake is in A just swap A and B in all the below reasoning, I've just done it for ease)
2) Take the 6 B (with the fake in them), split it in half. weigh one half against any 3 of the A, gold coins. If they weigh the same they are all gold and can be added to A and the fake is in the other half, if they weigh differently one of them is fake AND you know whether the fake is heavier or lighter than gold.
3) Take the half (3 coins) with the fake in and pick any two of them to weight against each other. If they weigh the same the third (unweighed one) is the fake, if they weigh differently, the one that is heavier or lighter (as found out in step 2 above) is the fake.
Coming up with this solution took me 4 minutes with a pen and paper from first principles, I've never done a problem like this before and I didnt cheat. 
fat_hampster
 Follow
 0 followers
 1 badge
 Send a private message to fat_hampster
Offline1ReputationRep: Follow
 68
 07122010 16:22
(Original post by looking)
Okay.
Start off by putting 4 coins on each side of the scales and measure.
If the 4 coins balance then proceed to (A) if not proceed to (B).
(A) Add one coin to either side of the scales. Either the scales stay balanced (i) or they become tipped (ii). (i) The scales are balanced therefore the bad coin is one of the two coins not on the scales. Measure one of these remaining coins against a real one. If balanced the last coin is bad, if unbalanced the coin on the scale is bad. (ii) The bad coin is amongst the last 2 remaining coins. Measure one against a good coin. If balanced the last coin is bad, if not the coin on scale is bad.
(B) With the 4 coins on either side of the unbalanced scale, swap the top two coins to the other side. The scales will either stay unbalanced tipped to one side (i) or fall to the other side(ii). (i) The bad coin is amongst the bottom two coins on each side. The bad coin is either heavy and one of the coins on the lower side of the scale, or is lighter and among the bottom two coins on the higher side of the scale. Fix the scale in place before changing the coins around: Remove the top two coins on each side of scale. Replace one of the potential heavy coins from the lower side with a proven gold coin. Put one of the coins from the lighter side onto the heavier side and then put one of the proven gold coins onto the lighter side. There will be three possible outcomes. Either the scales are balanced, tipped to one side or the other, proving which coin is of different weight. (ii) Do the same thing with the top two coins which have been proven to contain the fake coin.
I'm going to write out my solution in pseudocode, so that hopefully it is easier to understand.
firstly seperate the coins into 3 groups, a,b,c each of 4 coins a1,a2,...,b1,...,c4
notationally a(1,2,4) means coins a1 + a2 + a4. a means a(1,2,3,4)
weight(x,y) returns = if scales with x on one side and y on the other balance, < if x is lighter, > if x is heavier.
okay that should be enough notation.
x1 = weight(a,b)
if x1 == '=' then {
....x2 = weight(a(1,2,3),c(1,2,3))
....if x2 == '=' then { return c4.heavy}
....else if x2 == '<'{
........x3 = weight(c1, c2)
........if x3 == '=' then {return c3.heavy}
........else if x3 == '<' then {return c2.heavy}
........// symmetrical case for x3 >
....}
....//symmetrical case for x2 >
}
else if x1 == '<' then {
....x2 = weight(c(1,2) + a1 + b1, a(2,3) + b(2,3))
....if x2 == '=' then{
........x3 = weight(a4,c1)
........if x3 == '=' then {return b4.heavy}
........else if x3 =='<' then {return a4.light}
....}
....else if x2 == '<' then{
........x3 = weight((b2,b3)
........if x3 == '=' then {return a1.light}
........else if x3 == '<' then {return b3.heavy}
........// symmetrical case for >
....}
....// symmetrical case for>
}
returns fake coin and whether it is heavy or light.Last edited by fat_hampster; 07122010 at 16:24. 
 Follow
 69
 07122010 16:22
(Original post by fat_hampster)
...
{1,2,3,4}{5,6,7,8}{9,10,11,12}
STEP 1
12=Equal
{9101112} includes fake (Go to Step 2(a))
12=Unequal
{18} includes fake (Go to Step 2(b))
STEP 2(a)
{91011}{1,2,3}
Equal12 is fake (Go to 3a)
Unequal  {911} is fake {Go to 3b}
[if {911} heavier than {13}, fake is heavy, if lighter, fake is light}}
STEP 2(b)
Weigh {1,2,5,6}{4,8,9,10}
If equal then fake contained in {3,7} (Step 3(c))
If unequal then fake contained in {1,2,4,5,6,8} (Go to Step(d))
STEP 3(a)
Weigh 12 against 1 to show if heavier or lighter
STEP 3(b)
Weigh 9 against 10
If even 11 is fake
If uneven, if in step 2 fake was revealed to be lighter, lighter coin is fake, if revealed to be heavier, heavier coin is fake
STEP 3(c)
Weigh 1 against 3
If even 7 is fake (Heavier or lighter??)
If uneven, 3 is fake, and weight determined
STEP 3(d)
This was the step I didn't understand
You said that if {4,8,9,10} was lighter than {1,2,5,6}, then either 4 is fake or 5 or 6 are fake, but there's been no reason as of yet to rule out 1,2 or 8
[quote]
My solution (I don't think I've missed anything)
split the coins into 3 groups of 4 a,b,c.
weight a vs b.
either (a = b
in which case the fake is in c, then weigh 3 coins from c, against if the weighing is equal then the last coin is the fake, if the weighing is unequal, say the 3 in c are lighter than the 3 in a (symmetrical case for heavier) then weigh two of the weighed coins in c, either the lighter one is fake, or if equal the third coin is fake)
otherwise (a<b (symmetrical case for a>b) either fake is in a and is lighter, or fake is in b and is heavier. weigh two coins from c, plus 1 from a, plus 1 from b, against two from a, and two from b. if equal (then weigh last a against coin from c, if != then that a is fake, otherwise, last b is fake) otherwise (2c + b + a side < 2a + 2b side (or symmetrical case) then fake is amongst a on left, or 2bs on right. weigh the 2 b's against each other, if equal then the a is fake, otherwise the heavier of the 2 bs is fake)
[\quote]
So from what I gather it doesn't work for all possibilities combinations, nor does it identify whether or not 7 is heavier or lighter if it is the fake (using the numbering system i used) which the problem asks of youLast edited by munn; 07122010 at 16:24. 
fat_hampster
 Follow
 0 followers
 1 badge
 Send a private message to fat_hampster
Offline1ReputationRep: Follow
 70
 07122010 16:37
(Original post by munn)
I found it difficult to follow your solution so i tried writing it out my way
{1,2,3,4}{5,6,7,8}{9,10,11,12}
STEP 1
12=Equal
{9101112} includes fake (Go to Step 2(a))
12=Unequal
{18} includes fake (Go to Step 2(b))
STEP 2(b)
Weigh {1,2,5,6}{4,8,9,10}
If equal then fake contained in {3,7} (Step 3(c))
If unequal then fake contained in {1,2,4,5,6,8} (Go to Step(d))
STEP 3(d)
This was the step I didn't understand
You said that if {4,8,9,10} was lighter than {1,2,5,6}, then either 4 is fake or 5 or 6 are fake, but there's been no reason as of yet to rule out 1,2 or 8
So from what I gather it doesn't work for all possibilities combinations, nor does it identify whether or not 7 is heavier or lighter if it is the fake (using the numbering system i used) which the problem asks of you
The point is that weighings 1 and 2 combined narrows it down to 3 coins. if a < b then either one of the coins in a is lighter, or one of the coins in b is heavier. Coin 7 in your example, will be heavy if a < b and light if b < a.
in step 2(b)
If unequal by < & a < b (in first weighing) then fake contained in {1,2,8} (either 1 or 2 is light of 8 is heavy).
We gained information in the first weighing, and it's important to use all of it. 
 Follow
 71
 07122010 16:46
(Original post by fat_hampster)
If in step 2, the two sets you weight against each other are the same weight, then you haven't found out whether the fake is heavier or lighter in the final step.
My solution (I don't think I've missed anything)
split the coins into 3 groups of 4 a,b,c.
weight a vs b.
either (a = b
in which case the fake is in c, then weigh 3 coins from c, against if the weighing is equal then the last coin is the fake, if the weighing is unequal, say the 3 in c are lighter than the 3 in a (symmetrical case for heavier) then weigh two of the weighed coins in c, either the lighter one is fake, or if equal the third coin is fake)
otherwise (a<b (symmetrical case for a>b) either fake is in a and is lighter, or fake is in b and is heavier. weigh two coins from c, plus 1 from a, plus 1 from b, against two from a, and two from b. if equal (then weigh last a against coin from c, if != then that a is fake, otherwise, last b is fake) otherwise (2c + b + a side < 2a + 2b side (or symmetrical case) then fake is amongst a on left, or 2bs on right. weigh the 2 b's against each other, if equal then the a is fake, otherwise the heavier of the 2 bs is fake)
hope that makes sense, I'll try to type up a clearer version if I get time. 
 Follow
 72
 07122010 19:18
(Original post by fat_hampster)
The problem in the OP does not require whether it is heavier of lighter, but my solution does provide this.
The point is that weighings 1 and 2 combined narrows it down to 3 coins. if a < b then either one of the coins in a is lighter, or one of the coins in b is heavier. Coin 7 in your example, will be heavy if a < b and light if b < a.
in step 2(b)
If unequal by < & a < b (in first weighing) then fake contained in {1,2,8} (either 1 or 2 is light of 8 is heavy).
We gained information in the first weighing, and it's important to use all of it.
Here's mine, 27 possible combinations of weighing 3 sets of 4.
If we consider that there are 12 coins, then since the fake can be either light or heavy, there are 24 possible answers, 1L,1H 2L,2H etc
If we weigh the 3 groups of 4 seperately, there are 27 different combinations of results we can have
LLL
LLE
LLR
LRL
LRE
LRR
LEL
LER
LEE
RLL
ELL
LRR
LRE
LER
LEE
RLR
RLE
ELR
ELE
RRL
REL
ERL
EEL
RRR
RRE
RER
ERR
REE
ERE
EER
EEE
If we exclude LLL RRR and EEE that gives us 24 possible combinations to use
By assigning a result to each of these combinations 1L being 1 being fake and light, 1H fake and heavy, then we can work out (slowly) which three weighings we should make to find the fake coin.
Obviously since 1 is either heavy or light, if 1L is LLR, then 1H should be RRL as 1 is the results would be mirrored, also, my first 4 choices put coins{1,2,3,4} as heavy coins and the first weighing makes the left side heavy, so when putting 5H in, it cannot be in a combination Lxx, though 5L can be as it would obviously be in the right hand scale
Thus I've chosen:
LLE 1H
LLR 2H
LRL 3H
LER 4H
LRR 5L
LEE 6L
LRE 7L
LEL 8L
RRE 1L
RRL 2L
RLR 3L
REL 4L
RLL 5H
REE 6H
RLE 7H
RER 8H
ERR 9H
ELR 10L
ELE 11L
EEL 12H
ELL 9L
ERL 10H
ERE 11H
EER 12L
Hence we can (slowly) work out which 3 groups to choose for these results.
We only need to use the results for the Hs since the Ls are simply the opposite result.
LLE 1H
LLR 2H
LRL 3H
LER 4H
RLL 5H
REE 6H
RLE 7H
RER 8H
ERR 9H
ERL 10H
ERE 11H
EEL 12H
I specifically chose the results to make the first weighing
{1,2,3,4}L against {5,6,7,8}R
So from weighing 2:
LLE is 1H, so 1 is on the left in the second weighing (not in the third weighing)
LLR is 2H so 2 is on the left in the second weighing (on right in third)
LRL is 3H so 3 is on the right in the second weighing (on left in third)
LER is 4H, so 4 is not in the second weighing (on right in third)
RLL is 5H so 5 is on the left in the second weighing (on left in third)
REE is 6H so 6 is not in the second or third weighing
RLE is 7H so 7 is on the left in second weighing (not in third)
RER is 8H so 8 is not in the second weighing (on right in third)
ERR is 9H so 9 is on the right in the second weighing (on right in third)
ERL is 10H so 10 is on the right in second weighing (on left in third)
ERE is 11H so 11 is on the right in second weighing (not in third)
EEL is 12H so 12 is not in second weighing (on left in third)
Hence our second weighing should be:
{1,2,5,7} against {3,9,10,11}
and our third weighing should be:
{3,5,10,12} against {2,4,8,9}
So
{1,2,3,4}{5,6,7,8}
{1,2,5,7}{3,9,10,11}
{3,5,10,12}{2,4,8,9}
And the key above will tell you which one is fake going by your results.
Try it out, pick a fake number choose its weight and the key should agree with the results you'd get if you weigh it.
Tell me if theres a mistake, it took a bit of trial and error, I for ages had 4H as LEL and 8H as REL which gave me 6 results for L in the third weighing and 2 on the right, but once i switched 4H with 8L and 8H with 4L it seemed to work out.
So much for me not posting a solution
I imagine there are a large number of possible solutions for this depending on what your first choices areLast edited by munn; 07122010 at 19:22. 
vahik92
 Follow
 4 followers
 0 badges
 Send a private message to vahik92
 Thread Starter
Offline0ReputationRep: Follow
 73
 07122010 20:22
(Original post by Aurora.)
Hmm...Spoiler:ShowPut 5 coins on each side of the scale. If they balance, one of the two left is the fake.
Then you just have to test one of the real coins against the first one that's left, and if that balances then it's the other one. I think.
Right? 
vahik92
 Follow
 4 followers
 0 badges
 Send a private message to vahik92
 Thread Starter
Offline0ReputationRep: Follow
 74
 07122010 20:24
(Original post by asdfg0987)
If you were smart you'd have just googled it. 
vahik92
 Follow
 4 followers
 0 badges
 Send a private message to vahik92
 Thread Starter
Offline0ReputationRep: Follow
 75
 07122010 20:27
(Original post by HistoryRepeating)
Divide the coins in half, 6 coins in pile A and 6 in pile B
1) Split Pile A in half and weigh 3 on each side of the scale. If they weigh the same they are all gold and the fake is in B, if they weight differently the fake is in A. Lets say the fake is in B, so A is all gold (note: this doesnt make a difference to the proof, if the fake is in A just swap A and B in all the below reasoning, I've just done it for ease)
2) Take the 6 B (with the fake in them), split it in half. weigh one half against any 3 of the A, gold coins. If they weigh the same they are all gold and can be added to A and the fake is in the other half, if they weigh differently one of them is fake AND you know whether the fake is heavier or lighter than gold.
3) Take the half (3 coins) with the fake in and pick any two of them to weight against each other. If they weigh the same the third (unweighed one) is the fake, if they weigh differently, the one that is heavier or lighter (as found out in step 2 above) is the fake.
Coming up with this solution took me 4 minutes with a pen and paper from first principles, I've never done a problem like this before and I didnt cheat. 
 Follow
 76
 07122010 20:30
(Original post by vahik92)
yes, but what if the 10 that you weigh are not balanced? 
vahik92
 Follow
 4 followers
 0 badges
 Send a private message to vahik92
 Thread Starter
Offline0ReputationRep: Follow
 77
 07122010 20:30
(Original post by danny111)
This guy has it. 
vahik92
 Follow
 4 followers
 0 badges
 Send a private message to vahik92
 Thread Starter
Offline0ReputationRep: Follow
 78
 07122010 20:31
(Original post by Converse)
Nice. +Rep. 
James Gregory
 Follow
 3 followers
 0 badges
 Send a private message to James Gregory
Offline0ReputationRep: Follow
 79
 07122010 20:34
(Original post by vahik92)
if this is addressed to me, then i solved the problem myself because it is fun, and besides  i dont think this question is on the internet at all because i did a research., albeit not a deep one 
vahik92
 Follow
 4 followers
 0 badges
 Send a private message to vahik92
 Thread Starter
Offline0ReputationRep: Follow
 80
 07122010 20:35
(Original post by James Gregory)
This doesn't really prove who is most intellectual or logical, but assuming he isn't lying and that he really did do it in 4 minutes from first principles, then it does prove that HistoryRepeating is very good at discrete maths. Though quite likely he is big headed enough already.
Also, I really wish I had kept trying to see how long it took me to do, rather than just giving up after 2 minutes :/
Reply
Submit reply
Related discussions:
 TSR Member you'd most like a coffee with and why
 TSR user whose posts you enjoy the most!
 TSR Bollywood Society
 Do you believe you are more intelligent than other people on ...
 TSR is a forum where males are more vocal, and abuse ...
 Why is everyone on here so smart?
 Rightwing factions seeking to run debate on TSR?
 Black girls & TSR.
 "The only true wisdom is in knowing you know nothing" The ...
 Mechanical Engineers of TSR
TSR Support Team
We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.
This forum is supported by:
Updated: December 9, 2010
Share this discussion:
Tweet