Berge Sorting

In 1966 Claude Berge [2] proposed the following sorting problem:

Given a string of n alternating white and black pegs on a one dimensional board consisting of an unlimited number of empty holes, rearrange the pegs into a string consisting of white pegs followed immediately by (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes.
Such moves are called Berge 2-moves .

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]:
For any k, the alternating n string can be sorted in Berge k-moves for n > 2k+10.
This estimate is tight as 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:

1. David Avis and Antoine Deza:
Un des "problemes plaisans et delectables" de Claude Berge.
Discrete Mathematics 306 (2006) 2299-2302.

2. Claude Berge:
Problemes plaisans et delectables, le probleme des jetons noirs et des jetons blanc,
Revue Francaise de Recherche Operationnelle 41 (1966) 388.

3. Antoine Deza and William Hua:
Berge sorting.
Pacific Journal of Optimization 3 (2007) 27-35.

4. Antoine Deza and Feng Xie:
On the Generalized Berge Sorting Conjecture.
Journal of Discrete Algorithms 8 (2010) 1 - 7.

Mr Kanno's site (in Japanese) describing Berge sorting for k = 2 and n even

last change: October 2009 by Antoine Deza