Sucesiones de listas de números

En la Olimpiada Internacional de Matemáticas del 2012 se propuso el siguiente problema:

Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos números adyacentes x e y tales que x > y y x está a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que sólo puede aplicar un número finito de dichas iteraciones.

Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformación).

Definir las funciones

tales que

  • (soluciones xs) es la lista de pares (n,ys) tales que ys es una lista obtenida aplicándole n transformaciones a xs. Por ejemplo,

  • (finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar más transformaciones. Por ejemplo,

  • (finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas más largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo,

Soluciones

5 Comentarios

  1. Si a alguien se le ocurre como evitar repeticiones…

    1. Añadiendo una guarda para alicia (gracias a Manu Pena por la idea)

      Y filtrando repeticiones en busca

      Se consigue bajar bastante el número de repeticiones.

    1. Una versión mucho más eficiente de finalesMaximales es recorrer el árbol de expansión en anchura (y no todo el árbol usando soluciones).

  2. Por el tipo de búsqueda, es bastante ineficiente cuando el proceso se ramifica en exceso, pero no se me ocurre otro modo de definirla haciendo uso de la librería de espacios de estado. También adolece de repeticiones innecesarias.
    Gracias a fracruzam por la ayuda.

Escribe tu solución