Cuestión relativa a la enumeración de los vértices de un prisma (número de dos vértices adyacentes pueden sólo se diferencian por una cierta cantidad)

Question

Hay 100 vértices de un prisma con un 50-gon en su base. Los vértices se asignan números enteros de 1 a 100 (ambos inclusive), en un orden aleatorio. Cada número puede ser asignado solamente una vez. El objetivo es demostrar que siempre hay dos vértices adyacentes (dos vértices que están conectados por una arista), cuyo número se diferencian por 48 o menos.

Para probar esto, creo que es el vértice que se le asigna el número entero $50$. Dispone de 3 'vecinos', y hay sólo 3 números en el conjunto dado que difieren por más de 48 de 50: $1$, $99$, $100$.

Ahora hay 3 casos posibles: cada uno de los números puede estar en el 'opuesto' lado del prisma. Para 1 y 99, es fácil mostrar que hay vértices adyacentes que se diferencian por 48 o menos. En arte ASCII:

100---50---99 | | 1----X

X > 1+48=49 y X < 99-48=51, lo que significaría que X=50, sin embargo, el número entero de 50 fue asignado previamente. Posteriormente hay bordes que se diferencian por 48 o menos.

100---50---1 | | 99---X

Aquí tenemos el mismo problema. X tendría que ser de 50, pero los 50 ya estaba asignado.

Si nosotros, sin embargo, elegir 100 a estar en el lado opuesto, me encuentro con un problema:

1---50---99---48 ... 2---X | | | | ... | 51--100--49---98 ... 52

Necesito un larguísimo 'cadena' para llegar a un conflicto, y yo supongo que este no es el buen o buena manera de probar que la declaración en cuestión. Por favor me ilumine!

Answer 1

Deje $(n,m)$ significa que $n$ $m$ son en partes opuestas del prisma de cada uno de los otros y deje $A_n$ ser el margen de conjunto de los vecinos para $n$ - los números que son más de 48 lejos de $n$ y que no se me ha dado, ya que las etiquetas ya.

Se deduce que debido a que el 50 está en el medio de [1,100], $A_{50}=\{1,99,100\}$ y, a continuación, por el caso de ruptura que debemos tener $(50,100)$. Ya que hay una cantidad de números en el rango, sin embargo, que realmente conseguir dos "medio" de los números, 51. Por el mismo razonamiento, entonces tenemos que $A_{51}=\{1,2,100\}$. Esto muestra que 50 y 51 de tener que compartir el 1 y el 100, como vecinos, que nos obliga a tener $(1,51)$. Esto a su vez obliga a la localización de los 2.

Ahora podemos jugar el mismo juego con la "next-más de en medio" de los números, 49 y 52. $A_{49}=\{98,99,100\}$ $A_{52}=\{1,2,3\}$ . Desde el 1, 2, 99, y 100 ya están colocados, esto obliga a la ubicación de 49 y 52, así como el resto de los valores en sus siglas en conjuntos. Continuar de esta manera, expandiéndose hacia fuera desde el centro de la gama. En cada punto de sus ubicaciones son forzados. Usted comenzará a ver un patrón en la colocación de las etiquetas. ¿Qué ocurre en el punto donde los dos "extremos" que se están expandiendo fuera de$(50,100)$? ¿Qué conclusión puedes sacar de esto?