## Weighing coins! (electronic scale)

**Moderators:** jestingrabbit, Moderators General, Prelates

### Weighing coins! (electronic scale)

Okay. You have 5 coins. You have one scale. One of the coins is a fake and of a different mass. You must use 3 weighings only and you must be able to always find out which coin is fake. You cannot change the third weighing depending on the first and second weighings.

Oh... and the scale is electronic and it tells you the mass of whatever you put on it... You should also be able to find the real and fake masses Sorry if you thought it was a balance scale

Have fun! (yay my first post - I figure that's not a good thing...)

Oh... and the scale is electronic and it tells you the mass of whatever you put on it... You should also be able to find the real and fake masses Sorry if you thought it was a balance scale

Have fun! (yay my first post - I figure that's not a good thing...)

Last edited by Nab on Sat Aug 25, 2007 4:42 am UTC, edited 1 time in total.

Solution? wrote:Weigh four of the coins (a, b, c, d)

Weigh two of the four (a, b).

If the first weight does not equal twice the second then the 5th coin (e) is fake.

Otherwise weigh coins a, c and e

(a+b)/2=(a+c+e)/3 => d fake

Else....

(a+b+c+d)-(a+c+e) = b+d-e (d and e not fake) = b

b = (a+b)/2 => c is fake

Else....

(a+c+e)-(a+b) = c+e-b

if this is not equal to b then b is fake (we know c and e are not fake)

Else.....

a is fake

Edit: Realised the puzzle said the fake was a different weight, not necessarily lighter, so I rushed through the above to cover my stipidity! Hopefully it's right

Last edited by legato on Wed Jun 20, 2007 11:30 am UTC, edited 1 time in total.

I'm not a troll, I'm just an idiot

Hm... Can't see any flaws in that... Good work I have a slightly different solution.

New closely related problem: How many coins would it work for with 4 weighings? (no, I don't know... but it would be interesting )

New closely related problem: How many coins would it work for with 4 weighings? (no, I don't know... but it would be interesting )

Last edited by Nab on Wed Jun 20, 2007 1:43 pm UTC, edited 1 time in total.

Coins named A,B,C,D,E

Weigh A and let it's weight be x

Weigh B+C:

--If B+C != 2x

-----Let B+C = y

-----Weigh B

---------If B = x, then C is different and it's weight is y-x

---------Else let B = z

---------------If y = 2z, then A is different

---------------Else B is different and C = x

--Else Weigh D

-----If D=x, E is different

-----Else D is different

That should do it too.

Cuton

- gmalivuk
- GNU Terry Pratchett
**Posts:**26052**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

If you have a balance scale, and you *can* change your subsequent weighings based on the results of earlier ones, you can use k tests to completely solve (3^k-3)/2 coins. (Where one is fake and weighs differently, but you don't know whether it's heavier or lighter, and you don't start out with any known good coins to check against.) This was proven here.

Now, if you *can't* base your strategy on previous weighings, and you can't, in one step, tell whether one side or another is lighter, but you *can* find out exactly how much each side weighs, it's obviously different.

3 coins (the minimum for which the setup makes sense): 3 weighings. simplest is just weigh each coin one at a time. 2 weighings doesn't give you enough info.

4 coins: 3 weighings. ab, cd, ac.

5 coins:

6 coins: 4 weighings. ab, cd, ef, ace.

n coins: the only really interesting question of the lot. Go to it, people!

Mods: Can someone put a note in the subject line to say this is actually different from the one that usually gets posted?

(fixed because I misunderstood at first)

Now, if you *can't* base your strategy on previous weighings, and you can't, in one step, tell whether one side or another is lighter, but you *can* find out exactly how much each side weighs, it's obviously different.

3 coins (the minimum for which the setup makes sense): 3 weighings. simplest is just weigh each coin one at a time. 2 weighings doesn't give you enough info.

4 coins: 3 weighings. ab, cd, ac.

5 coins:

solution wrote:First two weighings are abc and cde. If these are the same, c is the bad coin, and the only requirement for a third weighing is that at least one known good coin is checked. If they're different (suppose abc is heavy), you know a or b is heavy, or d or e is light, and c is good. So what you need in a third weighing is to narrow down among these four. If you check ad next, and it's more than 2/3 the weight of abc, a is heavy. If it's less than 2/3 the weight of cde, d is light. If it's between these two weights, a and d are fine, and you can deduce whether b or e is bad based on the fact that three good coins would weigh 3/2 as much as the ad pair.

6 coins: 4 weighings. ab, cd, ef, ace.

n coins: the only really interesting question of the lot. Go to it, people!

Mods: Can someone put a note in the subject line to say this is actually different from the one that usually gets posted?

(fixed because I misunderstood at first)

gmalivuk wrote:3 coins (the minimum for which the setup makes sense): 2 weighings. a against b and c, then b against c.

The way I read the original question you couldn't compare weights like "a against b and c", only find the weight for each (eg weigh a, weigh b and c). If that's the case I think 3 coins would still take 3 weighings?

I'm not a troll, I'm just an idiot

This is a bit of a guess, but I think you can get an answer for twice as many coins as weighings eg for 4 weighings 8 coins:

That way you can use the first w-1 weighings to get the pair the fake is in and then the last weighing to work out which it is.

That could well be improved on though...

Code: Select all

`A B C D E F G H`

x x x x x x

x x x x

x x

x x x x

That way you can use the first w-1 weighings to get the pair the fake is in and then the last weighing to work out which it is.

That could well be improved on though...

I'm not a troll, I'm just an idiot

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

Weigh any two coins seperately as weighings one and two. Weigh the entire collection of coins as weighing three. If the two coins both weigh x, and total weight of all coins together is Z, then the lighter coin weighs Z-(n-1)x. If the two coins weigh x and y with x and y different, then either (n-1)x+y=Z or x+(n-1)y=Z. Either way, you know which coin is the odd one out.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

Proof that 3 is optimal for n>2:

(For n=2, 2 is obviously sufficient, and for n=1, 1 is obviously sufficient.)

You always need to weigh every coin at least once in order to guarantee the odd coin is weighed, and you need to weigh a proper subset at least once, or else you can't tell the seperate weights. Your two groups could always differ by only regular coins or by special coins, so you need a third weighing to tell these two cases apart (except in the n=2 case, where both coins are "special"), so three weighings is possible and optimal for any n>2.

My previous solutions assumed the scale had no maximum weight (so it could weigh all coins at once, for any n). If the scale has a maximum weight, and can only weigh up to a certain number of coins simultaneously without breaking, then the minimum number of weighings is either the number of weighings needed to ensure that every coin is weighed at least once, or three, whichever is more. This is obviously the least possible, since bad luck would have you not even weigh the odd coin until the last weighing, in which case you have no hope, and I've already proved that at least three weighings are needed. On the other hand, with enough weighings to weigh everything, you can weigh the same number of coins in two different weighings of disjoint subsets of coins, and then weigh the rest of the coins in disjoint subsets. If the two subsets with the same number of coins weigh the same, you know the usual mass, and can figure everything else out from that. If they weigh differently, every other weighing contains only ordinary coins, so you can again figure out the ordinary coin mass, and everything else out from that.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

Skep--the way I read your solution, you're weighing A, B, and ABCDE; how are you going to tell which of C, D, & E is fake?

Edit: Argh--I'm one post behind skeptical scientist. The above was a response to his first one.

Edit: Argh--I'm one post behind skeptical scientist. The above was a response to his first one.

Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

EricH wrote:Skep--the way I read your solution, you're weighing A, B, and ABCDE; how are you going to tell which of C, D, & E is fake?

Edit: Argh--I'm one post behind skeptical scientist. The above was a response to his first one.

Oh, right. I was only getting the separate weights, and not determining which coin was which.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

Blatm wrote:skeptical scientist wrote:...You always need to weigh every coin at least once in order to guarantee the odd coin is weighed...

Why? If you weigh all the coins but one, and all their weights are equal, you know that the last one is the odd one out, without weighing it, don't you?

One of the requirements is to find out the weights of the two varieties of coin. You need to weigh the odd coin to do so.

"With math, all things are possible." —Rebecca Watson

- gmalivuk
- GNU Terry Pratchett
**Posts:**26052**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

aguacate wrote:gmalivuk wrote:4 coins: 3 weighings. ab, cd, ac.

I don't think this would work. Let's say d is the fake coin and is heavy. This is the result of your weighings: ab = ac < cd. Now suppose a is the fake coin and is light. Your weighings result again is ab = ac < cd

Right you are. I wasn't really thinking through the ones other than for 5 coins, since that was the original question.

legato wrote:This is a bit of a guess, but I think you can get an answer for twice as many coins as weighings eg for 4 weighings 8 coins:Code: Select all

`A B C D E F G H`

x x x x x x

x x x x

x x

x x x x

That way you can use the first w-1 weighings to get the pair the fake is in and then the last weighing to work out which it is.

That could well be improved on though...

Yeah, like by checking H at some point. Each coin needs to be weighed at least once or you can't both determine the bad coin and whether it's heavy or light.

skeptical scientist wrote:Blatm wrote:skeptical scientist wrote:...You always need to weigh every coin at least once in order to guarantee the odd coin is weighed...

Why? If you weigh all the coins but one, and all their weights are equal, you know that the last one is the odd one out, without weighing it, don't you?

One of the requirements is to find out the weights of the two varieties of coin. You need to weigh the odd coin to do so.

I think that what the topic starter meant was that the solution he had come up with involved weighing the odd coin.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26052**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

Is it possible to do 4 coins in 3 weighings?

3 and 5 coins, yes. 6 and 7 take 4, and above that we can use the fact that 2n or 2n+1 coins can be solved in one more test than n coins, and that 3n, 3n+1, and 3n+2 can be solved in two more than n. (Do whatever you do for n, but with pairs or trios of coins. Then, weigh one coin from each pair (along with the extra, if there is on), or one from each trio and then another from each trio.)

But the trouble I'm having is with 3 weighings for 4 coins, which I'm starting to think can't be done, even though 3 is enough for 5 coins.

3 and 5 coins, yes. 6 and 7 take 4, and above that we can use the fact that 2n or 2n+1 coins can be solved in one more test than n coins, and that 3n, 3n+1, and 3n+2 can be solved in two more than n. (Do whatever you do for n, but with pairs or trios of coins. Then, weigh one coin from each pair (along with the extra, if there is on), or one from each trio and then another from each trio.)

But the trouble I'm having is with 3 weighings for 4 coins, which I'm starting to think can't be done, even though 3 is enough for 5 coins.

gmalivuk wrote:Is it possible to do 4 coins in 3 weighings?

3 and 5 coins, yes. 6 and 7 take 4, and above that we can use the fact that 2n or 2n+1 coins can be solved in one more test than n coins, and that 3n, 3n+1, and 3n+2 can be solved in two more than n. (Do whatever you do for n, but with pairs or trios of coins. Then, weigh one coin from each pair (along with the extra, if there is on), or one from each trio and then another from each trio.)

But the trouble I'm having is with 3 weighings for 4 coins, which I'm starting to think can't be done, even though 3 is enough for 5 coins.

Solution wrote:Weigh abc, bcd and acd.

If abc=bcd=acd, c is fake.

If abc=bcd!=acd, b is fake.

If abc=acd!=bcd, a is fake.

If acd=bcd!=abc, d is fake.

You'd do just as well going

Not seeing any solutions for 4 w/ 3. Tested everything with a 3 or 4 weighing, but I might've missed something.

8 coins 4 weighings: (96.8584073464102% sure)

I might be able to edit it slightly for 9 coins, but I don't know yet

a, b, c or ab, bc, ab

Not seeing any solutions for 4 w/ 3. Tested everything with a 3 or 4 weighing, but I might've missed something.

8 coins 4 weighings: (96.8584073464102% sure)

Code: Select all

`A B C D E F G H`

X X X X X

X X X X X

X X X

X X X

And you only need to check A, B, and D!

I might be able to edit it slightly for 9 coins, but I don't know yet

Last edited by Nab on Thu Jun 21, 2007 2:18 am UTC, edited 1 time in total.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26052**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

Nab wrote:4 coins 8 weighings: (96.8584073464102% sure)

I'm even more sure than 96.8% that you meant 8 coins 4 weighings.

Also, I'm 100% sure you're right.

a is light, comparing average weight of the coins each time: 1<2=3=4

b light: 3<1<2=4

c light: 4<1<2=3

d light: 3<1=2=4

e light: 4<1=2=3

f light: 3<2<1=4

g light: 4<2<1=3

h light: 2<1=3=4

(If one of these is heavy instead, the inequalities switch, but the reversed orderings are unique as well.)

It still seems really strange that you can't do 4 in 3 weighings, though.

Edit: I don't think, though, that you can do 9 in only 4...

Code: Select all

`A B C D E F G H I`

X X X X X X

X X X X X X

X X X

X X X

Should always work... Simple to check because you're weighing either 3 or 6 at a time so it's only doubling and halving

- gmalivuk
- GNU Terry Pratchett
**Posts:**26052**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

Nab wrote:9 coins 4 weighings?Code: Select all

`A B C D E F G H I`

X X X X X X

X X X X X X

X X X

X X X

Should always work... Simple to check because you're weighing either 3 or 6 at a time so it's only doubling and halving

Indeed. When I thought about it last night, I think I concluded that you couldn't know whether E was heavy or light. But obviously you could, since the average coin weight in the first two tests would be lighter (though equal to each other) than in the last two (which are also equal to each other). So yeah, 9 in 4 works as well.

10 and 11 can also be done in 4, because 5 can be done in three.

Code: Select all

`ABCDEFGHIJ ABCDEFGHIJK`

XXXXXX XXXXXX

XXXXXX XXXXXX

XX XX XX XX

X X X X X X X X X X X

Pretty sure 12 needs 5 weighings, though.

Code: Select all

`A B C D E F G H I J K L`

X X X X

X X X X

X X X X

X X X X X X

X X X X X X

Everything up to 23 can also be done in 5, since 6 to 11 can be done in 4. So we've got the following so far:

3 weighings: 3 or 5 coins

4 weighings: 4 or 6-11 coins

5 weighings: 12-23 coins

n weighings: up to 3*2^(n-2) coins, except 4, which needs 4 weighings

(not sure if this is last is always optimal, though. it would make sense for higher numbers of weighings that the sheer number of possible order relations between the weights, which grows faster than exponentially, can allow better results.)

if z = 3x, coin D is fake x is real value and 2y-x is the fake value.

if z= 3y then coin B is fake y is real value and 2x-y is the fae value.

if z-2x=y then coin C is the fake x is the real value and 2y-x is the fake value

if z-2y=x then coin A is the fake y is the real value and 2x-y is the fake value

There are 34 unique ways of weighing 4 coins in 3 weighings, up to equivalence, which are as follows:

Code: Select all

`ABCD, ABC, ABD`

ABCD, ABC, AB

ABCD, ABC, AD

ABCD, ABC, A

ABCD, ABC, D

ABCD, AB, AC

ABCD, AB, CD

ABCD, AB, A

ABCD, AB, C

ABCD, A, B

ABC, ABD, ACD

ABC, ABD, AB

ABC, ABD, AC

ABC, ABD, A

ABC, ABD, C

ABC, AB, AD

ABC, AB, A

ABC, AB, C

ABC, AB, D

ABC, AD, A

ABC, AD, B

ABC, AD, D

ABC, A, B

ABC, A, D

AB, AC, AD

AB, AC, BD

AB, AC, A

AB, AC, B

AB, AC, D

AB, CD, A

AB, A, B

AB, A, C

AB, C, D

A, B, C

EDIT: Tiredness caused far too many mistakes. Came quite close, but messed it up irrevocably at the end. Will come back to this tomorrow morning.

EDIT 2: OK, we can eliminate many of these options because they either fail to distinguish between a pair of coins, or they fail to weigh coin D. These are the ones that are left:

Code: Select all

`1 - ABCD, AB, AC`

2 - ABC, ABD, ACD

3 - ABC, ABD, AC

4 - ABC, ABD, A

5 - ABC, AB, AD

6 - ABC, AD, B

7 - AB, AC, AD

8 - AB, AC, BD

9 - AB, AC, D

These all fail to distinguish between 2 cases, which are given for each coin below (for each case, the capital letter denotes the fake coin, and the lowercase letter indicates whether the fake coin is heavy or light).

1) Ah / Dl

2) Ah / Al

3) Ah / Bl

4) Ah / Bl

5) Ah / Cl

