On the generalized Berge sorting conjecture

AbstractIn 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 ⌈n2⌉ white pegs followed immediately by ⌊n2⌋ 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. The generalized Berge sorting conjecture states that for any k and large enough n, the alternating string can be sorted in ⌈n2⌉ Berge k-moves. The conjecture holds for k=2 and n⩾5, and for k=3, n⩾5, and n≢0(mod4). We further substantiate this conjecture by showing that it holds for k=3, n⩾20, and n≡0(mod4). The introduced inductive solution generalized previous approaches and could provide insights to tackle the generalized Berge sorting conjecture