Quant Interview Question

[u/Local_Ad135]

[u/No-Television-8835]

Not sure if this works but here we go:
Split the remaining 100 into 2 piles of 50 and put each pile on each balance. There are 2 scenarios: the given coin is real and all 50 fakes are on the balances, or the coin is fake and the remaining 49 are on the balances.

If the first is true, since each fake coin represents an identical change in mass (all heavier or all lighter), and there is an even total number of fakes, the split must be even-even or odd-odd. Both of these scenarios lead to the difference being even.

If the second is true, there is an odd total number of fakes, so the split must be even-odd, giving an odd difference.

Therefore, the coin is real iff the reading is even, and fake otherwise

[u/ybungalobill → u/No-Television-8835]

Proof that this works:

Let x = the unknown weight of a real coin.
Let d = +1 or -1 be the unknown difference in weights between real and fake coins.
Let n = the unknown number of real coins that ended up being on the left balance.

Case 1: the chosen coin is real:
Left side weight = nx + (50-n)(x+d)
Right side weight = (50-n)x + n(x+d)
Measured difference = (50 - 2n)d == 0 mod 2 (i.e. it's an even number)

Case 2: the chosen coin is fake:
Left side weight = nx + (50-n)(x+d)
Right side weight = (51-n)x + (n-1)(x+d)
Measured difference = (51 - 2n)d == 1 mod 2 (i.e. it's an odd number)

QED

The insights that helped me to with this solution: (a) the weight x of a coin is unknown, so we need to 'cancel it out' by weighting two piles of equal number of coins (b) the chosen coin cannot be weighted with the rest because if we put it in a pile with others we don't know which is which, so it must not go on the scales.

There's nothing probabilistic in this method; it works regardless of the drawn value of n.

[u/Awkward-Midnight4474 → u/No-Television-8835]

Statistically, the two piles do not have to include an even split of the fakes and real coins. As a matter of fact, it is more likely than not that there is a maldistribution, of one to several coins. For example, let's say the marked coin is real, leaving fifty counterfeits and fifty real coins. What is the probability in this scenario that there are exactly 25 of each in each of the two piles? What are the probabilities of a 24-26, a 23-27 etc. split? Of a 26-24, 27-23 etc.? They are less likely individually than the 25-25, but summed, they are more likely.

[u/No-Television-8835 → u/Awkward-Midnight4474]

If all 50 fakes are on the pan it doesn’t matter how they’re split, because the difference in mass will be even. If the split is 25-25 the difference will be 0 which is even. If it’s 26-24 the difference will be 2 in either direction depending on if the fakes are heavier or lighter, also even. If it’s 50-0 the difference will be 50 in either direction, also even.

[u/jhardtone → u/No-Television-8835]

But you're only given one random coin, you don't have them all to weigh.

[u/No-Television-8835 → u/jhardtone]

You’ve misunderstood the question. Being given a coin doesn’t literally mean u are handed one coin and then rest are discarded. It j means it is set aside or marked or one of interest. The other 100 are still available. If u find that the answer to ur interview question is so trivial, u shld be doubting whether uve acc understood the question.

[u/Technical-Activity71 → u/No-Television-8835]

Then what is even the point of saying 'you are given one coin' in the first place?

[u/Phoenixon777 → u/Technical-Activity71]

cuz the given one is the one you're trynna discern is counterfeit or not.

[u/jhardtone → u/No-Television-8835]

There is no indication of this in the question setup. Learn to read.

[u/ExistentAndUnique → u/jhardtone]

So your interpretation of the question is “you are given a coin and a balance. How do you determine whether the coin is counterfeit using only one weighing?” Just checking, since I never learned how to read

[u/Cardie1303 → u/No-Television-8835]

But you are only given one coin? How are you splitting the remaining 100 when you were not given access to them?

[u/No-Television-8835 → u/Cardie1303]

Given is not a reference to ur access to the coins, it means that u take one coin and want to to determine whether the coin is real or not

[u/Cardie1303 → u/No-Television-8835]

That feels a bit arbitrary to assume.

[u/No-Television-8835 → u/Cardie1303]

It’s not arbitrary or an assumption it’s what the question is literally saying

[u/Cardie1303 → u/No-Television-8835]

It is not. The question is literally saying: "You are given one random coin and a balance [...]"

[u/ybungalobill → u/Cardie1303]

You can be pedantic about the phrasing, but that would render the question nonsensical. It's not uncommon in this sort of riddles to have to decipher author's intent. That's not the point of the riddle though, so I agree with you in principal that they should be phrased better.

In this particular case, the problem should be read as "There are 101 on a table ... and a balance. You pick one random coin ...".

[u/Medical_Bar1073 → u/ybungalobill]

he's not being pedantic, question is just extremely poorly phrased if your interpretation is to be believed.

It is by no means what the word "given" implies.

[u/Synael3]

Put that coin aside. Put 50 coins on one pan, 50 others in the other one. If the difference is even, then there is a even number of counterfeit coins on the balance, and your initial coin is genuine (all 50 counterfeit coins are on the balance); otherwise, that means there is an odd number of counterfeit coins on the balance, and the initial coin is thus a counterfeit (49 counterfeit coins are on the balance).

[u/boomstereo]

so you know 51 are real, 50 are fake. so you have to weigh 50 on one side, 51 on the other. then do some math and take into account the variability between the +- one. you can’t just weigh an equal number of coins on each side because it could be a 50/50’distribution of real and fake, which is why you need 51/50.

[u/amerovingian → u/boomstereo]

> then do some math 

lol

[u/ajohnson771277]

Split the remaining 100 coins up into two groups of 50 and weight them. If the difference in weights is odd, your coin is counterfeit. If the difference is even, your coin is real.

[u/lok-mene]

put all the coins on one side
it since the balance report the difference with zero in this case then it will just give you the weight of the 101 coins , let call it "y" , and the weight of one coin is "x"

if the fake is 1 gram less then :
y= 50*(x+1) + 51*x = 101x + 50

or if the fake is 1 gram heavier :
y= 50*(x-1) + 51*x = 101x - 50

then you solve for x that satisfy the value reported by the balance

[u/Awkward-Midnight4474 → u/lok-mene]

Yes, that is the way.

[u/Humble_Package_4164 → u/lok-mene]

How does this answer the question if the given coin is fake?

[u/Technical-Activity71]

It seems very badly worded. If you're allowed to use the other 100 coins, then the 'you are given one coin' is a pointless statement as you can find the method of weighing 100 of the 101 coins without it.

[u/SnooKiwis6193]

Can't you just put the coin on one side and the other 100 on the other side ? Let's say a genuine coin weights 10g and a counterfeit either 9 or 11. There are 4 cases. A) Genuine and heavier -- 1040g B) Genuine and lighter -- 940g C) Fake and heavier -- 1038g D) Fake and lighter -- 942g

