Un problema con 26 enteros positivos distintos

Question

Intento resolver el siguiente problema.

Supongamos que nos dan 26 números enteros positivos distintos. Demuestre que o bien existen 6 de ellos $x_1<x_2<x_3<x_4<x_5<x_6$ con $x_1$ dividiendo $x_2$ , $x_2$ dividiendo $x_3$ , $x_3$ dividiendo $x_4$ , $x_4$ dividiendo $x_5$ y $x_5$ dividiendo $x_6$ o existen seis de ellos, de tal manera que ninguno de ellos divide a otro de estos seis.

Un posible buen comienzo es suponer que, en cada seis de estos números, existe al menos uno que divide a otro de los mismos seis.

Actualización. He encontrado una solución del problema (para 17 números sin embargo) en un sitio ruso. ¡Por increíble que parezca, este problema era una pregunta en un concurso soviético de matemáticas de 1983 ( ) para estudiantes de 7-8 grados!

A continuación presento la solución que encontré en ese sitio como respuesta, y se generaliza para $n^2+1$ enteros distintos, donde demostramos que o bien existen $n+1$ de ellos dividiéndose entre sí o no buceando ninguno más.

Answer 1

Solicitar Teorema de Dilworth al poset del $26$ enteros bajo la relación de divisibilidad. O bien existe una anticadena de longitud $6$ (no hay dos de $6$ enteros se dividen entre sí) o el conjunto puede dividirse como máximo en $5$ cadenas (secuencias en las que cada entero divide al siguiente), una de las cuales debe tener una longitud mínima de $6$ por el principio del encasillamiento.

Answer 2

Definir una cadena como una secuencia $(y_j)$ tal que $y_1|y_2 |...|y_k$ y una anticadena una secuencia $(y_j)$ tal que $y_1 \nmid y_2 \nmid .. \nmid y_k$ .

A cada uno $x$ en la secuencia inicial adjuntar un par de números $(i_x,j_x)$ tal que $i_x$ es la longitud de la cadena más larga finalizando en $x$ y $j_x$ es la longitud de la anticadena más larga a partir de $x$ .

Elija ahora dos elementos $x\neq y$ tal que $x$ es antes $y$ en la secuencia $(x_n)$ . Si $x | y$ entonces $i_x<i_y$ ya que cualquier cadena que termine en $x$ puede ampliarse a una cadena más larga terminada en $y$ . Si $x \nmid y$ entonces $j_x > j_y$ ya que cualquier anticadena que comience en $y$ puede ampliarse a una anticadena más larga a partir de $x$ . Por lo tanto, la aplicación $x \mapsto (i_x,j_x)$ es inyectiva.

Consideremos una secuencia con $mn+1$ elementos, y supongamos que la longitud de la cadena más larga es $m$ y la longitud de la anticadena más larga es $n$ . Por lo tanto, el mapa $x \mapsto (i_x,j_x)$ es una inyección de un conjunto con $mn+1$ elementos en un conjunto con $mn$ elementos. Esto es una contradicción que demuestra que existe una cadena de longitud $m+1$ o una anticadena de longitud $n+1$ .

En el problema presentado aquí tenemos $m=n=5$ .

Answer 3

He encontrado esta solución (para 17 números sin embargo) en un Sitio ruso ya que este problema fue una pregunta de un concurso soviético de matemáticas de 1983 ( ¡) para estudiantes de 7-8 clases!

Solución. Adjuntaremos en cada uno de nuestros números $$ x_1<x_2<\cdots<x_{26}, $$ un índice junto a su subíndice de la siguiente manera:

$x_1$ se convierte en $x_{1,1}$ .

Si $x_1$ divide $x_2$ entonces $x_2$ se convierte en $x_{2,2}$ de lo contrario se convierte en $x_{2,1}$ .

En general, si hemos adjuntado índices a $x_1,\ldots,x_k$ entonces el índice de $x_{k+1}$ será $1$ es ninguno de los $x_1,\ldots,x_k$ divide $x_{k+1}$ o se convertirá en $i+1$ si $i$ es el mayor índice de todos los números que dividen a $x_{k+1}$ .

Si el índice de algunos de los $x_j$ es al menos $6$ entonces tenemos una secuencia $$ x_{k_1,1} \mid x_{k_2,2} \mid x_{k_3,3} \mid x_{k_4,4} \mid x_{k_5,5}\mid x_{k_6,6}. $$ En todos los índices son inferiores o iguales a $5$ entonces algún número en $\{1,2,3,4,5\}$ , digamos $j$ es necesariamente el índice de al menos $6$ números, es decir $$ x_{k_1,j} < x_{k_2,j} < x_{k_3,j} < x_{k_4,j} < x_{k_5,j} < x_{k_6,j}, $$ lo que significa que ninguna de las anteriores $6$ los números dividen a otro de ellos.

Nota. Esto se puede generalizar para encontrar una cadena de $k$ números, totalmente ordenados por división, o un subconjunto de $\ell$ números, sin que ninguno de ellos divida a otro, entre $m$ enteros positivos distintos, siempre que $(k-1)(\ell-1)\le m-1$ .