Conjunto de enteros positivos

Question

Dejemos que $A$ sea un conjunto de enteros positivos con las siguientes propiedades:

a) Si $n \in A$ entonces $n \leq 2018$

b) Si $S$ es un subconjunto de $A$ con $|S|=3$ entonces hay dos elementos $m,n \in S$ tal que $|n-m| \geq \sqrt{m}+\sqrt{n}$ .

¿Cuál es el número máximo de elementos $A$ puede tener?

Mi intento :

En primer lugar, $|n-m| \geq \sqrt{m}+\sqrt{n}$ reescrituras (WLOG $n \geq m$ ) $n-\sqrt{n} \geq m+\sqrt{m}$ o $(\sqrt{n}-1/2)^2 \geq (\sqrt{m}+1/2)^2$ o $\sqrt{n} \geq \sqrt{m}+1$ o $m \leq (\sqrt{n}-1)^2=n-2\sqrt{n}+1$

He conseguido demostrar que $|A| \leq 1344$ Y SI $2018 \in A$ entonces esto se mejora, pero nada más. ¿Alguna ayuda?

SOY UN BASURERO, ASÍ QUE ESCRIBÍ $n \geq 2018$ en lugar de $n \leq 2018$ Lo siento.

Answer 1

El conjunto $A:=\{2^k:\ k\geq11\}$ es infinito y tiene las propiedades deseadas, por lo que no hay un número máximo de elementos que $A$ puede tener.

Answer 2

Si $A = \{a_1, \dots, a_n\}$ , $a_k < a_{k + 1}$ entonces puede considerar $A' := \{a_1, \dots, a_n, 2 a_n\}$ , $|A'| > |A|$ . Si $S = \{a_i, a_j, 2 a_n\}$ y $|a_i - a_j| < \sqrt a_i + \sqrt a_j$ entonces WLOG $|a_n - a_i| \ge \sqrt a_n + \sqrt a_i$ y $$|2 a_n - a_i| = a_n + |a_n - a_i| \ge a_n + \sqrt a_n + \sqrt a_i \ge \sqrt a_i + \sqrt {2 a_n}.$$

Answer 3

Tengo algunas ideas que ofrecer sobre este problema. Algunas serán rigurosas y otras serán más intuitivas, pero proporcionarán una base para seguir investigando. Así que considere esto como una exploración detallada.

Definición de términos

Refiriéndonos al problema originalmente planteado, nos referiremos al conjunto $A$ que cumple las condiciones dadas como el \textit {conjunto de soluciones} o a veces simplemente como $A$ . Nos referiremos al subconjunto de 3 elementos $S$ de $A$ como \textit {el subconjunto} o \textit {un subconjunto} o simplemente $S$ . Y llamaremos a las condiciones de $|n-m| \geq \sqrt{n}+\sqrt{m}$ que se aplica a un par de elementos en $S$ como simplemente, \textit {las condiciones}.

Un comentario: El límite superior determinado inicialmente

Desde $A \subset \mathbb{N}$ entonces para dos elementos enteros positivos distintos $m, n \in A$ es obvio que $\sqrt{m}+\sqrt{n} > 2$ . Por lo tanto, cualquier $S \subset A$ que satisfaga las condiciones debe tener dos elementos con una diferencia de al menos 3. Entonces se deduce que no puede haber 3 enteros positivos consecutivos en cualquier lugar de $A$ . Eso lleva a $|A| \leq \frac{2}{3}\times2018 < 1345$ , \textit {es decir, }, $|A| \leq 1344$ .

Acotar el problema

Para determinar el número máximo de elementos que puede tener el conjunto solución, es útil caracterizar lo que el contenido de este conjunto, $A$ se ve como Supondremos que los elementos de $A = \{ a_1, a_2, a_3, ..., a_N \}$ están en orden creciente de manera que $a_i < a_j$ si $i < j$ .

Las condiciones del problema dictan que sólo consideremos subconjuntos de 3 elementos $S$ de $A$ . Al considerar tales subconjuntos, argumentaré que sólo necesitamos considerar aquellos subconjuntos cuyos elementos son consecutivos en $A$ : $S = \{ a_i, a_{i+1}, a_{i+2} \}$ para $1 \leq i \leq N-2$ . El motivo es la siguiente afirmación que es bastante fácil de demostrar:

Si tenemos $n, m \in \mathbb{N}$ y $\vert n - m\vert \geq \sqrt{n} + \sqrt{m}$ entonces es cierto que $|n_1 - m_1| \geq \sqrt{n_1} + \sqrt{m_1}$ para $n_1 \geq n$ y $1 \leq m_1 \leq m$ .

(Para demostrarlo, represente $n_1 = n + a$ y $m_1 = m - b$ para algunos $a, b \in \mathbb{N}_0$ .)

Si podemos asegurar, entonces, que todos los subconjuntos $S$ de $A$ que se compone de 3 elementos consecutivos en $A$ cumplir con la condiciones, entonces todos los subconjuntos de 3 elementos de $A$ cumplirá las condiciones.

Caracterización de $A$

El límite superior determinado inicialmente para $|A|$ asumió la menor diferencia posible entre valores en $A$ en toda la gama de valores de $A$ . Sin embargo, debido a las condiciones (de nuevo, sólo considerando subconjuntos de elementos consecutivos como estamos asumiendo ahora), la diferencia entre elementos debe, en en promedio, seguir aumentando a medida que los elementos se hacen más grandes. Digo "en promedio" porque estamos considerando subconjuntos de 3 elementos de $A$ y las condiciones sólo se requieren para un par de esos 3 elementos, lo que potencialmente permite que dos de los elementos tengan una diferencia arbitrariamente pequeña $\geq 1$ .

