Berge SortingIn 1966 Claude Berge [2] proposed the following sorting problem:
white pegs followed immediately by
(or vice versa) using only moves which take 2 adjacent pegs to 2 vacant
adjacent holes.
A solution for sorting the alternating n string in
Berge 2-moves for n > 2 was given in [1].
Berge's original problem can be extended to the same sorting problem using only Berge k-moves ; that is, moves which take k adjacent pegs to k vacant adjacent holes. A solution for sorting the alternating n string in
Berge 3-moves for n > 2 was given in [3, 4].(except for n = 12 and n = 16, for which one extra move is required) Conjecture [3]:
Berge k-moves for n > 2k+10.
is a lower bound for the minimum number of required Berge k-moves for k > 1.
The conjecture holds for k = 1, 2 and 3. See Table 1 which substantiated the conjecture by giving the minimum number h(n,k) of required Berge k-moves to sort the alternating n string by reporting the value of h(n,k)-
for given k < 15 and n < 51.See Table 2.1 and Table 2.2, for optimal solutions in
Berge 3-moves for n multiple of 4 and 16 < n < 92.Note that the alternating n string cannot be sorted by any number of k-moves for n < k +2. Prolog Programming Contest: The 12th Prolog Programming Contest took take place in August 2006, at the occasion of ICLP 2006 in Seattle, USA. The second problem was Berge Sorting. References:
Mr Kanno's site (in Japanese) describing Berge sorting for k = 2 and n even last change: October 2009 by Antoine Deza |