rompecabezas de inversión de monedas con una mano y dos pilas

Question

Suponga que tiene N monedas etiquetadas apiladas en un montón en la punta de los dedos (la palma de la mano está por encima de los dedos y la palma hacia abajo, para que puedas dejar caer tantas monedas como sea necesario desde el fondo de la pila) y tienes una mesa que sólo permite otras dos pilas (llámese L para la izquierda y R para la derecha). Puedes elegir libremente L o R para cada moneda, pero el orden de caída de las monedas es fijo. También puede recoger libremente las monedas de cualquiera de las dos pilas (el reverso de una caída).

Para la N general, ¿cuál es el mínimo de pastillas necesarias para invertir la pila de la pila? Tengo curiosidad por el número total de monedas recogidas y por el número de eventos de recogida, pero oficialmente sólo pregunto por esto último.

Como ejemplo, creo que el mínimo para N=7 es 5. Empezamos teniendo 1234567. Dejamos 247 en L y 1356 en R; recogemos 1356 de R. Dejamos 16 en L y 35 en R; recoger 24716 de L. Dejar 76 en L y 241 en R; recoger 35241 de R. Deja 54 en L y 321 en R; recoge 321 de R. Deja 321 en L; recoge 7654321 en L.

Answer 1

Creo que la asintótica es $\log$ N, pero esto podría tener un multiplicador constante dependiendo de lo que cuente exactamente. La solución se conoce básicamente como ordenación Radix.

Imagina que tienes una secuencia cualquiera de N números sin ordenar. Representa cada uno con $\log$ N dígitos. Ordenamos primero con respecto al dígito menos importante, luego el segundo menos y así sucesivamente, finalmente con respecto al dígito principal. Esto se hace dejando los números más pequeños en L y los más grandes en R.