Conference rusure::math

    Here's a pretty pattern of 39 checkers for N=11.
    
	@ @ . . . . . @ @ . .
	@ . @ . . . @ . . @ .
	. @ . @ . . @ . . . @
	. . @ . @ . . @ . . @
	. . . @ . @ . @ . @ .
	. . . . @ @ @ . @ . .
	. @ @ . . @ . . . . .
	@ . . @ @ . . . . . . 
	@ . . . . @ . . . . @
	. @ . . @ . . . . @ .
	. . @ @ . . . . @ . .

    Nice result!!  BTW, it matches a computer search fairly well:
    
	t = [ sqrt(4*N-3)+1)/2 ]
    	F(N) = max number of checkers
    
	 N  (t+1)*N  F(N) (t+1)*N-F(N)
	 1	 2    1	   1
	 2	 4    3    1
	 3	 9    6    3
	 4	12    9    3
	 5	15   12    3
	 6	18   16    2
	 7	28   21    7
	 8	32   24    8
	 9	36   29    7
	10	40   34    6
	11	44   39    5
	12	48    ?    ?
    
    From whence did Fred derive?  It's not at all obvious.
    
    How about a constructive lower bound?

     re .3
     
>>    From whence did Fred derive?  It's not at all obvious.
     
     There are C(N, 2) = N(N-1)/2 ways to select two columns out
     of N columns.  There are C(n(i), 2) = (n(i))(n(i)-1)/2 ways
     to select two occupied columns out of a row with n(i)
     columns occupied.
     
     You have an aligned rectangle if any two rows both have the
     same pair of columns occupied.
     
     The sum for row i = 1, ..., N of C(n(i), 2) is how many not
     necessarily distinct pairs of occupied columns there are. 
     If this exceeds the total number C(N, 2) of pairs of
     columns, then at least one pair must be duplicated.  The way
     the count is set up the duplicated pair must show up on
     separate rows and so it makes an aligned rectangle.
     
     For example, for N=4 you have
     
     occupied pair of columns: {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} n(i)(n(i)-1)
     
     Row 1: @--@                 no    no   yes    no    no    no    2
     
     Row 2: -@@@                 no    no    no   yes   yes   yes    6
     
     Row 3: @-@-                 no   yes    no    no    no    no    2
     
     The sum of the (n(i))(n(i)-1) terms is 10, or twice the
     numbers of yes's.  N(N-1) is 12, or twice the number of
     (unordered) pairs.  If row 4 has three checkers, then that
     is adding 6 (twice the number of pairs that three checkers
     make) to the sum, giving you a total of 16 compared to the
     limit of 12; i.e., a total of 8 yes's spread over 6 pairs. 
     At least one pair (one column of my table) would have to
     have two yes's in it, and that means there will be a
     rectangle.
     
     Dan

Notation summary
	t = [ sqrt(4*N-3)+1)/2 ]
	where [x] is the 'floor', the integral part of x.
    	F(N) = max number of checkers
	F(N) =< (t+1)N

>    Nice result!!  BTW, it matches a computer search fairly well:

	Thanks, but we can do better if you're looking to bound F(N) tightly.
Assume that we've got a solution satisfying the Monopoly House Rule, ie. each
row has either t or t+1 checkers in it.   Define a to be the number of rows that
have t+1 checkers.   The estimate I gave assumes a worst case: a = N.    But in
fact such a high value is often impossible.

	In reality...

F(N) =< tN + a 			(*)

	(N-a)t(t-1) + a(t+1)t =< N(N-1)
but
	(N-a-1)t(t-1) + (a+1)(t+1)t > N(N-1)

(This is just our old friend Fred, for the Monopoly House case).

Rearranging, get:

	a = [ (N-1 - t(t-1))N/2t ]

Now the good thing about (*) is that the bound is actually *attained* for some
n.   If N = n^2 - n + 1, then t = n, and a = 0.   But n^2 - n + 1 is just
the number of points (or edges) in the projective plane of degree n, PL(n).

Aha!	So we identify the rows of our square with the points of PL(n) and the
columns with the edges, and put a checker in a box iff the corresponding point
lies on the corresponding line.

(My geometry is rusty, but I believe we define a projective plane as follows:
we have points, and we have lines.   Every two points define a unique line
which passes through them;  every two lines meet at a unique point.   There is
also some criterion like 'each point has at least 3 lines' to rule out various
trivial cases.)

