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.


  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