6) Ah / Bl

7) Ah / Al

8) Ah / Dl

9) Ah / Dl

So 4 coins does require 4 weighings.

It's case 9 in the above post, but i will describe it a bit different.

Tw:=mass of the true coins.

Fw:=mass of the fake coin.

X=A,Y=BC,Z=CD.

So if 2X=Y!=Z=>X=Tw;(Z-X)=Fw D-fake

If 2X!=Y=Z=>X=Tw;(Y-X)=Fw C-Fake

If 2X=Z!=Y=>X=Tw;(Y-X)=Fw B-fake

If 2X!=Y=Z=>(Y/2)=Tw;X=Fw A-fake

Feel free to find my mistakes.

P.S.:Sorry for my english.

wesaq wrote:I'm prety sure you could get 4 with 3 weighings.

It's case 9 in the above post, but i will describe it a bit different.

Tw:=mass of the true coins.

Fw:=mass of the fake coin.

X=A,Y=BC,Z=CD.

So if 2X=Y!=Z=>X=Tw;(Z-X)=Fw D-fake

If 2X!=Y=Z=>X=Tw;(Y-X)=Fw C-Fake

If 2X=Z!=Y=>X=Tw;(Y-X)=Fw B-fake

If 2X!=Y=Z=>(Y/2)=Tw;X=Fw A-fake

