0

I don't know if this problem is known by any other name. The classic problem is: We have 10 machines that produce balls, each weighing 10grams. One of the machines, however, produces balls weighing 9 gramms only. We are allowed only one weighing and need to determine which machine is faulty.

The solution is to number the machines from 1 to n (n=10 here) and choose k balls from k-th machine. The total weight of selected balls would be off by expected weight by k-grams.

I was thinking of variations on this problem. What if we do not know by how much the faulty weight is off from the true weight, but that the difference between faulty weight and true weight is consistent? Can we still determine the faulty machine in one weighing?

How about 2 weightings?

Nik
  • 793
  • What is your solution? This question seems rather open-ended; usually something that broadly requests "good solutions" is likely to be closed. – Kazark Apr 19 '13 at 03:45
  • Sorry, my solution requires 2 weighings. Edited the original post to reflect this. Is a solution with a single weighing possible? – Nik Apr 19 '13 at 04:05
  • 1
    If two weighings are allowed, label machines with first n prime numbers. Collect k balls from k-th machine. Let the faulty machine be labeled 'i'. If w is the difference in weight, then first weighing would be off by iw grams. Now relabel all machines making sure that every machine's label changes. Let 'j' be the label of faulty machine this time. Second weighing would be off by jw grams. Ratio = i/j. For first 10 prime numbers, this ratio is unique for any two distinct primes. Thus, knowing this ratio means we would know i,j. Not sure if this uniqueness extends to any n > 10. – Nik Apr 19 '13 at 04:09

2 Answers2

1

For two weightings it's quite simple:

  1. Take 1 ball from every machine, ActualWeight - 10gr*10 is the difference for the faulty machine
  2. Using information from #1 you have the original task which is solvable with 1 weighting

I believe 1 weighting is not sufficient and here is why: if you take n1,n2,n3,...,n10 balls from corresponding machines, it's equally possible that 1st machine is faulty with weight difference 1/n1 and that 2nd machine is faulty with weight difference 1/n2 - these cases don't seem to be distinguishable...

maxim1000
  • 126
0

As simple as:

From machine #1 grab 1 ball, from machine #2 grab 2 balls, etc. Then weigh them in one go.

The weight should be the total number of balls multiplied by 10 grams. If the result is 90 grams less, we know that the faulty one is machine #9, if it is 20 grams less machine #2, etc.

jvdhooft
  • 7,589
  • 9
  • 25
  • 47
user653382
  • 1