1
$\begingroup$

Given 10 coin generating machines, all of which produces a coin of weight x. Out of these, two machines are defective and produces a coin of weight x-1. You are given a weighing machine, how will you find the defective machines.

Extend this questions to a total of n machines , out of those n machines, m are defective and producing coins of x-1 weights.

I was asked this in an interview but unfortunately could not crack it. Please suggest some valid solution.

$\endgroup$

closed as unclear what you're asking by kanchirk, GentlePurpleRain, Deusovi, CodeNewbie, Rohcana Sep 11 '15 at 18:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Any limitations? Surely we can't individually measure the coins and associate them to their machines $\endgroup$ – Sean Sep 11 '15 at 17:11
  • $\begingroup$ Does the weighing machine only weigh the sum of whatever put on it? $\endgroup$ – Nautilus Sep 11 '15 at 17:16
  • $\begingroup$ @Rolling stones I was asked a similar question (if not the same) and the answer was to name each machine with a number starting from 1 incrementally so that each generates the same number of coins as their number. Just weight the total once, we can deduct which machine is faulty. $\endgroup$ – kanchirk Sep 11 '15 at 17:18
  • 3
    $\begingroup$ The first step to answering any interview question should be to ask questions and make sure you have all of the necessary information. All three answers so far (Kate Gregory, Bailey M, and Dr Xorile) are all valid but all make a different assumption about the weighing machine. The first step to answering the question would be to find out information about the weighing machine. $\endgroup$ – LeppyR64 Sep 11 '15 at 17:25
  • $\begingroup$ A few questions that might help you make this question clearer: $\bullet$ How many coins do the machines generate? Do the machines produce only a single coin, or can they produce multiple or any other fixed number of coins? $\bullet$ What is the function of the weighting machine, does it weigh the sum of whatever put on it, or does it act like balance and tells which side is heavier or something else. $\bullet$ How many weighing are allowed? Should we try to minimise the number of weighing? $\bullet$ Do we know the value of x, or just that the defective coins weigh less. $\endgroup$ – Rohcana Sep 11 '15 at 18:23
4
$\begingroup$

Presuming the restriction is to only use the weighing machine once, then it's a question of generating the right number of coins.

The most general solution is to simply generate $2^{n-1}$ coins from the $n$th machine, and weigh the whole lot. Assuming you know what the $x$ is, you'll know how much you are below that. This discrepancy can be converted to binary and you can read of the machine.

However, this will require over 1000 coins in the first instance.

If you know that there are exactly 2 machines out of the 10, you can rely on that to generate a more reasonable number.

Generate $1, 2, 3, 5, 8, 13,\cdots$ coins from each of the 10 machines, and read of the answer (Fibonanci again?!)

  • 3: 1 and 2
  • 4: 1 and 3
  • 5: 2 and 3
  • 6: 1 and 5
  • 7: 2 and 5
  • 8: 3 and 5
  • 9: 1 and 8
  • 10: 2 and 8 etc. You get the idea.

This approach can, I believe be generalised, if $m$ is known. You probably just need a recurrence that sums over $m$ coins rather than $2$ (as above). I'd have to think about that a bit to confirm it, so I'll wait for the OP to clarify what his question actually is.

$\endgroup$
1
$\begingroup$

This answer assumes that the 'weighing machine' represents a scale to weight two objects against one another. If it turns out the weighing machine is something different, I'll have to reword this answer.


Weigh 5 coins on each side of the scale.

Scenario A: Both sides have the same weight, meaning each side has one defective coin. For each side, weight two coins versus two coins. If the weights are even, the fifth coin is the defective one. If the weights are uneven, weigh the two lighter coins against each other. The lighter of the two is the defective coin.

Scenario B: One side is lighter than the other. That side has both defective coins. Weigh two coins from that side against another two coins from that side.

  • If they are the same weight, again each side has a defective coin. Weigh the two pairs against each other, and the lighter two coins are defective.

  • If one side is lighter, that side has at least one defective coin. Weigh the two coins in that pair against each other. If they're the same weight, they are your two defective coins. If one is lighter than the other, the lighter one and the one excluded from the first measurement on this side are your two defective coins.

$\endgroup$
  • 1
    $\begingroup$ I would suppose that the existence of a coin machine suggests that this is to be done with multiple coins from each machine. Your answer would work just as well for coins. $\endgroup$ – Dr Xorile Sep 11 '15 at 17:32
1
$\begingroup$

The problem is easy if you can use as many weighings as you like. Take any one coin and weigh it (9 separate times) against coins from other machines. You will know which two are lighter when you're done.

If you're trying to minimize weighings, try weighing a different number of coins from each machine. Then you can back-conclude that the coins came from particular machines. Sometimes it's suggested to weigh 1 from machine 1, 2 from machine 2 etc against a similar total from say machine 10 but that may not work... if the weights differ by 5, does that mean machine 2 and 3 are bad, or 1 and 4? Best to use binary and weigh 1 from machine 1, 2 from 2, 4 from 3, 8 from 4 and so on.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.