Weighted coin problem.

Iancar29

During the lecture of this problem one of the students had to tell her how to do it , thats how bad it was at times.

So ye , any help or steps how to go about it would be great guys , thanks.

Btw i know the number of coins can differ but ye , heres this example..


Five coins are identical in appearance, but on coin is either heavier or lighter than the others, which all weigh the same . Draw a decision tree that gives an algorithm that identifies in at most three weighings that bad coin and determine whether it is heavier or lighter than the others using only a pan balance.

I know obviously we cant draw here . So even links to a good explanation or something would be much appreciated , i just hate how its worded considering my dyslexia . Thanks in advance.

Michael Collins

Take any 4 coins, split into 2 groups of 2 and weigh them. If the scale doesn't balance then your 'different' coin must be among this group of 4, if not it must be the coin you didn't weigh, agree?

Now to determine which group of 2 above your coin is in. Take either group of 2 and separate into 1 coin on each side. If the scale doesn't balance, the different coin must be in this group.

Now have a go at what happens next yourself!

Iancar29

Michael Collins wrote: »

Take any 4 coins, split into 2 groups of 2 and weigh them. If the scale doesn't balance then your 'different' coin must be among this group of 4, if not it must be the coin you didn't weigh, agree?

Now to determine which group of 2 above your coin is in. Take either group of 2 and separate into 1 coin on each side. If the scale doesn't balance, the different coin must be in this group.

Now have a go at what happens next yourself!

Thanks pal! , very easily explained.

So assuming the odd coin is among coins 1-4

Weighing A(1& 2) ..... and B (3 & 4 )

if A is balanced then odd coin is either 3 or 4
if A is not balanced then odd coin is either 1 or 2

asssuming A is balanced weigh 3 or 4 against 1 or 2 ...
so say 3 & 1... if thats balances then odd coin is 4.
If not then odd coin is 3.

Would i also have to have the separate tree to show the 1 or 2 coin being the odd coin also?

Thanks for your help

Delphi91

I think you're going overboard with your weighings there. The most you can have is three weighings.

Using your notation, let A = coins 1 & 2 and B = coins 3 & 4. Leave coin 5 out on its own.

1. Place group A on one side of the balance and group B on the other
2. There are three possible outcomes:
   [LIST=2]
3. If the scales balance, then the heavier coin is coin 5
4. If group A is heavier than group B, then the heavier coin is either coin 1 or coin 2. Place the two coins from group A on either side of the balance - the heavier side side corresponds to the heavier coin
5. If group B is heavier than group A, then the heavier coin is either coin 3 or coin 4. Place the two coins from group B on either side of the balance - the heavier side side corresponds to the heavier coin

[/LIST]

MathsManiac

Delphi91 wrote: »

I think you're going overboard with your weighings there. The most you can have is three weighings.

Using your notation, let A = coins 1 & 2 and B = coins 3 & 4. Leave coin 5 out on its own.

1. Place group A on one side of the balance and group B on the other
2. There are three possible outcomes:
   [LIST=2]
3. If the scales balance, then the heavier coin is coin 5
4. If group A is heavier than group B, then the heavier coin is either coin 1 or coin 2. Place the two coins from group A on either side of the balance - the heavier side side corresponds to the heavier coin
5. If group B is heavier than group A, then the heavier coin is either coin 3 or coin 4. Place the two coins from group B on either side of the balance - the heavier side side corresponds to the heavier coin

[/LIST]

But this is not a correct solution, because you have assumed that the odd coin is heavier than the others rather than lighter. In OP's problem, all you are told is that there is one coin that is EITHER heavier OR lighter, but you don't know which. As well as identifying the dodgy cpin, you also have to determine whether it is heavier or lighter than the others.

MathsManiac

Michael Collins's suggestion will get you there, but don't forget the second part of the task. For example, if the first weighing is balanced, so that you know the remaining coin is odd, you still need to use another weighing to decide whether it's heavier or lighter than the others.

Similarly, if the scales are unbalanced in the first weighing, it's not enough to just note that they are different, you also need to note which pair was heavier. Taking the information "The odd one is one of these two" into the second weighing is not enough. You need to be taking in information like: "One of these two is heavier than all the other coins, or else one of those two is lighter than all the other coins". Only after you answer this with the second weighing can you fully answer the question with the third.

Interestingly, it's possible to identify one odd coin among twelve with only three weighings, even when, as in this case, you don't know in advance whether it's heavier or lighter.

Delphi91

