¿El conjunto $X=\{1,2,\ldots,3000\}$ contienen un subconjunto $A$ de $2000$ enteros en los que ningún miembro de $A$ es dos veces otro miembro de $A$ ?
Empecé poniendo $P=[1501,3000]$ pero dos veces cualquier número entero en $P$ es demasiado grande para pertenecer a $X$ .
Estoy atascado y necesito ayuda.
Este es un problema bien conocido. Véase aquí con solución, publicado en 1996.
Resumiendo: Habiendo puesto [1501,3000] en nuestro conjunto, el intervalo [751,1500] queda excluido, por lo que necesitamos 500 de [1,750]. Habiendo añadido entonces [376,750] a nuestro conjunto, el intervalo [188,375] queda excluido, por lo que necesitamos 125 de [1,187]. Y recurrimos hasta el final.
No me parece que estas soluciones anteriores sean lo suficientemente buenas, parecen ser un poco tejidas a mano (asumen que cierta solución es la mejor y proceden a calcular en base a eso). Así que proporciono una solución, que eventualmente llegará a la misma conclusión.
Para cada número impar $n<3000$ , defina $P_{n}=\{2^{k}n|0\leq k;2^{k}n\leq 3000\}$ . Compruebe fácilmente que esos $P_{n}$ son disjuntos entre sí, y su unión disjunta es efectivamente $[1,3000]$ .
Ahora, considerando cualquier subconjunto $A$ . Podemos demostrar fácilmente que si para cada impar $n$ entonces $A\bigcap P_{n}$ no contienen ningún miembro dos veces otro, entonces $A$ también tendrá esa propiedad. Por lo tanto, la construcción de un $A$ con el máximo orden implican la construcción de todos aquellos $A\bigcap P_{n}$ que individualmente tienen el máximo orden. El máximo orden posible de $A\bigcap P_{n}$ es $[\frac{|P_{n}|+1}{2}]$ (el paréntesis significa piso, no sé cómo escribir ese paréntesis de piso).
Ahora la cuestión se reduce a encontrar el número de posibles $n$ de un valor determinado de $[\frac{|P_{n}|+1}{2}]$ . Esto no es demasiado difícil. Si $[\frac{|P_{n}|+1}{2}]=m$ para algún número entero $m$ entonces $|P_{n}|=2m-1$ o $2m$ . No sólo eso $|P_{n}|=k_{\max}+1$ donde $k_{\max}$ es el máximo $k$ tal que $2^{k}n\leq 3000$ . Por lo tanto, $k_{\max}=2m-2$ o $2m-1$ . En otras palabras, $2^{2m-2}n\leq 3000<2^{2m}n$ . El máximo posible $n$ en ese caso es $[\frac{3000}{2^{2(m-1)}}]$ y el mínimo es $[\frac{3000}{2^{2m}}]+1$ .
Lo único que queda es hacer realmente el cálculo de cada $m$ . Tenga en cuenta que buscamos a impar $n$ sólo.
Para $m=1$ obtenemos $751\leq n\leq 3000$ así que el número de posibles $n$ es $1125$ .
Para $m=2$ obtenemos $188\leq n\leq 750$ por lo que el número de posibles $n$ es $281$ .
Para $m=3$ obtenemos $47\leq n\leq 187$ por lo que el número de posibles $n$ es $71$ .
Para $m=4$ obtenemos $12\leq n\leq 46$ por lo que el número de posibles $n$ es $17$ .
Para $m=5$ obtenemos $3\leq n\leq 11$ por lo que el número de posibles $n$ es $5$ .
Para $m=6$ obtenemos $1\leq n\leq 2$ por lo que el número de posibles $n$ es $1$ .
Así que el orden máximo es $1\times 1125+2\times 281+3\times 71+4\times 17+5\times 5+6\times 1=1999$ . Por lo tanto, es imposible.
No estoy seguro de que todo esto sea correcto; sólo lo expondré para que la gente lo verifique.
Comenzar con todos los números de impar $\{1,\ldots,2999\}$ .
Sus dobles son números con un factor de $2$ Así que ahora suma todos los números con $2$ factores de $2$ . Este es el conjunto $\{4,12,20,28,\ldots\}$ . Ahora suma los números con $4$ factores de $2$ y así sucesivamente...
El número de números Impares es $$\left\lfloor \frac{3000-1}{2}\right\rfloor +1= 1500.$$ El número de números con $2$ factores de $2$ es $$\left\lfloor \frac{3000-4}{8}\right\rfloor +1 = 375.$$ Los siguientes son $$\left\lfloor \frac{3000-16}{32}\right\rfloor +1 =94 \\ \left\lfloor \frac{3000-64}{128}\right\rfloor +1=23 \\ \left\lfloor \frac{3000-256}{512}\right\rfloor +1=6 $$ y finalmente $1$ . Estas suman $$1500+375+94+23+6+1=1999$$ ¡Necesitamos uno más!
Esquema:
(1) Un número puede estar en el conjunto objetivo S si (a) el doble del número es mayor que 3.000 (conjunto $S_0$ ), o (b) el doble del número no está en S ( $S_1$ ; $S = S_0 \cup S_1$ ).
(2) si se elimina 1 número de $S_0$ ¿Cuántos números se pueden sumar ahora a $S_1$ ¿en el mejor de los casos? ¿Y en el caso inverso? Entonces, ¿qué conjunto se "llena primero"?
(3) Suponiendo que se eligen todos los de (a) como $S_0$ ¿Cuál es el mayor número entero $a$ que se añadirá a $S_1$ de (b) asumiendo que no hay solapamiento entre $S_0$ y $S_1$ ?
(3) cuántos enteros Impares $\le a$ están ahí? Suponiendo que elija todos, ¿puede añadir más pares? Si eliges un par $\le a$ ¿cuántas probabilidades hay que eliminar? Así que dado un máximo $S_0$ ¿Cuál es el tamaño máximo de $S_1$ ?
(4) concluir cuál es la mayor cardinalidad para $S= S_0 \cup S_1$ es
Considere el conjunto $N:=\{1,...,n\}$ y los subconjuntos de $N$ de tamaño máximo sujeto a ningún elemento de $N$ siendo dos veces otro. Entre estos subconjuntos, elija un conjunto $M$ que contiene el menor número de enteros pares. Sea $m\in M$ sea par. Entonces $m/2\not\in M$ . Si $m/2$ fuera impar, podríamos sustituir $m$ por ella y así obtener un conjunto con menos números pares; así cualquier elemento par de $M$ es divisible por $4$ . Siguiendo así, se ve fácilmente que $M$ comprende todos los elementos de $N$ de la forma $4^kl$ , donde $k$ es un número entero no negativo y $l$ es impar.
En el caso $N=\{1,...,3000\}$ podemos incluir en $M$ todo $1500$ Los enteros de impar, el $375$ Impares múltiplos de $4$ El $94$ Impares múltiplos de $16$ El $23$ Impares múltiplos de 64, el $6$ Impares múltiplos de $256$ y el solitario $1024$ : en conjunto $1500+375+94+23+6+1=1999$ números. Así que la respuesta es no, no podemos conseguirlo.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
