Groupe d’études et de recherche en analyse des décisions

G-2003-07

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

et

Dans une rubrique de la Revue Française de Recherche Opérationnelle intitulée Problèmes plaisans et délectables en hommage à l'oeuvre du 17ème siècle de Bachet, Berge proposa en 1966 un problème d'ordonnancement de n jetons alternativement noirs et blancs à l'aide d'un coup qui déplace 2 jetons adjacents. Notant 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) = 3, h(6) = 3 et h(7) = 4 et semble indiquer que la fonction h(n) est croissante. Dans cette note nous montrons que h(n) est égal à la partie entière de (n+1)/2 pour n ≥ 5.

, 7 pages