It has long been known that the 36 officer problem has no solution.
Steven Lord proved that there is a solution with 2 'wild' entries ('SC's). The object of this proof is to show that there is no solution with just 1 SC.
1. The problem
Steven Lord proved that the 2 SC case is possible with this example:
1, CO 5, CA 2, SC 4, LI 3, SL 6, MA
2, SL 1, LC 5, LI 3, MA 6, CA 4, CO
4, CA 6, SL 1, MA 2, LC 5, CO 3, LI
6, LI 3, CO 4, SL 1, CA 2, MA 5, LC
3, SC 4, MA 6, LC 5, SL 1, LI 2, CA
5, MA 2, LI 3, CA 6, CO 4, LC 1, SL
The issues here are that:
Column 1 has CO, SL, CA, LI, SC, MA.
Row 5 has LC, SL, CA, LI, SC, MA, (not in that order)
So Column 1 'wants' LC, while Row 5 'wants' CO.
Column 3 has SC, LI, MA, SL, LC, CA.
Row 1 has SC, LI, MA, SL, CO, CA (not in that order)
So Column 3 'wants' CO, while Row 1 'wants' LC.
At first blush, the placement of LC and CO may look arbitrary, but it is not.
2. Legal swaps and diagonals
In the nxn officer problem, swapping columns does not change the contents of rows, and swapping rows does not change the contents of columns. These swaps are therefore valid.
It follows that in valid solutions to the nxn officer problem, there is always exactly one rearrangement where any given rank or regiment occupies the entire main diagonal.
However, simply swapping adjacent entries is not valid, since a horizontal swap will change the contents of two columns, while a vertical swap will change the contents of two rows.
3. The proof
This proof will proceed by contradiction, by showing that there is no rearrangement of the 6x6 officer problem where either (trivially) LC or CO occupies the entire main diagonal or, (more significantly) LC or CO plus ONE copy of SC does.
We treat LC and CO from here on as variables, i.e. whichever pair of ranks appears only 5 times in the 2SC solution.
We can apply valid swaps to Steven's solution to obtain this arrangement, where CO occupies the main diagonal except for the top left, which is LC:
6, LC 3, SC 4, MA 2, CA 1, LI 5, SL
2, SC 1, CO 5, CA 6, MA 3, SL 4, LI
4, SL 6, LI 3, CO 5, LC 2, MA 1, CA
5, LI 2, SL 1, LC 4, CO 6, CA 3, MA
1, MA 4, CA 6, SL 3, LI 5, CO 2, LC
3, CA 5, MA 2, LI 1, SL 4, LC 6, CO
or this one, where LC occupies the main diagonal except for the second row, second column, which is CO:
6, LC 3, SC 4, MA 2, CA 1, LI 5, SL
2, SC 1, CO 5, CA 6, MA 3, SL 4, LI
5, LI 2, SL 1, LC 4, CO 6, CA 3, MA
4, SL 6, LI 3, CO 5, LC 2, MA 1, CA
3, CA 5, MA 2, LI 1, SL 4, LC 6, CO
1, MA 4, CA 6, SL 3, LI 5, CO 2, LC
(incidentally, both solutions have a lot of nice symmetries, well worth checking out.)
Note in either case that if only a single rank appeared 5 times, then it would have to occupy the position now occupied by the other rank, a contradiction, since the diagonal contains 6 items. So there must be a minimum of 2 such ranks.
Nor need we consider more than 2 ranks, since Steven's proof shows that no more than 2 are required.
Note that by successive swapping of rows and columns, we can always get to the top left corner positions:
3,SC 6,LC
1,CO 2,SC (1) or
2,SC 1,CO
6,LC 3,SC (2)
for any solution with 2 SC's.
But in either case, the LC and CO entries are fixed, because they share both the same column and row as the SC entries. What we would like to do in case (1) is to swap adjacent entries either vertically (to complete a diagonal of CO) or horizontally, (to complete a diagonal of LC).
But those swaps are impossible, because the first would change the contents of the first row, while the second would change the contents of the first column. Hence, for just one of the SC's to occupy the main diagonal would involve an invalid swap, a contradiction.
Therefore there is no solution with just 1 SC, which completes the proof.
Edited on July 17, 2024, 11:05 am
|
|
Posted by broll
on 2024-07-17 02:34:16 |
Proposed solutiom
