Intercambio y apretón de manos con los vecinos en un círculo

Question

$N$ personas están en una fiesta y deciden jugar a un juego cooperativo. Empiezan formando un círculo. El juego se desarrolla por turnos. En cada turno, se elige a una persona para que realice un de las siguientes acciones:

• Estrechar la mano de alguien adyacente
• Intercambiar posiciones con alguien adyacente

El juego termina cuando todas las parejas de jugadores se han dado la mano, y el objetivo del juego es minimizar el número de intercambios necesarios. ¿Cuál es la estrategia óptima?

He intentado trabajar con algunos pequeños ejemplos (por ejemplo $N = 3,4,5,6$ requiere $0,1,3,5$ intercambios mínimos pero realmente no puedo encontrar un patrón en la estrategia).

Answer 1

Supongamos que $\{a_1, a_2, ...,a_n\}$ la gente juega a este juego. Las parejas de vecinos son

$$ \{a_1,a_2\} $$ $$ \{a_2, a_3\} $$ $$ \vdots $$ $$ \{a_n, a_1\} $$

Lo que da $n$ pares de vecinos. El intercambio con un vecino perturba el conjunto por

$$ \{a_1, a_2, ... a_{n-k+1}, a_{n-k}, ..., a_n\} $$

Así que, ahora, $a_{n-k+1}$ puede agitar con $a_{n-k}$ (que presumiblemente ya tienen) y (lo que es más importante) agitar con $a_{n-k-1}$

Para estrechar con todos, la persona originalmente en la ubicación $n-k$ deben migrar (por intercambio) alrededor del anillo para posicionarse $n-k+3$ (y asumo que esta persona se sacude con todos en el camino).

Necesitamos un total de $\frac{n(n-1)}{2}$ apretones de manos, y cada intercambio nos permite dar la mano a 2 personas nuevas (una con la persona que intercambió, y otra con la persona que fue intercambiada).

Propondré que $\left\lceil \frac{n(n-1)}{4} \right\rceil $ Los intercambios garantizarán que todo el mundo se dé la mano, pero no se me ha ocurrido una expresión mínima.

Tal vez alguien pueda hacerse cargo.