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?
[Math] 12 balls weighing puzzle
co.combinatoricscoding-theorypuzzle
Related Solutions
This proof uses a combinatorial equivalent of the Borsuk-Ulam theorem. I think that the proof is a little more complicated than the average proofs here, so please check my related paper if you have difficulties to understand.
Octahedral Tucker's lemma. If for any set-pair $A, B\subset [n], A\cap B=\emptyset, A\cup B\ne\emptyset$ we have a $\lambda(A,B)\in\pm[n-1]$ color, such that $\lambda(A,B)=-\lambda(B,A)$, then there are two set-pairs, $(A_{1},B_{1})$ and $(A_{2},B_{2})$, such that $(A_{1},B_{1})\subset (A_{2},B_{2})$ and $\lambda(A_{1},B_{1})=-\lambda(A_{2},B_{2})$.
We will use this lemma for n=100. If for the boxes in A, the sum of the red balls is more than half of the total number of red balls, then we set $\lambda(A,B)=+red$. If it is more than half in B, then we set $\lambda(A,B)=-red$. We do similarly for blue and green (if they are not set yet to red). We also set $\lambda(A,B)=\pm (|A|+|B|)$ if $|A|+|B|\le 96$ (if they are not set to anything else yet). This way the cardinality of the range of lambda is 99, just as in the lemma. It is easy to verify that it satisfies the conditions of the lemma, thus there must be a set-pair for which we did not set any value. But in that case either A or B must be bigger than 96/2=48, thus at least 49. We can put the remaining boxes to the other part and we are done.
Note that this proof easily generalizes to more colors.
I am actually not aware of many results on planes of order 12 in the vein of what Lam et. al. did (I list the few I know of below). There seems to be a plethora of papers proving restrictions on the collineation group of a hypothetical such plane, but I am not aware of how any of these could be used to settle the existence problem.
Moreover, I am quite skeptical that disproving the existence of planes of order 12 by a computer search would help for the general theory much. Though it certainly would be nice to know, and if one actually found a plane of order 12, that would be quite exciting; but it's hard to gain deep insights from these combinatorial brute force searches.
Extending the approach by Lam et. al. to planes of order 12 is in principle possible. But probably still not feasible with today's computers, as the search space is a lot bigger than for order 10. Anyway, here are some reasons why I think that, and at the same time a sketch of things that would have to be done. But my personal belief is that one will need some substantially new ideas to make progress on this. Then again, only by actually trying to do it can one be sure... :)
From here on, I'll assume you are familiar with Lam's "The Search for a Finite Projective Plane of Order 10" and the notation used within.
A crucial point was the reduction of the (non-)existence to the value of certain weight enumerator coefficients $w_0$ to $w_{n^2+n+1}$ (a good exposition can be found in "On the existence of a projective plane of order 10" by MacWilliams, Sloane and Thompson). But the real breakthrough was when Assmus and Mattson proved that one only needs to know $w_{12},w_{15},w_{16}$ to determine all others. I'll refer to these as essential weight enumerator coefficients.
Some steps towards this for order 12 have been executed in "Ternary and binary codes for a plane of order $12$" by Hall and Wilkinson. Yet many nice properties and theorems will be hard to recover for order 12. E.g. for orders of the form $8m+2$, one knows the $\mathbb{F}_2$-rank of the incidence matrix. Not so for order 12, where working with a ternary code is in some ways more "natural." In particular, the $\mathbb{F}_3$-rank of the incidence matrix is known, but, alas, working with a ternary code means losing the natural identification of codewords with point sets, so tons of new machinery would be needed to exploit the ternary code. Thus I'll focus on the binary code case here.
Anyway, let's assume we reduced the number of essential weight enumerator coefficients as much as we can (Hall and Wilkinson pushed it down to 16; remember, for $n=10$ we had only 3). We must compute the essential coefficients.
According to Lam, for $n=10$ and the case $w_{12}$, they estimated, using a Monte-Carlo method (before doing it) that $4\times 10^{11}$ configuration had to be checked. I don't have a good means to compute a good estimate for $n=12$, but for that there are 16 coefficients to determine, and I'd hazard to guess that some of them are much, much harder than the three cases for $n=10$ put together. Several orders of magnitude. However, this is just gut feeling.
So let's assume we had somehow managed to overcome this and had computed all essential weight enumerator coefficients. We then would have the full weight enumerator at hand (and no projective plane arose as a byproduct of our search). Now, the hard part starts (corresponding roughly to the second half of Lam's paper), the one that took them 2 years for $n=10$: We have to somehow derive a contradiction (or construct a plane). A lot of ground work needs to be done (extending stuff from $n=10$), before one can even start writing code...
Ah well. To anybody who wants to try out this strategy on $n=12$, I would recommend to first try reproducing the $n=10$ result -- with modern computers it should be possible to do this much, much quicker than it took Lam et. al. originally (this verification might already interest some people on its own). Actually, at the very start, try it with even smaller examples ($n=6,8$), then go up.
Best Answer
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.