Determina si el conjunto $\{1,2,3,\ldots,3000\}$ contiene un subconjunto $A$ con $2000$ elementos tal que si $x$ está en $A$, entonces $2x$ no está en $A$.
Muestra que hay a lo más $\frac{2^n}{n+1}$ palabras binarias de $n$ d\'igitos que difieren en al menos $3$ lugares cada dos de ellas.
martes, 21 de febrero de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
16 comentarios:
(a) Demostraré que no existe tal conjunto A. Consideremos los 1500 conjuntos $X_i=\{x \mid \displaystyle\frac{x}{2^{v_2(x)}}=2i-1$, $1 \le x \le 3000$, $x \in \mathbb{N} \} \forall i \in \{1,2,\ldots,1500\}$. Cada $X_i$ tiene como elementos a los números con mayor divisor impar $2i-1$. Entonces como $\forall n\in \{1, 2, \ldots, 1500\}, \exists i$ tal que $\{n, 2n\} \subset X_i$, es fácil ver que si $X_i$ tiene $f(i)$ elementos, el máximo tamaño de A es $\mid$$A \mid \le \displaystyle\sum_{i=1}^{1500} \lceil \frac{f(i)}{2} \rceil$. Ahora, es fácil ver que éste valor se obtiene cuando tenemos un conjunto $Y = \{x \mid x\in \{1, 2, \ldots, 3000\}, 2 \mid v_2(x)\}$, pues $\mid$$Y \cup X_i \mid = \lceil \frac{f(i)}{2} \rceil$ es fácil de ver (en $X_i$, los elementos en $Y$ y no en $Y$ se van alternando). Así. basta demostrar $\mid$$Y$$\mid \le 1999$. Pero ésto es fácil, pues $\mid$$Y\mid= \displaystyle\sum_{i=0}^{11} (-1)^i \times \lfloor \frac{3000}{2^i}\rfloor=3000-1500+750-375+187-93+46-23+11-5+2-1=1999$ (hasta el 11 pues $2^{11}$ es la máxima potencia de 2 menor a 3000), ésto se verifica a mano (no es muy tardado). Acabamos (de hecho 1999 se puede pero 2000 no). Quod erat demonstrandum. $\clubsuit$
Perdón, pero a veces intentando poner $\mid$$X$$\mid$, donde $X$ es algún conjunto, se pone la primera $\mid$ en un renglón y el resto en otro. Debería leerse como la cardinalidad del conjunto $X$. También, en donde no se alcanza a leer, dice $3000-1500+650-375+187$$-93+46-23+11-5+2-1=$$1999$.
Para el de los dobles en el conjunto, veamos que no existe el conjunto que buscamos. Primero veamos que podemos tomar los enteros del conjunto de manera única separándolos en $1500$ grupos, donde si consideramos a los enteros impares menores a $3000$, que les diremos $i_{1}, i_{2},\ldots, i_{1500}$, entonces los conjuntos $C_{1}, C_{2},\ldots, C_{1500}$ serán tales que en el conjunto $C_{j}$ están todos los enteros de la forma $2^{a}\cdot i_{j}$.
Ahora, es claro que la condición que queremos en el conjunto solo afecta a elementos dentro de un mismo $C_{j}$, así que veremos como maximizar la cantidad de elementos tomados dentro de cada $C_{j}$. Ahora, veamos que si ordenamos nuestros elementos de menor a mayor, no podemos elegir $2$ de ellos que sean consecutivos. Entonces, por Casillas, si en el conjunto $C_{j}$ hay $M_{j}$ elementos, podemos tomar a lo más
$\left\lroof \frac{M_{j}}{2}\right\rroof$
esa caja que no se ve es techo de $\frac{M_{j}}{2}$.
(b) Por inducción. Primero el caso base. El número con $n=3$ es 3, y si tengo 3 palabras de 3 dígitos, como las palabras que difieren en al menos 3 lugares se pueden poner "por parejas", si tengo 3, habrá 2 de diferentes parejas, por lo que éstas 2 tiene a lo más 2 dígitos diferentes. Ahora el paso inductivo. Demostraré que si tengo $\lfloor \frac{2^n}{n+1} \rfloor + 1$ palabras, habrá 2 que difieran en a lo más 2 dígitos. Si hay $\lfloor \frac{2^{n-1}}{n} \rfloor + 1$ palabras con el mismo primer dígito, por inducción habremos acabado. Podemos asegurar ésto por casillas si tenemos al menos $2\lfloor\frac{2^{n-1}}{n}\rfloor+1$ palabras. Así, si demostramos que $2\lfloor\frac{2^{n-1}}{n}\rfloor+1\le\lfloor \frac{2^n}{n+1} \rfloor + 1$, acabamos. Ésto es equivalente a $2\lfloor\frac{2^{n-1}}{n}\rfloor\le\lfloor \frac{2^n}{n+1} \rfloor$. Pero si no $\exists i \in \mathbb{N}\cup\{0\}$ tal que $2^i=n+1$, entonces podemos estar seguros de que, por la desigualdad $2\lfloor x \rfloor \le \lfloor 2x \rfloor$ para $x$ positiva, que $2\lfloor\frac{2^{n-1}}{n}\rfloor\le \lfloor\frac{2^{n}}{n}\rfloor = \lfloor \frac{2^n}{n+1} \rfloor$. Si sí existe tal $i$, digamos $2^i=n+1$, entonces $2\lfloor\frac{2^{n-1}}{n}\rfloor = \lfloor\frac{2^{n}}{n}\rfloor - 1 = \lfloor \frac{2^n}{n+1} \rfloor$. En cualquier caso, la desigualdad deseada se cumple, y se termina la inducción. Quod erat demonstrandum. $\clubsuit$.
Bueno, entonces, vemos que esto siempre lo podemos lograr tomando los elementos
$i_{j}, i_{j}2^{2}, i_{j}2^{4},\ldots$
Y en particular al hacer esto para cada $C_{j}$, tenemos que el máximo se logra al elegir todos los números de la manera $2^{2n}i$, donde $i$ es impar y $n$ es entero. Haciendo las cuentas, tenemos que la cantidad máxima que se puede lograr es
$1500+375+94+23+6+1=1999$
Que es menor a $2000$ y acabamos.
Inciso a) Hagámoslo más general, para el conjunto $\{1,2,\dots,3n\}$ buscaremos el subconjunto $A$ de mayor cardunalidad. Consideramos los
conjuntos $A_{i}=\{a: 1\leq a\leq 3n, a=2^{\alpha}(2i-1), a,\alpha\in\mathbb{Z^0}\}$, $\forall$ $i\in B$ con $B=\{1,2,\dots, \lfloor\frac{3n+1}{2}\rfloor\}$,
dónde $\mathbb{Z^0}$ es el conjunto de los enteros no negativos. Es más que claro que los elementos que tomemos de $A_{i}$ no afectan los que podremos tomar
de $A_{j}$ para $i,j\in B$. Además de que si tomamos a una $a$ par de algún conjunto, digamos $A_{i}$, ya no es posible tomar $2a$ a menos que este nunca
estuviera en el conjunto. Por esto, por cada elemento que tomemos, hay otro que no podremos tener, excepto por el último, así que lo más que podremos tener
es la mitad de ellos más el último (tal vez). Ahora veamos que si $|A_{i}|$ es par, entonces para cada $a\in A_{i}$ cuya $\alpha$ es impar, hay un elemento
que no podemos tomar si tomamos a esa $a$ (su mitad), y por cada $a\in A_{i}$ cuya $\alpha$ sea par, hay otra que no podemos tomar (el doble) así que a lo
más podemos tomar la mitad y se puede lograr tomando todos cuyos $\alpha$ son todos pares. De manera similar hacemos prara ver que si $|A_{i}|$ es impar,
entonces para toda $a\in A_{i}$ cuya $\alpha$ sea distinto $0$, hay al menos otro elemento de $A_{i}$ que no podemos tomar (su mitad), y además está el caso
en que $\alpha=0$, así que a lo más se puede tomar $\frac{A_{i}+1}{2}$ y sí es posible lograrlo, simplemente tomamos todos los elementos cuyas $\alpha$'s son
pares.
Haciendo todo lo anterior para cada $A_{i}$, notamos que hemos seleccionado del conjunto original, a todos los números de la forma $2^{\alpha}(2i-1)$ para
$\alpha$ par y para $i\in B$. Esto significa que el máximo valor de esta $|A|$ es, por el principio de inclusión exclusión (puesto que queremos a todos menos
los pares pero sí a los múltiimplos de cuatro, pero no a los de ocho, etc.): \[\sum_{i=0}^{\infty}{(-1)^{i}\lfloor\frac{3n}{2^{i}}\rfloor}\] Si ahora vemos lo que sucede en el caso particular de $3000$, veremos que de hecho este número es $1999$ así que la respuesta es no.
perdón, donde dice $\mathbb{Z^0}$ quería escribir $\mathbb{Z}^0$
P1:
Primero vemos que podemos dividir el conjunto $\left \{ 1,2,...,3000 \right \}$ en los conjuntos de la forma:
$C_{2k+1}=\left \{ 2k+1,2(2k+1),4(2k+1),...,2^{n_{k}}(2k+1) \right \}$
Con $2k+1\in \left \{ 1,2,...,3000 \right \}$ y $n_{k}$ sea el número más grande tal que $2^{n_{k}}(2k+1)\leq 3000$.
Primero, podemos ver que los conjuntos son disjuntos. Entonces podemos ver cómo optimizar la forma de escoger los números para nuestro nuestro conjunto aquí (podemos ver que la elección inteligente de números en cualquier $C_{2k+1}$ no afecta en la condición del problema a los demás).
Tomemos un conjunto $C_{2k+1}$ y digamos que $n_{k}$ es impar.
Sabemos que, viendo que los elementos del conjunto $C_{2k+1}$ están ordenados en una fila, lo que queremos evitar es tomar 2 elementos "consecutivos". La forma de tomar más números sin hacerlo con dos consecutivos es tomándolos de manera alternada. Como la cardinalidad del conjunto es par (hay $n_{k}+1$ elementos), hay 2 maneras máximas de tomar alternadamente. Por lo que tomaremos el subconjunto:
$\left \{ 2k+1,4(2k+1),...,2^{n_{k}-1}(2k+1) \right \}$
Si $n_{k}$ es par, el conjunto $C_{2k+1}$ tiene un número impar de elementos. Sabemos que optimizando tenemos que tomar intercalados, pero hay una manera de tomar intercalados con más elementos que otra. Esta es tomar los números:
$\left \{ 2k+1,4(2k+1),...,2^{n_{k}}(2k+1) \right \}$
Haciendo esto con todos los conjuntos $C_{2k+1}$ tenemos un conjunto optimizado.
Pero veamos que la unión de cada conjunto derivado de la optimización de su correspondiente $C_{2k+1}$ forma los el conjunto de números $1\leq x\leq 3000, x=2^{2r}p$, con $p$ impar. Entonces el conjunto con más elementos es exactamente el mismo que este.
Pero el conjunto recién mencionado tiene cardinalidad:
$S=\left \lfloor \frac{3000}{1} \right \rfloor-\left \lfloor \frac{3000}{2} \right \rfloor+\left \lfloor \frac{3000}{4} \right \rfloor-...$
Primero se cuenta la cantidad de números múltiplos de $2^0$ en 3000, le quitamos la cantidad de números múltiplos de $2^1$ pero le sumamos la cantidad de números múltiplos de $2^2$ y así sucesivamente. Con un poco de cuentas aburridas tenemos que:
$S=3000-1500+750-375+187-93+46-23+11-5+2-1=1999$
Como la optimización nos dio una cardinalidad menor a 2000, no se puede!
@Juan: revisa bien tus casos y todo lo que asumes... ¿estás seguro de que:
$\lfloor\frac{2^{6}}{6}\rfloor=\lfloor\frac{2^{6}}{7}\rfloor$ y de que
el caso que te preocupa es cuando $n+1$ es potencia de dos? no te refieres a muchísimos más casos? en particular $n=4$ no cumple tu inducción, es decir que $2\lfloor\frac{2^{3}}{4}\rfloor+1\leq \lfloor\frac{2^{4}}{5}\rfloor+1$? Creo que debes revisar tu solución Juan.
a) Sea $X={1,2,...,3000}$. Partimos el conjunto ${1,2,...,3000}$ en subconjuntos de la forma ${x,2x}$ con $v_{2}(x)=2^{2k}$ para $k=0,1,2,...,5$ (si $2x$ no pertenece a $1,2,...,3000$, en lugar de ${x,2x}$ consideramos sólo al subconjunto ${x}$). Todo elemento de $X$ está en uno de estos subconjuntos, ya que por construcción todo $y$ menor o igual que $3000$ tal que $v_{2}(y)=2^{2k}$ está en uno (la máxima potencia par de $2$ que divide a un elemento de $X$ es $10$), y como todo $y$ menor o igual que $3000$ tal que $v_{2}(y)=2^{2k+1}$ cumple que $y/2\in X$ y está en uno de esos subconjuntos, por lo que $y$ pertenece a uno de ellos. Ahora, hay $\lfloor\frac{3000}{2^{2k}}\rfloor-\lfloor\frac{3000}{2^{2k+1}}\rfloor$ subconjuntos de la forma ${x,2x}$ con $v_{2}(x)=2^{2k}$, pues ésta es la cantidad de múltiplos de $2^{2k}$ menos la cantidad de múltiplos de $2^{2k+1}$, que es la cantidad de números $x$ con $v_{2}(x)=2^{2k}$, y hay un subconjunto de esa forma por cada uno de esos $x$. Sumando los valores de $\lfloor\frac{3000}{2^{2k}}\rfloor-\lfloor\frac{3000}{2^{2k+1}}\rfloor$ para $k=0,1,2,3,4,5$, obtenemos que hay $1999$ de estos subconjuntos, y si existiera $A$ con $2000$ elementos, al menos $2$ de ellos estarían en un mismo subconjunto, lo cual implicaría que uno sería el doble del otro, lo cual es imposible. Por lo tanto, $A$ no existe.
a)
Cada numero podemos escribirlo como una potencia de dos por un impar, y separamos los numeros del conjunto inicial en 1500 subconjuntos en que todos los que tienen el mismo impar en esta descomposicion estan en en mismo subconjunto.
Por la forma de construirlos no hay dos numeros en subconjuntos distintos tal que uno es el doble del otro, por lo tanto solo hay que cuidar la condicion del problema en cada subconjunto.
Hay que construir el conjunto $A$' que cumpla que si esta $x$ entonces $2x$ no esta y tiene la mayor cardinalidad posible.
$B_i=\{i,2i,4i,\dots,2^ki\}$
$2^ki \leq 3000$
Si lo separamos en parejas $(i,2i),(4i,8i),\dots$, y en el subconjunto $A$' hay mas de $\lceil \frac{k}{2} \rceil$ por casillas habra dos de la misma pareja y uno sera el doble del otro, entonces lo maximo es $\lceil \frac{k}{2} \rceil$, que si sera posible cuando tomamos todas las potencias pares de dos.
Asi podemos ver que $A$' esta integrado por numeros menores a $3000$ de la forma $2^{2k}i$ con $i$ impar.
Con inclusion y exclusion vemos que la forma de contar esto es:
$\mid A$'$\mid =\lfloor \frac{3000}{1} \rfloor - \lfloor \frac{3000}{2} \rfloor + \lfloor \frac{3000}{4} \rfloor - \dots $
Y haciendo las cuentas te da que
$\mid A$'$\mid=1999 \textless 2000$
Por lo tanto $A$ no existe.
a) Supongamos que existe A como la pide el problema
Formemos los conjuntos
$C_i=\{i,2i,4i,...,2^ni\}$ con i impar entre 1 y 2999 y $2^ni\le 3000$ si los agrupamos por parejas $(i,2i),(4i,8i),...$ por el principio de las casillas hay a lo más $\lceil \frac{n}{2} \rceil$ elementos de $C_i$ en A, en otro caso abría dos de la misma pareja, contradicción.
Entonces la cardinalidad de A es a lo más la suma de los techos de la mitad de la cardinalidad de los conjutos $C_i$, que se puede ver como la suma de las potencias pares de 2 por un impar, menos las potencias impares de 2 por un impar; que es lo mismo que
$1999=\left \lfloor \frac{3000}{1} \right \rfloor-\left \lfloor \frac{3000}{2} \right \rfloor+\left \lfloor \frac{3000}{4} \right \rfloor-...$
por inclusion y exclusion
Contradicción. Por lo tanto no existe A como lo pide el problema.
Publicar un comentario