Un des “problèmes plaisans et délectables” de Claude Berge

Between 1962 and 1966 Claude Berge edited a series of columns that appeared in the Revue Française de Recherche Opérationnelle, entitled Problèmes plaisans et délectables  , in homage of the 17th century work of Bachet. Each of these columns gives a new problem, along with solutions for earlier problems supplied by readers. The last of these columns contains a sorting problem, problem 41, in which we are given a string of nn alternately white and black pegs on a one-dimensional board consisting of an unlimited number of empty holes. We are required to rearrange the pegs into a string of consecutive white and black pegs, using only moves which take a pair of adjacent pegs to two vacant adjacent holes. With h(n)h(n) denoting the minimum number of moves needed to obtain a string of white pegs followed by black pegs, Berge gives the values h(5)=3h(5)=3, h(6)=3h(6)=3 and h(7)=4h(7)=4 and asks the reader to determine whether or not the function h(n)h(n) is increasing. This was the last issue of the Revue, and as far as we can tell, no solution has been published. In this note we offer a solution to problem 41 by showing that h(n)=⌈n/2⌉h(n)=⌈n/2⌉ for n⩾5n⩾5.RésuméDans une rubrique de la Revue Française de Recherche Opérationnelle intitulée Problèmes plaisans et délectables   en hommage à l’œuvre du 17ème siècle de Bachet, Berge proposa en 1966 un problème d’ordonnancement de nn jetons alternativement noirs et blancs à l’aide d’un coup qui déplace 22 jetons adjacents. Notant h(n)h(n) le nombre minimum de coups nécessaires pour obtenir une séquence de jetons blancs suivis de jetons noirs, Berge montre que h(5)=3h(5)=3, h(6)=3h(6)=3 et h(7)=4h(7)=4 et semble indiquer que la fonction h(n)h(n) est croissante. Dans cette note nous montrons que h(n)=⌈n/2⌉h(n)=⌈n/2⌉ pour n⩾5n⩾5.