Partículas en movimiento en el gráfico

Question

Considere el grafo completo $K_n$, y supongamos que ponemos a$k$ partículas diferentes en cada vértice, por lo que hay $kn$ partículas en total. Nos dicen que el $k$ partículas en un vértice están vinculados el uno con el otro. Ahora debemos hacer el siguiente juego:

En el paso $1$ nos debe mover cada partícula de su actual vértice a otro, con las siguientes reglas en mente:

• Ninguna partícula puede estar en su posición.
• Ninguna partícula puede permanecer conectado con otro.
• No puede haber más de $k$de las partículas en cada vértice al final del paso.

Así pues, tras el paso de $1$ cada dos partículas $p,q$ cuales fueron emparejados antes de (que comparten el mismo vértice antes del paso 1), debe ir a los diferentes vértices. Entonces, nos encontramos con una configuración distinta de la $kn$ partículas en el $n$ vértices.

Así que, si hemos hecho el paso $i$, se procede con el paso de $i+1$ como sigue: Debemos mover cada partícula de su actual vértice a otro, con las siguientes reglas

• Ninguna partícula puede estar en su posición ni un vértice que ha sido antes.
• Ninguna partícula puede ser emparejado con cualquier partícula que ha sido vinculado antes con.
• No puede haber más de $k$de las partículas en cada vértice al final del paso.

Seguimos hasta que no puede continuar en algún paso $s$; a continuación, el juego termina.

Ganamos si podemos hacer que cada partícula de llegar a cada vértice, y perdemos lo contrario.

Así que, mis preguntas son:

• Hay alguna forma para construir un algoritmo para saber si un juego con $k$de las partículas en cada vértice se puede ganar? En particular, hay alguna forma de encontrar el valor de $k$ ejemplo de que un juego con $k$de las partículas en cada vértice se puede ganar, pero un juego con $k+1$ partículas no?
• Es allí una más o menos conocido (solucionado o no) problema o teorema que podría ayudar a llegar a una solución para este (En el caso de que una solución de este problema no es tan elemental)?

Por ejemplo, con $1$ de las partículas en cada vértice el juego es claramente acertadas (Solo tienes que ir a través de un ciclo Hamiltoniano con todas las partículas), y con $n$de las partículas del juego es no (habrá dos vértices que debe permanecer vinculado o un vértice que no se mueve en el paso $1$).

Estoy particularmente interesado en el caso de que $n=6$, pero cuando pensaba en que quería generalizar. Por supuesto, en lugar de ser $K_n$ podemos comenzar con una arbitraria de Hamilton gráfico de $G$, modificando el número de partículas de cada vértice tiene contar inicialmente con las partículas sólo pasar de un vértice a algunos de sus vecinos, pero puede ser más complejo.

El juego vino de un problema de mi padre (que es un P. E. profesor en una escuela) me preguntó acerca de. Él ha $36$ estudiantes y quería hacer 6 grupos de 6 alumnos en cada grupo para discutir algún tema y, a continuación, cada estudiante debe ir a otro grupo para hablar de otro tema. Pero él no quería a los estudiantes a permanecer en el mismo grupo o de la repetición de los socios. Por supuesto, esto no es posible, pero puedo tratar de darle una alternativa donde en vez de ser grupos de 6 personas, que son, por ejemplo, los grupos de $3$ pares de personas.

Answer 1

Si $n$ es un número primo, entonces hay una solución para cada $k\leq n-1$.

Es decir, la etiqueta de los vértices de la gráfica con elementos de $\mathbb{Z}/n\mathbb{Z}$ y la etiqueta de las partículas en cada vértice $1,2,\ldots,k\in\mathbb{Z}/n\mathbb{Z}$. En cada paso, una partícula etiquetados $p$ actualmente en el vértice $x$ va al vértice $x+p$.

Desde $n$ es primo, en $n$ pasos, cada una de las partículas pasa a través de un ciclo Hamiltoniano, por tanto, el primer requisito es satisfecho.

Nota (a través de la inducción) que, a cada paso, las partículas en cada vértice tiene distintas etiquetas. Esto significa, en particular, que cada vértice tiene en la mayoría de las $k$ partículas (de ahí exactamente $k$ partículas) en cada paso. Así, el tercer requisito se cumple.

Por último, supongamos que en el paso $t$ ($0\leq t<n$), dos partículas marcadas $p$ e $q$ (con $p\neq q$) se encuentran en la misma posición para la primera vez. Deje $(x_s)_{t\leq s<n}$ e $(y_s)_{t\leq s<n}$ indican las trayectorias de estos dos partículas a partir de ese momento. Deje $z_s:=y_s-x_s$ e $r:=q-p$. Observar que $z_t=0$ e $z_{s+1}=z_s+r$ para $s\geq t$. Desde $r$ e $n$ son relativamente primos, $z_s\neq 0$ para $t\leq s<n$, lo que significa que dos partículas no se reunirá de nuevo. Por lo tanto, el segundo requisito es satisfecho.

Así, su padre podría, por ejemplo, el uso de $7$ grupos, ya sea con $5$ o $6$de los estudiantes en cada grupo. Si los grupos de $5$ al principio son etiquetados $1,2,\ldots,5$ (por lo que el número que falta es $6$), luego, en cada paso siguiente, él todavía tiene $5$ o $6$de los estudiantes en cada grupo con $6$ siendo el número que falta en los grupos de $5$.