No estoy seguro de una conexión profunda; por lo que deduzco, es simplemente el caso de que el rompecabezas de la caja y el problema 6 tienen un subproblema común, que es: probar que "atravesar cajas" produce un ciclo, es decir, nos lleva a visitar un nodo que ya hemos visitado. En el rompecabezas de las casillas, hay una restricción adicional de que este ciclo incluya el nodo de inicio. Esta restricción se mantiene porque el rompecabezas de las casillas implica una permutación, mientras que el problema 6 no implica necesariamente una permutación.
A menos que se me pase algo por alto, los problemas 6a y 6b pueden resolverse simultáneamente utilizando la técnica de "atravesar cajas" a partir del índice 1 de la matriz, a pesar del comentario de que "la parte b) parece ser mucho más difícil que la parte a), y aparentemente requiere técnicas totalmente diferentes". Dado que se utilizaron las palabras de cobertura "parece" y "aparentemente", no podemos decir que el comentario sea falso, pero sin embargo, creo que sería falso sin esas palabras de cobertura. La idea clave es que, como se explica en el PDF del rompecabezas de la taquilla, "jugador $ B_i $ nunca abre una taquilla (que no sea la taquilla i) sin encontrar primero su número, por lo que cada vez que abre una nueva taquilla debe encontrar su propio número o el número de otra taquilla sin abrir". El mismo razonamiento básico se aplica al problema 6, con sólo ligeras modificaciones.
El problema 6 puede parecerse un poco más al rompecabezas de la taquilla si se saca un [1] de la foto. Podemos considerar que b = {a[2], ... ...a[n]} como la matriz "real" con m = n - 1 elementos, y el valor a[1] como el índice del nodo de inicio. Podemos volver a etiquetar {2, ... , n} como {1, ... ... m} si se desea.
Todo lo que nos importa es encontrar un ciclo, es decir, encontrar un valor que es un índice que ya hemos visitado. Esto equivale a encontrar un duplicado en la matriz a, ya que los índices que visitamos son precisamente valores de la matriz en a. Podemos cumplir con los requisitos de tiempo y memoria usando una matriz booleana de tamaño m. La matriz booleana nos permite ver si ya hemos visitado un índice, y por supuesto tiene una memoria constante y es rápido. Corrección: la matriz booleana tendría memoria lineal, no constante. Evidentemente hay una mejor manera de resolver esto). Estamos garantizados de no visitar ningún índice de la matriz dos veces, así que el algoritmo tiene tiempo lineal. Si no pensáramos en una matriz booleana, podríamos estar tentados a usar algún tipo de estructura de lista con inserción y búsqueda rápidas, pero una matriz booleana es más rápida.
Para unir más los problemas, podemos interpretar los datos como un gráfico dirigido donde cada vértice tiene un grado superior a 1. En el rompecabezas del casillero, el grado superior de cada vértice es también 1, pero el problema 6 no tiene tal restricción.
El grado 1 garantiza que podemos atravesar de un vértice a otro sin ninguna ambigüedad. Más allá de eso, necesitamos garantizar que un ciclo ocurrirá independientemente de donde comencemos.
Una permutación está dividida en ciclos, lo que nos permite concluir para el rompecabezas del armario que encontraremos nuestro ciclo precisamente cuando volvamos al nodo de partida. Para el problema 6, tenemos garantizado encontrar algún ciclo, porque de otra manera tendríamos que seguir sin parar, pero la matriz es finita, así que eso es absurdo.
Tal vez mi respuesta debería ser más rigurosa, pero espero que al menos sea satisfactoria y precisa. Si no, hágamelo saber, e intentaré arreglarlo. Admito que después de mirar este problema por un largo período de tiempo, mi mente se está nublando un poco..
EDITAR : Oh, creo que he descubierto cómo resolver 6b con la memoria constante. Puedes seguir n - 1 enlaces, cubriendo así n (no necesariamente distintos) índices de la matriz de a, y para este momento se garantiza que estás en medio de un ciclo. Anota tu índice de matriz actual. Luego da la vuelta hasta que veas ese índice de nuevo, lo que te dará el período del ciclo. Entonces usando esto puedes encontrar el "nodo de entrada" del ciclo, que será tu duplicado. (Usa la aritmética modular.) No lo he trabajado en detalle pero creo que es un bosquejo exacto.
