martes, 18 de agosto de 2015

Problema del día 18 de agosto.

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$.

6 comentarios:

Ariel dijo...
Este comentario ha sido eliminado por el autor.
Ariel dijo...
Este comentario ha sido eliminado por el autor.
Ariel dijo...

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.

Ariel dijo...

La linea que no cabe es
$$1 = (A(n + 2) - A(n + 1)) - (A(n + 1) - A(n))$$
$$= C(n + 2) - C(n + 1)$$

Olga Medrano dijo...

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.

Olga Medrano dijo...

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