Feel free to find my mistakes.

P.S.:Sorry for my english.

Consider the following weights:

1) A=2

B=C=D=2.5

2) A=B=D=2

C=3

Then the weighings will result in the same numbers, and we cannot tell the difference between the two cases.

my solution

for coins A,B,C,D,E

weigh A and B

weigh C

if A and B are equal to 2C, then we can assume the off coin is either D or E and go ahead and weight D. if D is equal to C then E is our coin, otherwise, it's D

if A and B are not equal to 2C, then we know the off coin is either A, B, or C. weigh A. if it's exactly half of A+B then the off coin is C, otherwise we know the off coin is either A or B (and that C is correct). if A is not the same as C then A is our off coin, if they are the same, the off coin is B.

end my solution

my solution

for coins A,B,C,D,E

weigh the following:

A, B

C, D

A, C, E

i will refer to the correct coin weight (or the individual weight of one of the 4 coins) as W.

if (A+B) == (C+D) then the off coin is E (determined in 2 weighings)

if (A+C+E) is equal to either 3/2(A+B) or 3/2(C+D) then W can be determined by 1/3(A+B+C). from there, the off coin is either coin B or D in whichever group that does not match 2W.

if (A+C+E) does not equal either 3/2(A+B) or 3/2(C+D), then it gets a little hard. in order to solve it from here, we need to find W. to find W, we perform these equations:

trial 1 = (A+B) + 1/2(C+D)

trial 2 = 1/2(A+B) + (C+D)

the correct trial has a resulting value equal to (A+C+E). if trial 1 is the correct trial, the value of W would be (C+D), if trial 2, it would be (A+B). from there, the off coin is either A or C in whichever group that does not match 2W.

end my solution

### Who is online

Users browsing this forum: Google Feedfetcher and 9 guests