Moving particles on graph

Question

Consider the complete graph $K_n$, and suppose we put $k$ different particles in each vertex, so there are $kn$ particles in total. We say the $k$ particles in a vertex are paired with each other. Now we do the following game:

At the step $1$ we must move every particle from its current vertex to another one, with the following rules in mind:

• No particle can stay in its position.
• No particle can stay paired with another one.
• There can not be more than $k$ particles in each vertex at the end of the step.

So, after the step $1$ every two particles $p,q$ which were paired before (shared the same vertex before the step 1) must go to different vertices. Then, we end up with a different configuration of the $kn$ particles in the $n$ vertices.

So, if we have just done the step $i$, we proceed with the step $i+1$ as follows: We must move every particle from its current vertex to another one, with the following rules

• No particle can stay in its position nor to a vertex it's been before.
• No particle can be paired with any particle it's been paired before with.
• There can not be more than $k$ particles in each vertex at the end of the step.

We continue until we cannot proceed at some step $s$; then the game ends.

We win if we can make every particle reach every vertex, and we lose otherwise.

So, my questions are:

• Is there any way to build some algorithm to know if some game with $k$ particles in each vertex is winnable? In particular, is there any way to find the value of $k$ such that a game with $k$ particles in each vertex is winnable, but a game with $k+1$ particles is not?
• Is there a more or less known (solved or not) problem or theorem which could help getting a solution for this one (In case a solution of this problem is not so elementary)?

For example, with $1$ particle in each vertex the game is clearly winnable (Just go through a Hamiltonian cycle with all the particles), and with $n$ particles the game is not (There will be two vertices which must stay paired or one vertex which doesn't move at the step $1$).

I'm particularly interested in the case where $n=6$, but when I thought about it I wanted to generalize it. Of course, instead of being $K_n$ we can start with an arbitrary Hamiltonian graph $G$, modifying the number of particles each vertex has initially having the particles only move from a vertex to some of its neighbors, but it can get more complex.

The game came from a problem my father (who is a P.E. teacher at a school) asked me about. He has $36$ students and wanted to make 6 groups, place 6 students in each group to discuss some topic, and then each student must go to another group to discuss another topic. But he didn't want the students to stay in the same group or repeat partners. Of course, this is not possible, but I can try giving him an alternative where instead of being groups of 6 people, they are, for example groups of $3$ pairs of people.

Answer 1

If $n$ is a prime number, then there is a solution for every $k\leq n-1$.

Namely, label the vertices of the graph with elements of $\mathbb{Z}/n\mathbb{Z}$ and label the particles in each vertex $1,2,\ldots,k\in\mathbb{Z}/n\mathbb{Z}$. At each step, a particle labeled $p$ currently at vertex $x$ goes to vertex $x+p$.

Since $n$ is prime, in $n$ steps, each particles goes through a Hamiltonian cycle, hence the first requirement is satisfied.

Note (via induction) that at every step, the particles in each vertex have distinct labels. This in particular means that each vertex has at most $k$ particles (hence exactly $k$ particles) at every step. So, the third requirement is fulfilled.

Lastly, suppose that at step $t$ ($0\leq t<n$), two particles labeled $p$ and $q$ (with $p\neq q$) meet at the same position for the first time. Let $(x_s)_{t\leq s<n}$ and $(y_s)_{t\leq s<n}$ denote the trajectories of these two particles from that moment on. Let $z_s:=y_s-x_s$ and $r:=q-p$. Observe that $z_t=0$ and $z_{s+1}=z_s+r$ for $s\geq t$. Since $r$ and $n$ are relatively prime, $z_s\neq 0$ for $t\leq s<n$, which means the two particles will not meet again. Hence, the second requirement is satisfied as well.

So, your father could for instance use $7$ groups with either $5$ or $6$ students in each group. If the groups of $5$ at the beginning are labeled $1,2,\ldots,5$ (so the missing number is $6$), then at every following step, he will still have $5$ or $6$ students at each group with $6$ being the missing number in the groups of $5$.