## Berge Sorting

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

Such moves are called

Given a string ofnalternating 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.Berge.2-moves

A solution for sorting the alternatingnstring in Berge2-moves forn> 2 was given in [1].

Berge's original problem can be extended to the same sorting problem using onlyBerge; that is, moves which takek-movesadjacent pegs tokvacant adjacent holes.k

A solution for sorting the alternating(except fornstring in Berge3-moves forn> 2 was given in [3, 4].

n= 12 andn= 16, for which one extra move is required)

Conjecture[3]:This estimate is tight as is a lower bound for the minimum number of required Berge

For any, the alternatingknstring can be sorted in Bergek-moves forn> 2+10.kk-moves fork> 1.

The conjecture holds fork= 1, 2 and 3.

See Table 1 which substantiated the conjecture by giving the minimum number h(n,k) of required Bergek-moves to sort the alternatingnstring by reporting the value of h(n,k)- for givenk< 15 andn< 51.

See Table 2.1 and Table 2.2, for optimal solutions in Berge 3-moves fornmultiple of 4 and 16 <n< 92.

Note that the alternatingnstring cannot be sorted by any number ofk-moves forn<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:

- David Avis and Antoine Deza:

Un des "problemes plaisans et delectables" de Claude Berge.

Discrete Mathematics306 (2006) 2299-2302.

- Claude Berge:

Problemes plaisans et delectables, le probleme des jetons noirs et des jetons blanc,

Revue Francaise de Recherche Operationnelle 41 (1966) 388.

- Antoine Deza and William Hua:

Berge sorting.

Pacific Journal of Optimization3 (2007) 27-35.

- Antoine Deza and Feng Xie:

On the Generalized Berge Sorting Conjecture.

Journal of Discrete Algorithms8 (2010) 1 - 7.

Mr Kanno's site (in Japanese) describing Berge sorting fork= 2 andneven

last change: October 2009 by Antoine Deza