Berge Metrics

Abstract

<p>We consider a number of generalizations of the following question originally posed by Claude Berge in 1966. Let Sn denote the set of all strings made of [n/2] white coins and [n/2] black coins. Berge asked what is the minimum number of moves required to sort an alternating string of Sn by taking 2 adjacent coins to 2 adjacent vacant positions on a one-dimensional board of infinite length such that the sorted string has all white coins immediately followed by all black coins (or visa versa).</p> <p>We survey and present results dealing with the first generalization of Berge sorting which allows Berge k-moves, i.e., taking k adjacent coins to k adjacent vacant positions. We then explore a further generalization which asks for any pair of strings in Sn what is the minimum number of Berge k-moves needed to transform one string into the other. This induces a natural metric on the set Sn called the Berge k-metric. We examine bounds for the diameter of Sn allowing Berge k-moves. In particular, we present lower and upper bounds for Berge 1-metric and explore some aspects of Berge 2-metric along with computational results.</p>