¿Es posible alcanzar cada disposición mezclando de esta manera?

Question

Supongamos que tenemos una pila vertical de $n$ monedas distinguibles, cada una de las cuales está boca arriba o boca abajo. Sea una mezcla el siguiente procedimiento: dividir la pila a voluntad en una pila superior e inferior, y simplemente rotar toda la pila superior $180^\circ$ como unidad. Así, para $1\le k\le n$:

$$\underbrace{x_1,...,x_{k}}_{\text{pila superior}},\underbrace{x_{k+1},...,x_n}_{\text{pila inferior}} \\ \downarrow\\ \overline{x_k},...,\overline{x_{1}}, x_{k+1},...,{x_{n}}$$

donde cada $x_i$ es o bien $H_i$ o $T_i$, y

$$\overline{x_i} = \begin{cases} H_i, & \text{si }x_i = T_i \\ T_i, & \text{si }x_i = H_i. \end{cases} $$

Dado que hay $2^n$ secuencias concebibles de $H/T$ sin subíndices, y hay $n!$ formas de agregar los subíndices a cada una, hay $n! \cdot 2^n$ formas concebibles de organizar la pila.

¿Es el caso que, para cualquier $n$, todas estas disposiciones concebibles son alcanzables mediante mezclas repetidas (independientemente de la disposición inicial)?

Answer 1

Sí, puedes conseguir todos ellos. Basta con demostrar que puedes llevar cualquier moneda deseada hasta abajo en cualquier orientación, ya que luego puedes manipular el resto de la pila sin afectar a la moneda de abajo y así construir la secuencia deseada de abajo arriba. Pero esto es fácil: cualquier moneda puede ser llevada hasta arriba en como máximo un movimiento, donde se puede voltear si es necesario antes de invertir la pila para llevarla hasta abajo.

Answer 2

Sí.

Sabemos que si podemos intercambiar cualquier par de elementos adyacentes (sin realizar otros cambios) y hacer esto repetidamente, podemos obtener todas las permutaciones. Y si podemos voltear una sola moneda (sin realizar otros cambios) y hacer esto repetidamente, podemos obtener todas las disposiciones de caras y cruces.

Para voltear la moneda $x_n$, primero rota las $n$ monedas superiores, de modo que $x_n$ ahora esté en la parte superior. Luego rota solo la moneda superior para que se voltee, y luego rota las $n$ monedas superiores. $x_n$ estará en su lugar original, volteada, sin que ninguna otra moneda haya cambiado.

Para intercambiar dos monedas adyacentes, rota desde la parte superior de la pila hasta la moneda inferior, de modo que esas dos monedas ahora estén en la parte superior. Luego rota esas dos monedas, para que ambas sean intercambiadas y volteadas. Luego voltea cada una de esas monedas, como se describe en el párrafo anterior. Luego rota las monedas nuevamente para devolver esas dos a su posición original.

Answer 3

Preguntar si se puede llegar a cualquier disposición es lo mismo que preguntar si se puede ordenar (en una configuración determinada, como tener los subíndices en orden ascendente y todas las monedas boca arriba).

Otros usuarios han señalado que esto es posible. La pregunta de cómo hacer esto eficientemente se conoce como el "Problema de Voltear Pancakes Quemados". Tú (un camarero) tienes una pila de pancakes de diferentes tamaños, pero están desordenados--quieres ordenar los pancakes por tamaño, de manera que el más grande esté en la parte inferior, seguido por el siguiente más grande, y así sucesivamente. La única operación disponible para ti es tomar una espátula, insertarla en algún lugar de la pila, levantar la pila de pancakes por encima de la espátula, invertirla y reemplazarla.

Además, uno de los lados de cada pancake está quemado, y (para efectos de presentación) quieres colocar todos los lados quemados hacia abajo. (Esto corresponde a las caras en tus ejemplos de monedas.)

Se han creado varios algoritmos para ordenar una determinada pila de pancakes quemados, con el objetivo de utilizar la menor cantidad de volteos necesarios. Más información:

http://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman

http://en.wikipedia.org/wiki/Pancake_sorting#The_burnt_pancake_problem

http://www.math.illinois.edu/~dwest/openp/pancake.html

¿Por qué es difícil ordenar pancakes?

http://arxiv.org/pdf/1010.0219v1.pdf

Para tu información, este problema está relacionado con el estudio de la mutación del ADN. Además, quizás te interese saber que Bill Gates coescribió un artículo sobre la variación "no quemada" de este problema.