One of the ``problèmes plaisants et délectables'' by Claude Berge (Un des ``problèmes plaisants et délectables'' de Claude Berge). (Q2433697)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | One of the ``problèmes plaisants et délectables'' by Claude Berge (Un des ``problèmes plaisants et délectables'' de Claude Berge). |
scientific article |
Statements
One of the ``problèmes plaisants et délectables'' by Claude Berge (Un des ``problèmes plaisants et délectables'' de Claude Berge). (English)
0 references
30 October 2006
0 references
This paper studies the following sorting problem (using a slightly different statement), originally proposed by Claude Berge in the 1960's. Input: \(\lceil n/2\rceil\) black and \(\lfloor n/2\rfloor\) white balls, placed alternatively in a one-dimensional board consisting of an infinite number of cells (the first ball is black). Operation allowed: move two adjacent pairs of balls (keeping their relative order). Output: all white balls are placed consecutively, followed by all black balls. The authors show that the minimum number of moves needed to sort these balls is equal to \(\lceil n/2\rceil\) for \(n\geq5\).
0 references
sorting
0 references
optimal algorithm
0 references
complexity
0 references