A lemma and a conjecture on the cost of rearrangements. (English) Zbl 1114.05002

Given a line of books, which are either of black cover or of white cover, what is the minimum cost of sorting them out using transpositions (of blocks) so that books of the same color are put one after another? The lemma referred to in the title is the main result of this paper and states that the cost is at least logarithmic under certain assumptions on the configuration of books. Two (not one but closely related) conjectures are formulated for a continuous version of the problem.


05A05 Permutations, words, matrices
35L65 Hyperbolic conservation laws
35Q35 PDEs in connection with fluid mechanics
35R25 Ill-posed problems for PDEs
37C60 Nonautonomous smooth dynamical systems
Full Text: arXiv EuDML


[1] A. BRESSAN, An ill posed Cauchy problem for a hyperbolic system in two space dimensions, Rend. Sem. Mat. Univ. Padova, in this volume p. 103. Zbl1114.35123 MR2033003 · Zbl 1114.35123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.