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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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. $\endgroup$– Will OrrickCommented Sep 18, 2010 at 21:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Sep 20, 2010 at 2:55