Title: Berge Metric
Abstract:
We present the problem of sorting general strings on n black and white coins using Berge k-moves, i.e., taking k adjacent coins to k vacant adjacent holes on a one-dimensional board. The notion of a Berge Metric characterizes the maximum number of k-moves needed to sort one string into another. We present Peter Sziklai's lower and upper bounds for moving one coin at a time and establish the Berge 1-distance for general strings.