Fakultät für Mathematik und Informatik

Institut für Angewandte Mathematik

=========================================================================== 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 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 and

= denotes the equality relation

!= denotes the inequality relation

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

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: .16094A578B2C132C8B574A0936These 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: :BC6ADH475LFKGN2L6A59GN2O0O0M18FJEI3M18493JHK7BEICDAs 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.

Achim Flammenkamp

96-12-29 17:50