Considere cualquier $10$ diferentes enteros positivos. Demuestra que puedes elegir cuatro números de entre los diez números ( $a<b<c<d$ ), tal que para dos números cualesquiera $x<y\in \{a,b,c,d\}$ , $x|y$ o para dos números cualesquiera $x<y\in \{a,b,c,d\}$ , $x$ no es un divisor de $y$ .
Respuesta
¿Demasiados anuncios?
Kevin Long
Puntos
810
Esto puede ir fuera de su visión de este problema como un problema de teoría de grafos, pero hay un concepto más general que se está aplicando aquí conocido como Teorema de Dilworth . Piensa en estos números formando un dígrafo, donde $(x,y)$ es una arista dirigida si $x|y$ . Obsérvese que este dígrafo tiene la propiedad transitiva, es decir, que si $(x,y)$ y $(y,z)$ son aristas, entonces $(x,z)$ es también una arista, y la propiedad antisimétrica, que si $(x,y)$ es una arista y $x\neq y$ entonces $(y,x)$ no es un borde. Todo esto se deduce de nuestro conocimiento de la divisibilidad.
De hecho, tenemos aquí una estructura poset, donde $x<y$ si $(x,y)$ es un borde. Por el teorema de Dilworth, la mayor anticadena es el tamaño de la menor partición del poset en cadenas. Si este tamaño es al menos $4$ , entonces nuestro tamaño $4$ La anticadena es un conjunto de elementos que no están relacionados entre sí, es decir, que ninguno divide a otro. Entonces supongamos que este tamaño es menor que $4$ es decir, como máximo $3$ . Entonces una de nuestras cadenas debe tener tamaño al menos $4$ . Si no, tendríamos como máximo $3$ con un máximo de $3$ elementos cada uno, lo que significa que tenemos como máximo $9$ elementos, una contradicción. Entonces, nuestra cadena de tamaño mínimo $4$ es un conjunto de números donde para cada par, uno divide al otro. Aquí es donde entra su intuición- necesitamos $10$ porque supera $3\times 3$ .
