00867nas a2200109   4500008004300000245005900043210005700102260002600159520051500185100002100700856003600721       2003                        en_Ud  00aA lemma and a conjecture on the cost of rearrangements0 alemma and a conjecture on the cost of rearrangements  bUniversità di Padova3 aConsider a stack of books, containing both white and black books. Suppose that we want to sort them out, putting the white books on the right, and the black books on the left (fig.~1). This will be done by a finite sequence of elementary transpositions. In other words, if we have a stack of all black books of length $a$ followed by a stack of all white books of length $b$, we are allowed to reverse their order at the cost of $a+b$. We are interested in a lower bound on the total cost of the rearrangement.1 aBressan, Alberto  uhttp://hdl.handle.net/1963/2914