Decimos que un subconjunto $S$ de $\{1,2,...,n\}$ es equilibrado si tiene la siguiente propiedad: Cada que $a$ y $b$ sean elementos de $S$ cuyo promedio sea un entero, dicho promedio también será un elemento de $S$.
Sea $A(n)$ el número de subconjutnos equilibrados de $\{1,2,...,n\}$. Encuentra todos los enteros positivos $n$ tal que $A(n+2)-2A(n+1)+A(n)=1$.
Ejemplo: Todos los subonjuntos de $\{1,2,3\}$ son equilibrados excepto el $\{1,3\}$, por lo tanto $A(3)=7$.
martes, 18 de agosto de 2015
Suscribirse a:
Comentarios de la entrada (Atom)
6 comentarios:
Mi solución está algo larga, ojalá no esté muy confusa.
Extendemos la definición de subconjunto equilibrado a cualquier conjunto de enteros.
Sea $B(n)$ el número de subconjuntos equilibrados de $[n]$ que no contienen a 1 y $C(n)$ el número que sí lo contienen, entonces $A(n) = B(n) + C(n)$. Ahora veamos que todo subconjunto equilibrado de $[n]$ que no contiene a 1 es un subconjunto de $\{2, 3, \dots, n\}$. Restando 1 a cada elemento de este subconjunto obtenemos un subconjunto de $[n - 1]$ que es equilibrado si y solo si el conjunto original lo es, entonces $B(n) = A(n - 1)$ ($A(0) = 1$). Ahora, la condición equivale a:
$$1 = (A(n + 2) - A(n + 1)) - (A(n + 1) - A(n)) = C(n + 2) - C(n + 1)$$
Usando que $A(n) = B(n) + C(n)$ y la recursión que obtuvimos. Ya que todo subconjunto que contiene a 1 y es equilibrado para $n + 1$ es también equilibrado para $n + 2$, la condición es equivalente a que exista un único subconjunto equilibrado de $n + 2$ que contiene tanto a $1$ como a $n + 1$. Además, $\{1, 2, 3, \dots, n + 1\}$ cumple esto, por lo cuál la condición equivale a que este sea el único subconjunto que lo cumpla.
Sea $n + 1 = 2^k \cdot r$ con $r$ impar. Si $r \neq 1$ entonces definamos $S = \{1, r + 1, 2r + 1, \dots, 2^k \cdot r + 1\}$, y veamos que el promedio de dos elementos del conjunto, si es un entero, está también en el conjunto. Ya que $r \neq 0$, este conjunto no es $[n + 2]$, y entonces la condición deseada no se cumple. Luego, $n = 2^k - 1$ para algún $k$.
Ahora mostraremos por inducción que si $m$ es entero positivo y $k$ no negativo, $S$ es un conjunto equilibrado, $m \in S$ y $m + 2^k \in S$, entonces $\{m, m + 1, \dots, m + 2^k\} \subset S$. Esto es obvio para $k = 0$. Ahora, si $c \in S$ y $2^k + c \in S$, entonces $2^{k-1} + c \in S$ pues $S$ es equilibrado. Aplicando la hipótesis para $k - 1$ y $m = c$, tenemos que $\{c, c + 1, c + 2 \dots c + 2^{k - 1}\} \subset S$. Ahora usando esta misma hipótesis para $m = c + 2^{k - 1}$ tenemos $\{2^{k - 1} + c, 2^{k -1} + c + 1, \dots, 2^k + c\} \subset S$, lo cual concluye la demostración.
Finalmente aplicar el resultado anterior con $m = 1$ implica que todo $n$ de la forma $2^k - 1$ cumple.
La linea que no cabe es
$$1 = (A(n + 2) - A(n + 1)) - (A(n + 1) - A(n))$$
$$= C(n + 2) - C(n + 1)$$
Vamos a buscar a qué es igual A(n) primero. Tenemos 4 tipos de conjuntos equilibrados, cuya suma da A(n), por definición:
en los que n y 1 están dentro del subconjunto
en los que n está adentro pero 1 no
en los que 1 está adentro pero n no
en los que ni 1 ni n están adentro
A(n-1)= el número de subconjuntos que abarcan los números de 1 a n. Entonces, A(n-1) es igual al número de subconjuntos de {1,2,…,n} en los cuales el n no está. Además, si a cada uno de los números de esos subconjuntos le sumamos 1, el subconjunto seguirá siendo equilibrado, pero ahora tenemos puros subconjuntos de {1,…,n} que no contienen al 1 (porque cada elemento después de sumarle 1, nos da mayor a 1). De la misma manera podemos hacer una biyección entre los subconjuntos eq. que no contienen ni al 1 ni a n, y los subconjuntos eq. de {1, …, n-2}. Por lo tanto, por inclusión exclusión tenemos que
(#subconjuntos de [n] que no tienen al 1)+(#subconjuntos de [n] que no tienen al n)-(#subconjuntos de [n] que no tienen al 1 ni al n)= (#subconjuntos que no contienen al 1 o al n)= (#subconjuntos en b),c), y d) )
Pero (#subconjuntos de [n] que no tienen al 1)=A(n-1),
(#subconjuntos de [n] que no tienen al n)= A(n-1)
(#subconjuntos de [n] que no tienen al 1 ni al n)= A(n-2)
=> (#subconjuntos en b),c), y d) )= 2A(n-1)-A(n-2)
Digamos que en a) hay f(n) números. Veamos por lo tanto esto:
A(n)= suma de a), b), c), y d)=f(n)+(#subconjuntos en b),c), y d) )= f(n)+2A(n-1)-A(n-2)
=> A(n)+A(n-2)-2A(n-1)=f(n)
=>los n que cumplan van a ser los n’s tal que f(n)=1, como nos lo dice el enunciado.
Ahora veamos la siguiente inducción:
“La única n que cumple que f(n)=1 y que está en el intervalo {2^k, 2^k+1, …, 2^(k+1)-1} es 2^k+1”, para k mayor o igual que 2
B.I. para k=2, tenemos que nuestro intervalo de interés es {4, 5, 6, 7}
-f(4)>1 porque tenemos amenos 2 subconjuntos eq. de {1,…4} que usan 1 y 4: {1,4} y {1,2,3,4}
-f(5)=1 (si 1 y 5 están en el conjunto, como su promedio (3) es entero, entonces 3 también está en el s. pero eso también hace que 2 y 4 tengan que estar en el subconjunto, entonces solo hay uno que sirve: {1,2,3,4,5}
-f(6)>1porque tenemos amenos 2 subconjuntos eq. de {1,…6} que usan 1 y 6: {1,6} y {1,2,3,4,5,6}
-f(7)>1 porque tenemos amenos 2 subconjuntos eq. de {1,…7} que usan 1 y 7: {1,4,7} y {1,2,3,4,5,6,7}
entonces el único número que nos sirve ahí es el 5, o 2^2+1
H.I. tenemos que el único k en {2^k,…,2^(k+1)-1} tal que f(k)=1 es 2^k+1
D.I. Veamos cuántos números del conjunto {2^(k+1),…,2^(k+2)-1} cumplen que f(x)=1
Si x es par, tenemos una contradicción, ya que tenemos dos conjuntos al menos contados dentro de f(x): {1,x} y {1,…,x}. Entonces x es impar, y como 1 y x están en el subconjunto, y su promedio es entero, también (x+1)/2 está. Entonces analizamos dos partes no ajenas de nuestro subconjunto: {1,…,(x+1)/2} y {(x+1)/2,…,x}. Tenemos que en cada conjunto hay (x+1)/2 números, y como 2^(k+1)=1), tenemos
2^k=<(x+1)/2=<2^(k+1)-1.
Ahora veamos que si f(x) no es 1, entonces hay dos subconjuntos N y M de {1,…,x} que contienen 1 y x, pero veamos que formando dos subconjuntos P y Q de {(x+1)/2,…,x} así:
a está en N si y sólo si (x+1-a) está en P
a está en M si y sólo si (x+1-a) está en Q
y uniendo N y P, y M y Q, respectivamente, vamos a obtener dos conjuntos equilibrados distintos (tenemos que no hay problemas ya que el promedio (si fuera entero) de cualesquiera a y b de alguno de los dos subconjuntos sí estaría ahí, por simetría)
por lo tanto, para que f(x) pueda ser 1, se necesita que f((x+1)/2)=1, entonces
(x+1)/2= 2^(k+1)+1, por H.I.
=> x+1=2^(k+2)+2
=> x=2^(k+2)+1
Terminamos la inducción, y es fácil ver que entre 1,2,y 3 el único n que cumple es el 3. Por lo tanto, los números de la forma 2^k+1 con k mayor o igual a 1 son los que buscábamos.
Ah ahi lei mal el problema creo... encontré los n's tal que A(n)-2A(n-1)+A(n-2)=1
Publicar un comentario