Demostrar que las 25 personas pueden estar sentadas de esta manera

Question

5 matemáticos, 5 biólogos, químicos 5, 5 físicos, y 5 de los economistas se sientan alrededor de una gran mesa redonda.

Demostrar que el 25 personas puede estar sentado de forma tal que, si a y B son dos personas diferentes con la misma especialidad (por ejemplo, dos matemáticos), entonces la gente que está sentado inmediatamente a la izquierda de a y a la izquierda de B son de diferentes especialidades (por ejemplo, un biólogo y químico).

Yo pensaba que el uso de la inducción, ya que $n=1$ y $n=2$ son fáciles de hacer. Sin embargo, no sé cómo continuar.

Answer 1

Vamos a comprobar esta generalización: Si hay $$ n de personas cada de $n$ las diferentes especialidades, a continuación, el $n^2$ la gente puede estar sentados alrededor de una mesa redonda en la que, si $A$ y $B$ son dos personas diferentes con la misma especialidad, entonces la gente que está sentado inmediatamente a la izquierda de a y a la izquierda inmediata de $B$ son de diferentes especialidades. (Nuestro problema es el caso $n=5$.)

Si $n=1$, entonces sólo hay una persona, por lo que la instrucción que estamos tratando de demostrar que es trivial. Si $n=2$, entonces hay dos personas en cada una de las dos especialidades. Pueden ser colocados de modo que ambas parejas de personas de la misma especialidad, están uno al lado del otro; este asientos satisface los requisitos del problema. Nosotros continuamos ahora por inducción.

Supongamos que podemos asiento $$ n de las personas en cada una de $n$ especialidades de acuerdo a las condiciones del problema. Ahora, considere el problema con $n+1$ de personas en cada una de $n+1$ especialidades. A nuestro actual de $n$-especialidad de asientos, necesitamos agregar $1$ por persona adicional de cada uno de los originales $n$ especialidades, además de $n+1$ de la gente de la nueva especialidad, que llamaremos $Z$.

Deje de $S$ ser uno de los originales $n$ especialidades, y considerar la izquierda vecinos de la original de $n$ personas desde $S$. Los vecinos deben tener diferentes especialidades (entre el original de $n$ especialidades), así que entre ellos debe haber exactamente una de cada original de la especialidad, incluyendo a S mismo. Por lo tanto no deben ser un par de especialistas en $S$ en asientos contiguos. Nos asiento de al $(n+1)^{\text{th}}$ persona $S$ y una persona de a $Z$ (en cualquier orden) entre el par adyacente de personas desde $S$. De esta manera hemos puesto una especialidad-$Z$ persona a la izquierda de una especialidad-$S$ persona, y una especialidad-$S$ persona a la izquierda de una especialidad-$Z$ persona; esto es todo lo que hemos hecho. Así, es todavía el caso de que no hay dos personas de la misma especialidad tienen las personas de la misma especialidad, como sus vecinos de la izquierda. Repetimos esta operación para todos $n$ opciones de especialidad $S$.

Finalmente, tenemos que añadir el $(n+1)^{\text{th}}$ de la especialidad-$Z$ persona. Podemos simplemente asiento a su lado a cualquier otra especialidad-$Z$ persona. Por construcción, todos los de la especialidad-$Z$ personas se han dejado a los vecinos de las diferentes especialidades.

Como un ejemplo, en nuestro problema, tenemos $5$ personas cada una de las especialidades M,B,C,P, a y E. se puede iterar el proceso anterior de la siguiente manera, donde la lista de abajo son considerados como empezar en algún punto sobre la mesa y yendo hacia la derecha:

$\begin{align} M \\MMBB \\ MMCCMBBCB\\ MMPPMCCPCMBBPBCB\\MMEEMPPEPMCCECPCMBBEBPBCB \end{align}$

Tenga en cuenta que en cada lista, no par de letras aparece dos veces en la secuencia.

Answer 2

Es una teoría de grafos problema. Lo que estás buscando es un circuito Euleriano en un grafo dirigido de la orden de los $5$, que consta de cinco vértices $M,B,C,P,E$ y $25$ dirigido bordes, una que va desde cada vértice a cualquier otro vértice y también uno de bucle de cada vértice a sí mismo. La existencia de un circuito Euleriano (es decir, atravesar cada arista exactamente una vez) en el gráfico se comprueba fácilmente; véase la respuesta a esta pregunta.

Para generalizaciones buscar secuencia De Bruijn.

Answer 3

Una prueba inductiva puede realizarse según el siguiente esquema:

$A\to un (ABB) \to A(ACBCC) (ABB) \to A(ADBDCDD)(ACBCC) (ABB) \to A(AEBECEDEE)(ADBDCDD)(ACBCC)(ABB)$ $

En cada etapa tienes $n$ personas de tipos de $n$, con todos $n ^ 2 pares consecutivos posible $.

Answer 4

Puede construir una solución por inducción. Supongamos que tiene una solución para $n$. Hay $n$ dobles-ponga un $n+1$ entre cada par y dos de ellos en uno de los espacios. Ahora todas $1$ $n $ tienen los vecinos necesarios excepto ellos mismos tan doble de cada uno. Así que a partir de $1221$ vamos a $1233213$ y luego a $112233213$ la siguiente es entonces $ $141242344213 y $114122423344213$

Answer 5

Dado que hay 5 tipos de personas, cada uno de los cuales se encuentra a la izquierda (o derecha) de UNA persona, esta relación puede ser mostrado como un cuadrado (persona por vecino). Además, el asiento va a ser una secuencia continua, donde la 'izquierda' persona de la actual pareja será el "derecho" a la persona de la siguiente pareja.

Cada vecino relación puede ser numerados del 1 al 25. Proporciona una relación tiene un número único y señala otra relación válida (a excepción de la última relación, por supuesto), entonces el sistema es válido.

M M B C P E B P M E C B B E E M M M M C C E P P C M P B M