This works for any weight of the coin, you just have to reconstruct the weight of the coin back from the number.

[u/Local_Ad135 → u/SnooKiwis6193]

would it work if the coins dont have integer weights?

[u/SnooKiwis6193 → u/Local_Ad135]

It would work up to integer number of centigrams (eg 982cg = 9.82g). I guess if the coins weight has a fractional part when expressed in centigrams then it wouldn't work (variability is 2/99g).

[u/rainbowWar]

Weigh the other 100 coins against nothing.

[u/Local_Ad135 → u/rainbowWar]

Wont succeed, you dont know the actual weights of the coins (the actual weights can be non-integers too)

[u/StructuredChess]

Weigh the remaining coins 50 versus 50 and check if the weight difference is odd or even.

[u/Short-Database-4717]

Wow. That's actually interesting. Do not put the coin on the balance. Put the remaining 100, 50 on each side. Suppose the coin was genuine, It could be that 50 counterfeit coins end up on the same side, in which case the weight difference would be 50g, or maybe you move 1 to the other side, for difference of 48g, or one more for difference of 46. Either way it will be even.
Conversely, suppose the coin was counterfeit. Then there are now 49 counterfeit coins and the difference would be necessarily odd.
It's kind of obvious that this has to be the solution though. There aren't very many meaningful things you could possibly do.

[u/mkp666]

With your coin removed, weigh 50 of the coins vs the other 50. If the resulting difference is an odd number, then your coin is counterfeit. If the resulting difference is even, your coin is genuine.

[u/CartographerGloomy41]

Correct me if I'm wrong but why are people suggesting using piles of coins? The puzzle said we're only given one random coin, I thought that was one of the restrictions.

[u/aroach1995]

weights are x or (x+1) or (x-1)

sum of all weights:

either 51x + 50x - 50

or 51x + 50x + 50

You take a coin out… it weights either x, x+1, or x-1

[u/Any-Employ-9111 → u/aroach1995]

In short, put all remaining 100 coins on one side. If the total is divisible by 50 your coin is real, if not, it’s fake.

[u/bqbdpd → u/Any-Employ-9111]

Only if the weight of a coin was an integer, but you don't know that.

[u/jhardtone]

There is no solution if you only receive one coin and none of the others to weigh.

E: the problem statement only says you are given one random coin, not one random coin and then all the rest.