Friedrich-Schiller-Universität Jena
Fakultät für Mathematik und Informatik
Institut für Angewandte Mathematik

Symmetries in No Three in Line Configurations

The single letter n always denotes the size of a given grid.

Symmetry Notation

  ===========================================================================
  Symmetry classes in no-three-in-line   or   the  Group D4 of the n x n grid
  ===========================================================================


                                1-fold     2-fold      4-fold      8-fold
                              ---------------------------------------------

reflection in mid-pendicular:               ort1        ort2          


1/k rotation about center:       iden       rot2        rot4        full


reflection in long-diagonal:                dia1        dia2

Symmetry Conditions

Symmetry class == ort1 || ort2 || full and n odd
The mid row == symmetry row must contain 2 markers. But this forces in the corresponding columns an odd number of markers. A contradiction. Therefore in ort1 || ort2 || full there exists no solution if n is also odd.
Symmetry class == rot4 and n odd
There must be a total of 2n markers which is not dividable by 4. But each quarter of the grid which must contain (2n)/4 markers. A contradiction! Therefore if n is odd in class rot4 there are no solutions.
Symmetry class == dia2
If n is even either on both long diagonals are 2 markers, or on neither long diagonals is any marker. Empirically is found that only the first case is realized! If n is odd, then on exact one of the long diagonals are 2 markers
Symmetry class == dia1
on the reflecting long diagonal must be 0 or 2 markers.
Symmetry class != iden && != dia1 and n odd
the central point can not be marked because the total number of markers must be even.
|| denotes the logical or
&& denotes the logical and
= denotes the equality relation
!= denotes the inequality relation

Symmetry Effects

In symmetry class dia1 or dia2 a marker on a reflecting long diagonal forbids any further marker on the diagonal orthogonal crossing his position.
In symmetry class rot4 there appear interesting number theoretic phenomena. Each marker which is set in a possible configuration forbids certain other positions of the grid because further markers together with their 3 symmetry markers block certain lines. The number variates not only with the grid size but strongly depends on the actual position of the marker. E.g. look at this 10 x 10 example: 
. . . . . . + . . .
. + . . o . . . + .
. . . . . . . . . .
+ . . . . . . . . .
. . . . . . . . o .
. o . . . . . . . .
. . . . . . . . . +
. . . . . . . . . .
. + . . . o . . + .
. . . + . . . . . .
The markers set at the o positions block the + locations. In general a marker can block not more than n other positions.

Near Symmetry Misses

The size of a miss of a configuration C in regard to a symmetry class SYM let be defined as: | { SYM(x,y) | (x,y) \in C but SYM(x,y) is \notin C } |.
Due to an idea of John Selfridge I looked for nearest missed symmetric configurations. There are some which missing reflection in a(both) mid-perpendiculare: 
n=3  missing ort2:  x010212
n=7  missing ort2:  :13062415240635
n=7  missing ort2:  :13240615062435
n=9  missing ort1:  .135628044707285613
n=11 missing ort2:  :372845190A460A19562837
n=13 missing ort2:  :0C4839562A1B571B2A6739480C
n=13 missing ort1:  .16094A578B2C132C8B574A0936
These are nearly missing quarter rotation symmetry of the grid: 
n=3  missing rot4:  x010212
n=9  missing rot4:  :341613680802572745
n=17 missing rot4:  :AD7F570C35CE08EF6A128G24BD4G9B1936
n=19 missing rot4:  :58BE8G461F6IDF19GI7B029H350C3HCE2A47AD
n=19 missing rot4:  :8BDE8G461F16DF09GI7B029I35CH3HCE2A457A
n=21 missing rot4:  :5CBD5CGH39IK7A1E021G6E4JIK6JAD02BH348F798F
n=23 missing rot4:  :CH188CHI3D03DF6BKL46027FKMGI12BG79JM9J45AEEL5A
n=25 missing rot4:  :9D8ICI3K38EH1259KNHO5D0A2MEOBJ0714FJMN7AGL4L6C6GBF
n=25 missing rot4:  :BC6E7D475LFKGNLM6E59182O0O0MGNFJAI2318493JHKBHAICD
n=25 missing rot4:  :BC6ADH475LFKGN2L6A59GN2O0O0M18FJEI3M18493JHK7BEICD
As a conclusion the only n=3 solution misses nearest the full symmetry of the grid.
In symmetry class dia1 dia2 or rot2 nearest misses are unknown (doesn't exist?). Configurations with minimum KNOWN misses for rot2 have miss 4 in stead of 2. Configurations with minimum KNOWN misses for dia1 have miss 4 in stead of 2.

Back to my HomePage

Achim Flammenkamp
96-12-29 17:50