Optimization on a square lattice: Torsten Sillke, FRA, June 1997
Problem: (Ingo Alth"ofer, Jena, 31. Jan 1995)

Arrange the four letters {A,B,C,D} into a 5x5 square.
You have to use 9*A, 6*B, 5*C, and 5*D.
Adjacent letters get a cost shown in the following table:
Cost Phi: A B C D
+
A  0 0 1 4
B  0 3 2 2
C  1 2 0 0
D  4 2 0 0
The cost table is symmetric.
Determine all arrangements which give the minimal total
cost according the cost function Phi.
Example arrangement:
B D A B C 8
A C A A D 6
C A C A B 3
B C D B B 7
A D D A A 8
3 2 1 0 5
The numbers give the sum of cost in each row and column.
The total sum of cost for this example is 43.
Solution: (Torsten Sillke, FRA, 8. June 1995)

I make the following chain of reduction:
 4 letter optimization problem
 2 letter optimization problem
 isoperimetric problem (graphs)
 isoperimetric problem (geometric)
Reduction to a 2 letter optimization problem:
Replace the cost function Phi by Phi' which has lower cost.
The minimal total cost of Phi' will give a lower bound for
the minimal total cost of Phi.
Cost Phi': A B C D
+
A  0 0 1 1
B  0 0 1 1
C  1 1 0 0
D  1 1 0 0
But for Phi' A and B as well as C and D become equal.
So we only have two distinct letters '0' for A or B
and '1' for C or D. Our new two letter problem can
be written with a new cost function Psi.
Cost Psi: 0 1
+
0  0 1
1  1 0
We have 15 * '0' (9*A and 6*B) and 10 * '1' (5*C and 5*D).
The reduced problem is to find a 5*5 square arrangement
of 15 * '0' and 10 * '1' such that the number of adjacent
'0' and '1' is minimal.
This is a isoperimetric problem.
The isoperimetric problem in the 2dimensional lattice:
This discrete (edge version) of the isoperimetric problem
has been analyzed by B. Bollobas and I. Leader.
In this case (seperating 10 points in a 5*5 grid)
it is sufficient to consider the geometric isoperimetric problem
with a boarder which is parrallel to the axis.
Local optimal configurations are:
type 1

________
 
 
 A = 10  (inner) boarder length = 2*sqrt(10) = 6.32
 
______________
type 2
 
_______________
 
 A = 10  (inner) boarder length = 5
_______________
Going back to the discrete problem we
have for the
type 1 has a boarder length of at least 7,
_ _ _
x x x_ _
x x_ x x x examples of boarder length = 7
x x x x x x
x x x x x x
type 2 has a boarder length a least 5.
_ _ _ _ _
x x x x x
x x x x x
A boarder length 6 is not possible as a 'one step'
boarder is impossible for type 2 for aera 10.

Discretization don't increase the boarder for type 2.
Therefore we get total cost = 5 for function Psi.

The unique arrangement with total cost 5 is:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1
So we have a lower bound for Phi' and therefore for Phi.

The total cost for Phi is at least 5.

Going back from Psi to Phi:
The (0, 1)problem has a unique solution with cost Psi 5.
If there is a solution with total cost 5 of the Phi function,
this will give a total cost 5 solution of the Psi function.
To get minimal costs only placements which give Phi(x,y) = Phi'(x,y)
are allowed. In the following table all combinations which
are forbidden are marked with ''.
Cost Phi'': A B C D
+
A  0 0 1 
B  0   
C  1  0 0
D    0 0
Dissect the 5*5 square in the following seven regions 'a' to 'g':
a b c d e
a b c d e
f f f f f
g g g g g
g g g g g
Now there are 6 letters 'B' to place on the upper three rows.
If there was a 'B' on a fplace we would have a BC of BD
combination which is forbidden. Therefore all 'B' must be on
places 'a' to 'e'. By the pigeonhole principle one region
must contain a double 'B'. But a BB combination is forbidden.
This shows that total cost 5 for the Phi function is impossible.

The total cost for Phi is at least 6.

The construction of all solutions with total cost 6:
There is no (0, 1)solution of total cost 6. (This could have been
of type 2 only.) Therefore a total cost 6 solution of Phi results
in the total cost 5 solution of Psi.
To get minimal costs only placements which give Phi(x,y) <= Phi'(x,y) + 1
are allowed. In the following table all combinations which
are forbidden are marked with ''.
Cost Phi'': A B C D
+
A  0 0 1 
B  0  2 2
C  1 2 0 0
D   2 0 0
Region 'f' must contain exactly one 'B' (this will increase 5 to 6).
The regions 'a' to 'e' can be filled in two different ways:
A B A B A B A B A B
B A B A B A B A B A
This gives for the upper part the five possibilities:
B A B A B A B A B A B A B A B A B A B A B A B A B
A B A B A B A B A B A B A B A B A B A B A B A B A
B A A A A A B A A A A A B A A A A A B A A A A A B
At the boarder between the regions 'f' and 'g' we will find four AC
combinations. The last 'C' can be placed anywhere as BC and BD cost
the same. Therefore we get in total 16 different solutions (ignoring
reflections). The two symmetric ones are:
B A B A B B A B A B
A B A B A A B A B A
A A B A A A A B A A
C C C C C C C D C C
D D D D D D D C D D
Ingo says he constructed the problem by random.