MathsManiac wrote: »

But this is not a correct solution, because you have assumed that the odd coin is heavier than the others rather than lighter. In OP's problem, all you are told is that there is one coin that is EITHER heavier OR lighter, but you don't know which. As well as identifying the dodgy cpin, you also have to determine whether it is heavier or lighter than the others.

Good point, didn't read the problem carefully!

Rubecula

A = (1 + 2)
B = (3 + 4)
C = (1 + 5)
D = (2 + 5)

weigh A against B if both the same then the odd coin must be 5. If not then you now weigh C against B if both the same then the odd coin is 2. If not the same you weigh D against B. If both the same then the odd coin must be 1. If it is still unequal the odd coin must be in group B.

Weigh coin 3 against any of 1, 2, or 5. If they are the same it must be 4 if it is not the same then 3 is the odd coin and this can be verified with a measure against any of the remaining coins.

Obviously by weighing them and finding the difference you will also know whether it is lighter or heavier than a real coin.

MathsManiac

Rubecula wrote: »

A = (1 + 2)
B = (3 + 4)
C = (1 + 5)
D = (2 + 5)

weigh A against B if both the same then the odd coin must be 5. If not then you now weigh C against B if both the same then the odd coin is 2. If not the same you weigh D against B. If both the same then the odd coin must be 1. If it is still unequal the odd coin must be in group B.

Weigh coin 3 against any of 1, 2, or 5. If they are the same it must be 4 if it is not the same then 3 is the odd coin and this can be verified with a measure against any of the remaining coins.

Obviously by weighing them and finding the difference you will also know whether it is lighter or heavier than a real coin.

But this strategy does not solve the problem in at most three weighings. (After your third sentence, you have used your three weighings and yet the problem is not finished.)

hivizman

MathsManiac wrote: »

Interestingly, it's possible to identify one odd coin among twelve with only three weighings, even when, as in this case, you don't know in advance whether it's heavier or lighter.

This takes me back.

I was introduced to this problem when I was at school, in the idle days that filled the time between the end of examinations and the end of the school year. My maths teacher introduced us to an algorithmic approach for working out three weighings of four coins against four coins that would identify the odd coin and whether it was lighter or heavier depending on the outcomes of the three weighings. Basically, each weighing can have one of three outcomes (left side goes down = 0, weighing balances = 1, right side goes down = 2), and the three weighings give you enough possibilities to match uniquely the 24 possible situations (12 coins multiplied by two possibilities for the odd coin) with 24 possible outcomes of the weighing process.

Also, the method generalises to n weighings, where the number of coins that can be involved is given by (3^n - 3)/2. So you can detect the odd coin, and whether it is heavier or lighter, out of 39 coins with 4 weighings, out of 120 coins with 5 weighings, and so on.

Some years later, I was discussing the 12-coin problem with a friend who had a maths degree, and he presented a solution that involved a complicated decision tree with subsequent weighings depending on the outcome of previous weighings. We were both delighted to work out that his solution and mine were actually isomorphic.

