La estantería de alturas

**Qué entrena:** reconstrucción de permutaciones desde perfiles locales.

Cinco libros de alturas distintas 1,2,3,4,5 (1 = más bajo, 5 = más alto) están en fila.

Cada libro anota cuántos libros más altos que él hay a su izquierda.

Las notas, de izquierda a derecha, son:
$$
0,\ 1,\ 1,\ 3,\ 0.
$$

¿Cuál es el orden de alturas de izquierda a derecha?

1. Encaja todo, y la solución es única.
2. Tomando a_1=4,\ a_2=2,\ a_3=3: para a_1=4, hay 0 más altos a la izquierda.
3. Tomando a_1=4,\ a_2=2,\ a_3=3: para a_2=2, solo 4 es más alto (1).

[Volver al problema](#prob-estanteria-alturas-dominacion-izquierda)

**Respuesta:**
$$
4,\ 2,\ 3,\ 1,\ 5.
$$

Sea la fila $a_1,\dots,a_5$.

• Nota 5 = 0: no hay nadie más alto a su izquierda $\Rightarrow a_5=5$.
• Nota 4 = 3: sus 3 de la izquierda son más altos $\Rightarrow a_4=1$.

Quedan $\{2,3,4\}$ para $a_1,a_2,a_3$ con notas $0,1,1$.

Tomando $a_1=4,\ a_2=2,\ a_3=3$:

• para $a_1=4$, hay 0 más altos a la izquierda,
• para $a_2=2$, solo $4$ es más alto (1),
• para $a_3=3$, solo $4$ es más alto (1).

Encaja todo, y la solución es única.

---