dave@cogsci.indiana.edu (David Chalmers) (03/01/89)
This is a combinatorial problem which is actually of considerable
importance in the theory of genetic algorithms. Any thoughts or
even better, solutions, would be appreciated.
Given integers n and k, we construct k 'circles' of the integers 1,...,n
in various orders. For example [n=6, k=2]
1 2 1 4
6 3 3 2
5 4 6 5
We define the 'distance' d(i,j) between two integers i,j
to be the LEAST distance between them on any of the circles
e.g. above, d(1,4)=1; d(3,5)=2.
The 'maximal distance' D of the construction is
D = max d(i,j)
i,j
(or in English: the maximum 'least distance' between any two integers i,j.)
In the above example, we can see that D=2 (as we have arranged it so
that no two integers are always separated by 3).
The problem is to find the construction of k circles which minimizes
this 'maximal least distance' D. In particular, we want to find
F(n,k) which is the smallest possible value of D. Another way of
saying this is that we want the 'cosiest' possible construction - that
construction that lets every pair of integers be as close together
(somewhere) as possible.
For our example, it's easy to see that F(6,2)=2. That is, the construction
above is the best we can do. (To do better, we would need d(i,j) = 1 for
all pairs (i,j), which would be impossible with only 2 circles).
A closed form expression for F(n,k) would be wonderful. Failing that, even
a rough estimate or bound would be nice.
Dave Chalmers
Center for Research on Concepts and Cognition
Indiana University