Author:
Jed Pack
[ Edit  View ]

Date Posted: 20:01:10 07/10/02 Wed
Mr. Cullinane,
There are exactly 840 unique configurations that can be attained through swapping columns, rows, or quadrants in the 4 by 4 case. As justification of the above statement, consider the following:
I programmed a computer to perform repeated random column, row, and quadrant swaps and keep track of unique configurations generated in this manner. After several thousand iterations, there were 840 unique configurations. This only proves that there are AT LEAST 840 members of the group. To prove there are EXACTLY 840 members of the group, I performed each of the 18 transformations (swapping the 6 pairs of rows, columns and quadrants) on each of the 840 configurations. In each case the resulting configuration was one of the 840 configurations. This proves that the 840 configurations are a group and that they are the only configurations that can be attained through the above mentioned transformations.
P.S. In my earlier message I stated that there were AT MOST 900. The previous argument is valid. The following addendum shows more formally that there are at most 840:
The two binary matricies that describe the configuration (call them A and B) are always different and never complementary (i.e. A is not an element of the set {B, 1B}). This statement follows inductively from two facts:
1) The condition is obviously true at the beginning.
2) No transformation can change this since the same operation is performed on both A and B.
As a result, 60 of the 900 configurations described by arbitrary combinations of two of the thirty available matricies are impossible. This leaves 840 possible configurations.
P.P.S. If you are interested, I can send you data files that describe each configuration. I can also include a 840 by 18 matrix indicating which configuration is produced by performing each of the 18 transformations on each of the 840 configurations.
P.P.P.S. The two binary matricies mentioned in my previous posting DO fully describe the configuration. Each of the 16 cells has four possible states (black corner can be top right, top left, bottom right, or bottom left). Thus, the original configuration (with four black diamonds) can clearly be described by one matrix as follows:

 2  1  2  1 
 4  3  4  3 
 2  1  2  1 
 4  3  4  3 

where a 1 means the black corner is bottom left, 2 means bottom right, 3 means top left, and 4 means top right.
This matrix can easily be generated using the two binary matricies as follows: 2*A+B+1.
As a result, these two matricies also fully describe the configuration.
[ Post a Reply to This Message ]
