| In 1966, Claude Berge 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 |‾n/2‾| white pegs followed immediately by |_n/2_| black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Avis and Deza proved that the alternating string can be sorted in |‾n/2‾| such Berge 2-moves for n ≥ 5. Extending Berge's original problem, we consider the same sorting problem using Berge k-moves, i.e., moves which take k adjacent pegs to k vacant adjacent holes. We prove that the alternating string can be sorted in |‾n/2‾| Berge 3-moves for n\not\equiv 0 (mod 4) and in |‾n/2‾|+1 Berge 3-moves for n\equiv 0 (mod 4) , for n ≥ 5. In general, we conjecture that, for any k and large enough n, the alternating string can be sorted in |‾n/2‾| Berge k-moves. This estimate is tight as |‾n/2‾| is a lower bound for the minimum number of required Berge k-moves for k ≥ 2 and n ≥ 5. |
|
