Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In an article describing the twelve balls weighing problem, the author mentions a solution that involves the finite projective plane of order 3, discovered by Rick Wilson. Does anyone know what this solution could have been?

share|improve this question
    
Interestingly, Problem 20K in van Lint and Wilson's "A Course in Combinatorics" is a generalization of the 12 balls problem to the problem of finding the counterfeit coin among (3^r-1)/2 - 1 coins in r weighings. Their solution appears to be similar to the one in the article you link to. They make no explicit mention of the projective plane of order 3, but since the problem is posed immediately after their discussion of how codes were used to rule out the existence of the plane of order 10, there may be some connection with the ternary code of the plane that I'm not seeing immediately. –  Will Orrick Sep 18 '10 at 21:29

1 Answer 1

up vote 7 down vote accepted

Will Orrick is right, the problem is solved by exhibiting a matrix $3\times 12$ with entries in $\{-1,0,1\}$ where all columns are pairwise independent and the row sums are zero, as mentioned in Wilson's book.

In general you can solve the $\frac{3^r-1}{2}-1$ coin problem using $r$ weighings. You need to use one of the generator matrices of the simplex code, so the columns are given by the points in the projective space $P(r-1,3)$ (you throw out the point at infinity) and by induction show that the choices can be made to arrange the zero sum rows. For the case of 12 coins it suffices to consider the projective plane, and you get a constant weight code and thus end up weighing groups of 4 coins each time.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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