Bar de cócteles problema

Question

Recientemente fui con amigos y nos planteamos la siguiente pregunta: Considere el $n$ gente sentada en un bar de cócteles junto a la otra. Cuántos reordenamientos tiene que ser hecho para asegurar que cada posible pareja se ha sentado al menos una vez uno al lado del otro?

Más precisamente:

Por $n>1$, encontrar un subconjunto $A$ $S_n$ con cardinalidad mínima tal que para cada una de las $1\leq i<j\leq n$ no es un porcentaje ($\pi\in A$tal que $|\pi(i)-\pi(j)|=1$.

Answer 1

No es una respuesta completa, pero: al $n+1$ es primo, la respuesta es $n/2$.

Observe que $n/2$ es un límite inferior para cualquier $n$: cada elemento de a $A$ "cheques" en la mayoría de los $n-1$ nuevas parejas, y hay $\binom n2 = n(n-1)/2$ parejas que necesitan ser revisados en total.

Para la construcción de $n/2$ configuraciones que lograr esto al $n+1$ es el primer: número de la gente de a$1$$n$, y en el $k$th de configuración, hacer que la persona $i$ sentarse en el asiento $ik\pmod{n+1}$. Debemos demostrar que, para cualquier $1\le i<j\le n$, que existe $1\le k\le n/2$ tal que $ik\pmod{n+1}$ $jk\pmod{n+1}$ difieren por 1, es decir, $ik-jk\equiv\pm1\pmod{n+1}$. La adecuada $k$ elegir es $k\equiv\pm(i-j)^{-1}\pmod{n+1}$, con el signo elegido para que el residuo se encuentra entre el $1$ $n$ más que entre $n+1$$2n$.

Answer 2

Básicamente, se le da un grafo completo, y usted tiene que elegir el número mínimo de caminos hamiltonianos (o ciclos, si la tabla es circular) que cubra todos los bordes.

Cuando hay un número par de personas, es un conocido teorema que $K_{2n}$ puede ser descompuesto en $n$ borde discontinuo caminos hamiltonianos. (Véase la Moderna Teoría de grafos, página 16, por ejemplo, o ver una anterior respuesta que tiene una instantánea del libro en línea).

Al $n$ es impar, se puede hacer aún mejor, y hacer de $\frac{n-1}{2}$ de los ciclos!

Así que, si quieres caminos, por $2k$ respuesta es $k$ $2k+1$ respuesta es $k+1$.

Si desea ciclos, los valores se cambian.

Creo que esas son óptimas.