MHB Finding whether a coin is fake

[mathmaniac1]

There are 101 coins out of which 50 are fake and are 1 gram lighter than the original ones.One coin is chosen randomly.How can you find whether it is fake or original by a machine that shows the difference in weights of what is placed on the two pans?

 

[Nono713]

Request for clarification:
- How many weightings are we allowed to perform?
- When you say the machine shows the difference in weights, does it also give which one is lighter, or just the absolute difference in weight?

 

[mathmaniac1]

Oh,sorry...We are allowed only one weighing and the machine does not show which is heavier or lighter,it just gives the difference...

Looks like you have something in your mind...;)

 

[mathmaniac1]

Hint

Spoiler

Use the idea of parity

 

[Nono713]

Could you post the answer now Mathmaniac? It's been over a week and I don't think anyone is going to be answering, and I frankly have no idea but I am interested in the solution.​

 

[agentredlum]

Partial Answer

Let x be the weight of a lighter coin, then the total weight of all coins is 50x + 51(x + 1) = 101x + 51

Suppose you pick a light coin, place it on 1 side , place all remaining coins on the other side so now on one side you have 49x + 51(x + 1) and on the other side you have x. The difference is

49x + 51(x + 1) - x = 48x + 51(x + 1) = 99x + 51

Suppose you pick a heavier coin, place it on 1 side, place all remaining coins on the other side so now on one side you have 50x + 50(x + 1) and on the other side you have (x + 1). The difference is

50x + 50(x + 1) - (x + 1) = 50x + 49(x + 1) = 99x + 49So... When the machine gives you the difference. subtract 49 then divide by 99. If you get a whole number then you picked the heavier coin, otherwise you picked the lighter coin.

Note*This method works pretty well only if the coins have whole number weights. Further consideration of what may happen if the coins don't have whole number weights is giving me a headache so i stop here.

:)

 

[mathmaniac1]

Another very useful hint:

Spoiler

Keep the chosen coin aside and try dividing the remaining coins into two piles for weighing.Now use the idea of parity on the difference.

I hope this will be useful.

Parity seems to be very simple but it is very useful in many problems like this.

I wonder why the MHB fails to give the answer.

 

[agentredlum]

Another very useful hint:

Spoiler

Keep the chosen coin aside and try dividing the remaining coins into two piles for weighing.Now use the idea of parity on the difference.

I hope this will be useful.

Parity seems to be very simple but it is very useful in many problems like this.

I wonder why the MHB fails to give the answer.

I think i got it using the hint. The weight of the coin is inconsequential, what matters is the +1 difference in weight. The scale will always read integer so if you read even integer you have heavy coin set aside, if you read odd integer you have light coin set aside.

Spoiler

Set aside 1 coin and divide the others into 2 piles of 50 coins each. Label the piles A and B

CASE1: Suppose you set aside a heavy coin, then there are 50 heavy and 50 light coins left.

Let the number of heavy coins in pile A = x then the number of light coins in pile A is (50 - x)

Let the weight of the light coin = p and the weight of the heavy coin = (p + 1) then the weight of pile A is

W_A = x(p + 1) + (50 - x)(p) = 50p + x \\ \\

The number of heavy coins in pile B is (50 - x) and the number of light coins in pile B is x. Then the weight of pile B is

W_B = (50 - x)(p + 1) + xp = 50p + 50 - x \\ \\

W_A - W_B = 2x - 50 an even number since x is natural, the weight p vanishd!

CASE2: Suppose you have set aside a light coin then you have 49 light coins left and 51 heavy coins, proceed as before making 2 piles of 50 coins each.

Let the number of LIGHT coins in pile A = x then the number of heavy coins in pile A = (50 - x) and the weigh of pile A is

W_A = xp + (50 - x)(p + 1) = 50p + 50 - x \\ \\

The number of light coins in pile B = (49 - x) and the number of heavy coins in pile B = (x + 1) because (49 - x) + (x + 1) = 50 which must be the total number of coins... a bit tricky...

W_B = (49 - x)p + (x + 1)(p + 1) = 50p + x + 1 \\ \\

W_B - W_A = 2x - 49 an odd integer.

:)

I wouldn't be surprised if someone gets an easier way.

:)

 

[mathmaniac1]

​Agent,you made it look more difficult than it really is.

My solution

Spoiler

Divide the remaining coins into two equal piles with 50 coins and it is all too simple afterwards
The difference will be of the form 0x+b where $$b= \pm \ 1 + \pm \ 1 + \pm \ 1...50 times$$.If the resulting sum is even.Then it means there were even number of +1 in both piles .Which means the total of all fake coins is even which happens only if the coin kept aside is real (so that there are 50 fake coins remaining).
If the sum is odd then the total number of fake coins is odd implying that the chosen coin is fake.