The general formula above tells us that we can assess three coins with two weighings (weigh coin 1 against coin 2 and then coin 2 against coin 3 - if the first weighing balances, then coin 3 is odd and the second weighing tells us whether coin 3 is heavier or lighter than the normal coin 2; if the first weighing doesn't balance, then coin 3 is normal and the second weighing tells us whether coin 2 is lighter, heavier or normal, in the last case implying that coin 1 is odd, so the first weighing tells us whether coin 1 is lighter or heavier).

With four coins, we need three weighings. We have to weigh two coins against the other two coins to begin with (if we weigh one against one, then two weighings allows us to decide whether the odd coin is one of coins 1, 2 and 3, and, if so, whether the odd coin is light or heavy, but if both the first two weighings balance, then we know the odd coin is coin 4 but we need a third weighing to determine whether coin 4 is lighter or heavier). But this weighing can have only one of two outcomes - (a) either one of coins 1 and 2 is lighter or one of coins 3 and 4 is heavier, or (b) either one of coins 1 and 2 is heavier or one of coins 3 and 4 is lighter. A second weighing, say coin 1 against coin 2, allows us to tell whether coin 1 is lighter or heavier than coin 2 (which implies that coins 3 and 4 are normal), or the same weight (which implies that coins 1 and 2 are normal). In either case, we need to weigh one of the two coins 1 and 2 against one of the two coins 3 and 4 to get enough information to identify the odd coin and whether it is lighter or heavier.

Is there a general proof that shows that, for all numbers of coins between 4 and 12, we need three weighings to identify the odd coin and whether it is lighter or heavier? Or is there a counter-example where we need more than three weighings? Is there a general algorithm for determining the actual sequence of weighings, or do we have to work it out for each number of coins through logic-informed trial and error?

Iancar29

Heres the descision tree format for a 12 coin problem..



I rather not do a long one like this as it easy to makes mistakes... 9 or less im ok with..

hivizman

Number the coins from 1 to 12.

For each weighing, record "0" if the left side of the balance goes down, "1" if the weighing balances and "2" if the right side of the balance goes down.

Weighing 1: 1,3,4,5 against 2,6,7,8

Weighing 2: 1,6,7,8 against 2,9,10,11

Weighing 3: 2,3,8,11 against 5,6,9,12

Outcomes 000 and 222 are impossible because there is no coin on the same side in all three weighings. Outcome 111 is impossible because this would imply no odd coin. There remain 24 possible outcomes, which map onto the 24 possible values for the odd coin as follows:

001 1H 221 1L
002 2L 220 2H
010 3H 212 3L
011 4H 211 4L
012 5H 210 5L
020 6L 202 6H
021 7L 201 7H
022 8L 200 8H
100 9L 122 9H
101 10L 121 10H
102 11L 120 11H
110 12L 112 12H

The weighing sequence is quite similar to the decision tree. For example, if the first weighing shows a balance, we know that the odd coin is one of 9,10,11 and 12. The second weighing above is equivalent to the second weighing in this situation in the decision tree (three coins known to be true against coins 9, 10, and 11 is equivalent to four coins known to be true against coins 9, 10 and 11 and a fourth coin known to be true). The third weighing then incorporates both a comparison of coins 9 and 11 (equivalent to the comparisons of coins 9 and 10 in the decision tree with renumbering of the coins), if the second weighing is unbalanced, and a comparison of coin 12 with a coin known to be true, if the second weighing is balanced - in either situation, the other coins in the weighings above will be true so won't affect the comparisons.

The assignment of coins to the three weighings is determined by writing the numbers from 1 to 12 in ternary notation together with their complements (where 0 is rewritten as 2, 1 as 1 and 2 as 0). It's necessary to ensure that there are exactly four coins on each side of each weighing and four omitted from each weighing. This is done by selecting either the ternary representation of the number or the complement to represent the odd coin being heavy.

The selection is made by looking at the sequence of numbers and selecting the sequence where the digits "ascend" rather than "descend" - that is, the digits follow the cyclical order 0-1-2-0 rather than 0-2-1-0. So, for coin 1, we select 001 as "heavy" but for coin 2, we select 220 as "heavy", because 002 follows the descending cyclical order. Note that, once we make a decision based on the first digits, we ignore subsequent digits, so the "heavy" allocation for 6 is 202, which begins by following the ascending order, even though the last two digits follow the descending order.

The same approach can be applied for 39 coins in 4 weighings and 120 coins in 5 weighings, and so on.

The problem with this approach is that it's not obvious how you would apply it to numbers of coins other than those representing the maximum coins for different numbers of weighings. On the other hand, once you have a clear grasp of how to apply the decision tree approach, this can be used for any number of coins.

MathsManiac

...and one can try out one's strategy here: http://nrich.maths.org/5796

hivizman

MathsManiac wrote: »

...and one can try out one's strategy here: http://nrich.maths.org/5796

Many thanks for this link.

Looking at my earlier post, there is an underlying logic. The twelve coins are in effect divided into four groups of three: {1,2,12}, {3,4,5}, {6,7,8} and {9,10,11}. The solution could be written as a decision tree - which I've set out in words rather than try to draw.

The outcomes of the first weighing provide the following information:

(A) Left side of scale goes down: odd coin must be 1H, {3,4,5}H, 2L or {6,7,8}L
(B) Scale balances: odd coin must be {9,10,11} or 12 (can't tell whether H or L).
(C) Right side of scale goes down: odd coin must be 1L, {3,4,5}L, 2H or {6,7,8}H

The second weighing narrows the possibilities:

(A) In weighing 1, left side of scale went down:

(A1) Left side of scale goes down: odd coin must be 1H or 2L (from first weighing, {9,10,11} and 12 must be true, and{3,4,5} must be true - otherwise scale would balance given that these are omitted from the second weighing - and {6,7,8} must be true - can't both be light from weighing 1 and heavy from weighing 2).
(A2) Scale balances: odd coin must be {3,4,5}H as these coins were in weighing 1 but not weighing 2.
(A3) Right side of scale goes down: odd coin must be {6,7,8}L.

(B) In weighing 1, scale balanced:

(B1) Left side of scale goes down: odd coin must be {9,10,11}L.
(B2) Scale balances: odd coin must be 12, but we don't yet know whether this is L or H.
(B3) Right side of scale goes doen: odd coin must be {9,10,11}H.

(C) In weighing 1, right side of scale went down:

(C1) Left side of scale goes down: odd coin must be{6,7,8}H
(C2) Scale balances: odd coin must be {3,4,5}L
(C3) Right side of scale goes down: odd coin must be 1L or 2H.

The third weighing needs to be no more than a weighing of one coin against another, but the actual weighing {2,3,8,11} against {5,6,9,12} does all the weighings in one go - which one is actually relevant is contingent on the outcomes of the first two weighings. Depending on the outcome of the previous weighings, we have narrowed the possible outcomes down to the odd coin being in one of the four groups. For the three groups {3,4,5}, {6,7,8} and {9,10,11}, we know whether the odd coin is heavy or light. Weighing one coin from each group against another coin tells us which is the odd coin from the group (if the scale balances, then the odd coin is the one left out of the comparison).

So the final weighing is comparing 3 with 5, 8 with 6 and 11 with 9. It is also comparing 2 with 12 - either 2 is true and 12 is odd, in which case this tells us whether 12 is heavy or light, or 12 is true and we know whether we have either (1H or 2L) or (1L or 2H).

Is this solution, with some relabelling of coins and possibly some reversals of the pans in which the coins are placed, effectively the same as that of Iancar29, or is it a distinct solution?

ZorbaTehZ

There is a famous solution to that problem, published in Eureka, by the Blanche Descartes collective: (F refers to Professor Felix Fiddlesticks)

F set the coins out in a row

And chalked on each a letter, so,

To fom the words 'F AM NOT LICKED'

(An idea in his brain had clicked.)

And now his mother he'll enjoin:

MA DO LIKE

ME TO FIND

FAKE COIN

hivizman

ZorbaTehZ wrote: »

There is a famous solution to that problem, published in Eureka, by the Blanche Descartes collective: (F refers to Professor Felix Fiddlesticks)

The solution is distinct from mine in the sense that it cannot be transformed into my solution by combinations of (a) renumbering the coins, (b) reordering the three weighings, and (c) reversing the sides of the scale in any particular weighings.

This can be seen by looking at the three coins that are in only one weighing and the three coins that appear in all three weighings.

In my solution, the three coins in only one weighing are 4, 10 and 12, and the three coins in all three weighings are 2, 6 and 8. Using the letter X to signify a coin in only one weighing, Y to signify a coin in exactly two weighings, and Z to signify a coin in all three weighings, my three weighings are:

(1) XYYY against YZZZ
(2) YYZZ against XYYZ
(3) YYZZ against XYYZ

In ZorbaTehZ's solution, the three coins in only one weighing are T, L and C, and the three coins in all three weighings are O, I and D. Using the same notation, Zorba's weighings can be represented as:

(1) YYYZ against XYZZ
(2) XYZZ against YYYZ
(3) YYYZ against XYZZ

There is no way of rearranging Zorba's weighings to give the same pattern as my weighings, so the two solutions must be distinct.

This raises the question: how many distinct solutions of the 12 coin problem are there? Note that we need consider only those solutions where there are four coins on both sides in all three weighings - we can convert any solution involving fewer than four coins on both sides by adding coins known to be true to make up the numbers. So the decision tree solution of Iancar29 can be converted into a "four against four" solution quite easily. Though is there a way of doing so that gives a solution isomorphic to any of the published "four against four" solutions?

hivizman

By the way, there are several other solutions on the internet (where the problem is sometimes referred to as the "12 balls puzzle"). Most of these follow a decision tree approach.

For example:

http://www.mathsisfun.com/pool_balls_solution.html

http://www.newton.dep.anl.gov/newton/askasci/1995/math/MATH007.HTM

http://www.cut-the-knot.org/blue/OddballProblem1.shtml (this gives a decision tree approach and also a slight variant of my "four against four" approach).

http://www.bikwil.com/Vintage06/Billiard-Ball-Puzzle.html

There is a Wikipedia article on the problem, which links not only to the playable version to which MathsManiac kindly provided a link but also to a general demonstration of whether solutions are possible for different formulations of the problem.