The problem is, that projective planes don't exist for all n.   Perhaps someone
with a text-book can look it up.   I show below the incidence (= checkers)
diagrams for n = 3,4,5.   From the dim mists of time, I seem to recall Marshall
Hall proving that Pl(6) (and other ones = 2 mod 4?) don't exist, through some
argument I can't recall).   I want to know what the answer is before I carry 
on.

	In the mean time, here is my extended version of CLT::GILBERT's table.

	 N  t (t+1)*N  	  F(N) (t+1)*N-F(N)	a	tN+a tN+a-F(N)
	 1  1	 2	    1	  1		0	 1	0
	 2  1	 4	    3	  1		1	 3	0
	 3  2	 9	    6     3		0	 6	0
	 4  2	12	    9     3		1	 9	0
	 5  2	15	   12     3		2	12	0
	 6  2	18	   16     2		4	16	0
	 7  3	28	   21     7		0	21	0
	 8  3	32	   24     8		1	25	1
	 9  3	36	   29     7		3	30	1
	10  3	40	   34     6		5	35	1
	11  3	44	   39     5		7	40	1
	12  3	48     45or46  2or3	       10	46   0or1
	13  4   65    	   52    13             0	52	0

The important thing is the last column, which shows the difference between
my bound (*), and CLT::GILBERT's computed answer.   In addition, I exhibit
below the exact projective plane solution for N=13, and by pruning the
top row and the leftmost column, we get a lower bound of F(N) >= 45.


n=3:

X X X . . . .
X . . X X . .
X . . . . X X
. X . X . X .
. X . . X . X
. . X X . . X
. . X . X X .    

n=4:

X X X X . . . . . . . . .
X . . . X X X . . . . . .
X . . . . . . X X X . . .
X . . . . . . . . . X X X
. X . . X . . X . . X . .
. X . . . X . . X . . X .
. X . . . . X . . X . . X
. . X . X . . . X . . . X
. . X . . X . . . X X . .
. . X . . . X X . . . X .
. . . X X . . . . X . X .
. . . X . X . X . . . . X
. . . X . . X . X . X . .

	Forgot to put in n=5.

X X X X X . . . . . . . . . . . . . . . .
X . . . . X X X X . . . . . . . . . . . .
X . . . . . . . . X X X X . . . . . . . .
X . . . . . . . . . . . . X X X X . . . .
X . . . . . . . . . . . . . . . . X X X X
. X . . . X . . . X . . . X . . . X . . .
. X . . . . X . . . X . . . X . . . X . .
. X . . . . . X . . . X . . . X . . . X .
. X . . . . . . X . . . X . . . X . . . X
. . X . . X . . . . X . . . . X . . . . X
. . X . . . X . . X . . . . . . X . . X .
. . X . . . . X . . . . X X . . . . X . .
. . X . . . . . X . . X . . X . . X . . .
. . . X . X . . . . . X . . . . X . X . .
. . . X . . X . . . . . X . . X . X . . .
. . . X . . . X . X . . . . X . . . . . X
. . . X . . . . X . X . . X . . . . . X .
. . . . X X . . . . . . X . X . . . . X .
. . . . X . X . . . . X . X . . . . . . X
. . . . X . . X . . X . . . . . X X . . .
. . . . X . . . X X . . . . . X . . X . .

	So tN + a is attained for N=21, and by removing the left-hand row and
top most column, tN+a-F(N) = 0 or 1 for N=20.

	View the array above (and the same applies for the arrays for n=3,4)
in the following way.   The 2n+1 left-most rows and top-most columns are a
fixed frame, and wlog we can fill in the checkers in the way defined.
The remainder of the grid consists of an array of (n-2) x (n-2) blocks, each
block consisting of an (n-1)x(n-1) square of values, P(i,j) (i,j in {1,..,n-2}

	Regarding a checker as 1 and a space as 0, each P(i,j) will be a 
permutation matrix (ie. exactly n-1 non-zero entries, one in each row & column)
The permutation matrices will be any such that:

(a)	I + sum(i)(P(i,j)) = U for all j.	
	I + sum(j)(P(i,j)) = U for all i.
where U is the matrix with all entries 1.

(b)	Let Q(i,j,k,l) = P(i,j).(P(k,j))'.P(k,l)
where A' is the transpose of A.   No entry of Q(i,j,k,l) may have a 1 in the
same site as P(i,l).

	Symmetry considerations simplify the search space enormously for these
things.

	Anyone have any book knowledge of projective planes.