COMPUTATIONAL FRAMEWORK FOR THE GENERALIZED BERGE SORTING CONJECTURE

Abstract

In 1966, Claude Berge proposed the following sorting problem. Given a string of n alternating white and black pegs, rearrange the pegs into a string consisting of all white pegs followed immediately by all black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Berge's original question was generalized by considering the same sorting problem using only Berge k-moves, i.e., moves which take k adjacent pegs to k vacant adjacent holes. Let h(n,k) denote the minimum number of Berge k-moves to sort a string of n alternating white and black pegs.The generalized Berge sorting conjecture states that h(n,k) is equal to the ceiling of n/2 for any k and large enough n. We develop a computational framework to determine h(n,k) for small instances with a focus on the most computationally challenging instances; that is, the determination of (k+2,k).