Si tenemos $A = \{a_1, a_2, a_3, ...\}$ y si queremos considerar un subconjunto $S = \{a_i, a_{i+1}, a_{i+2}\}$ , debemos aplicar las condiciones a $a_i$ y $a_{i+2}$ en cada caso, lo que hará que $S$ lo más compacto posible y, por lo tanto, $A$ lo más compacto posible y maximizar el número de elementos en $A$ . Es decir, aplicando las a un par de elementos consecutivos en $S$ crea más distancia global entre los elementos de $S$ . Además, cuando aplicamos las condiciones, queremos estar lo más cerca posible de la igualdad en la condición. Es decir, en es decir, queremos, para cada $S$ que $a_{i+2}$ sea el menor valor mayor que $a_i$ tal que $a_i$ y $a_{i+2}$ cumplir la condición. El mismo proceso de pensamiento se aplica si consideramos el subconjunto $S' = \{a_{i+1}, a_{i+2}, a_{i+3}\}$ y así sucesivamente.

Construyendo $A$

Basado en la caracterización anterior, $A$ puede construirse como dos secuencias intercaladas, los elementos impar y Par, cada uno de cuyos elementos consecutivos cumple la condición dada. Si queremos hacer $A$ lo más compacto posible, maximizando la número de elementos, querríamos empezar con 1 y 2 como elementos iniciales, $A = \{1, 2, ...\}$ .

Para determinar qué elementos deben venir a continuación, podemos manipular la condición original de la siguiente manera:

$$|a_{k+2} - a_k| \geq \sqrt{a_{k+2}} + \sqrt{a_k}$$ Desde $a_{k+2} > a_k$ : $$a_{k+2} - a_k \geq \sqrt{a_{k+2}} + \sqrt{a_k}$$ Dividiendo ambos tamaños por $\sqrt{a_{k+2}} + \sqrt{a_k}$ : $$\sqrt{a_{k+2}} - \sqrt{a_k} \geq 1$$ O: $$a_{k+2} \geq (\sqrt{a_k}+1)^2$$ Para el conjunto más compacto $A$ : $$a_{k+2} = \lceil (\sqrt{a_k}+1)^2\rceil$$

Utilizando esta fórmula, obtenemos lo siguiente para $A$ al comenzar con $1, 2$ :

$$1, 2, 4, 6, 9, 12, 16, 20, ...$$

El impar y las subsecuencias pares son geométricas. En este caso concreto, se pueden calcular con la siguiente forma cerrada:

$$a_k = \begin{cases} (\frac{k+1}{2})^2, & \text{if $k$ is odd} \\[2ex] \frac{k(k+2)}{4}, & \text{if $k$ is even} \end{cases}$$

Si construimos $A$ así hasta su valor máximo de elemento potencial de 2018, obtendremos:

$$1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, ..., 1849, 1892, 1936, 1980$$

El siguiente valor por encima de $1980$ sería $2025$ que es $> 2018$ .

¿Cuántos elementos hay en este $A$ ? Podemos sumar el número de elementos indexados Impares y el número de elementos pares elementos indexados. Estos se calculan resolviendo $n^2 = 2018$ y $n(n+1) = 2018$ para $n$ :

$$|A| = \lfloor\sqrt{2018}\rfloor + \lfloor\frac{-1+\sqrt{-1+4(2018)}}{2}\rfloor = 44 + 44 = 88$$

¿Hemos encontrado el mayor conjunto $A$ ?

Sobre la base de cómo construimos $A$ no se pueden insertar valores adicionales y seguir cumpliendo con el original condiciones originales. Creo que se puede demostrar que lo siguiente es cierto (como que he trabajado en ello, pero necesito ir volver a comprobar mi trabajo para estar seguro):

Si $n, k \in \mathbb{N}$ y $n > k^2$ , entonces el valor $n = (k+1)^2$ es el valor más pequeño de $n$ que cumple la condición, $|n-k^2| \geq \sqrt{n}+k$ . También se puede demostrar de forma similar que $n = (k+1)(k+2)$ es el valor más pequeño que cumple la condición, $|n-k(k+1)| \geq \sqrt{n}+\sqrt{k(k+1)}$ .

En otras palabras, nuestra construcción, asumiendo que empezamos en $1, 2$ , eligió los valores subsiguientes tan pequeños como posible en cada paso del proceso, maximizando así el tamaño de $A$ en ese caso.

También puedes considerar otros valores de partida. ¿Qué pasa con $2, 3$ por ejemplo? Lo he intentado y, utilizando la fórmula anterior, he obtenido:

$$2, 3, 6, 8, 12, 15, 20, 24, 30, 35, 42, ...$$

Que se produce por la siguiente forma cerrada: $$a_k = \begin{cases} \frac{(k+1)(k+3)}{4}, & \text{if $k$ is odd} \\[2ex] \frac{k(k+4)}{4}, & \text{if $k$ is even} \end{cases}$$

Esto lleva a un conjunto $A$ con un máximo de 87 elementos.

A partir de $3, 4$ resultados en:

$$3, 4, 8, 9, 15, 16, 24, 25, 35, 36, ...$$

Y la siguiente forma cerrada:

$$a_k = \begin{cases} \frac{(k+1)(k+5)}{4}, & \text{if $k$ is odd} \\[2ex] (\frac{k+2}{2})^2, & \text{if $k$ is even} \end{cases}$$

Y luego $A$ tiene un máximo de 86 elementos.

Como es de esperar, si se empieza con números más altos como elementos iniciales en $A$ el tamaño máximo de $A$ disminuye más.

Conclusión

El análisis anterior no se hizo con todo rigor, pero el tamaño máximo de $A$ que cumple las condiciones parece ser 88 sobre la base de ese análisis.