Un conjunto de números enteros cuyos elementos todos brecha $2015^{200}$ pero no se dividen entre sí

Question

Deje $S$ ser un conjunto de números naturales,de tal manera que cada elemento se divide $2015^{200}$, pero para el no hay dos elementos $a$ y $b$, $a|b$. Encontrar el máximo número de elementos en $S$ .

$2015^{200}=(5\cdot 13\cdot 31)^{200}$

Por lo tanto, cada elemento es de la forma $5^p13^q31^r$ donde $p,q,r$ se encuentran entre el $0$$200$, inclusive.La condición dada también dice que para el no hay dos elementos $5^p13^q31^r$ y $5^a13^b31^c$,$p\le a,q\le b,r\le c$.

He tratado de adivinar la solución fijando el valor de $a$ y, a continuación, dejando $b$ $c$ a través de la gama de valores que les permita tomar.Pero sigo recibiendo confundido de nuevo y de nuevo.

Agradezco cualquier tipo de comentario,sugerencia o respuesta.

EDITAR:

Como se ha señalado en los comentarios de abajo,un trivial límite superior es $201^2$. Pero, ¿es realizable?Podemos demostrar que no es?Porque entonces podemos ganar un poco de perspectiva.

Answer 1

Tenga en cuenta que cualquiera de los dos elementos distintos $5^{p_1} 13^{q_1} 31^{r_1}$ $5^{p_2} 13^{q_2} 31^{r_2}$ son incomparables (ni divide los otros) si $p_1 + q_1 + r_1 = p_2 + q_2 + r_2$. Así que una solución mutuamente incomparable conjunto está dada por $$ S_n = \left\{5^p 13^q 31^r \;\big\vert\; p+q+r=n;\; 0\le, p,q,r \le 200\right\} $$ para cualquier $n$. El tamaño de este conjunto es máxima cuando $n=300$ (*). Para demostrar que este es el más grande mutuamente incomparable conjunto, podemos aplicar Dilworth del teoremaque dice que si un antichain $A$ tiene cardinalidad igual a la de una partición $P$ del conjunto, en cadenas, a continuación, que antichain es máxima. Una partición correspondiente aquí está dada por (el cierre transitivo de) la siguiente relación de equivalencia: si $x=5^p 13^q 31^r$, luego

• Si $p+q+r\equiv 0$ (mod $3$), $x \sim 5x$,
• Si $p+q+r\equiv 1$ (mod $3$), $x \sim 13x$, y
• Si $p+q+r\equiv 2$ (mod $3$), $x \sim 31x$.

La equivalencia de la relación de enlaces de cada triple $(p,q,r)$ a un único triple con $p+q+r=300$, y lo hace mientras se alojan en el interior de la caja de $0\le p,q,r \le 200$. (La última propiedad es la clave, ya que distingue, dicen, $S_{300}$ de la menor $S_{200}$.)

---

Nota sobre la evaluación de la $|S_n|$:

Sólo las restricciones $p,q,r\ge 0$ aplicar para $0 \le n\le 200$, por lo que el número de formas de elegir los $(p,q,r)$ sumando a $n$ en ese rango es $$|S_n|=1+2+\ldots+n+(n+1)=\frac{1}{2}(n+1)(n+2).$$ For $200<n \le 300$, we have to subtract out cases where one of the terms (and it can be only one) is larger than $200$: there are $$1+2+\ldots+(n-200)=\frac{1}{2}(n-200)(n-199)$$ cases where each of $p,q,r$ is greater than $200$. Por lo que el tamaño total es $$ |S_n|=\frac{1}{2}(n+1)(n+2)-\frac{3}{2}(n-200)(n-199) $$ en este rango. (Por lo $|S_{300}|=30301=|S_{299}|+1$.) Finalmente, para $n>300$, podemos usar la simetría, debido a $|S_{n}|=|S_{600-n}|$.