Sea $S_{n}$ el conjunto de los primeros $n$ enteros positivos. Determina todas las secuencias
\[a_{1}, a_{2}, \ldots, a_{n^{2}+n}\]
tales que $a_{i}\in \left\{0, 1\right\}$ para todo $i\in S_{n^{2}+n}$, y
\[a_{i+1}+a_{i+2}+\cdots+a_{i+n}<a_{i+n+1}+a_{i+n+2}+\cdots+a_{i+2n}\]
para todo $0\leq i\leq n^{2}-n$.
lunes, 10 de junio de 2013
Suscribirse a:
Comentarios de la entrada (Atom)
4 comentarios:
Ajá, según yo es $a_i=f\left(i-1-\left(\lceil \frac{i}{n} \rceil\right)(n-1)\right)$, donde definimos $f(x)=0$ si $x \le 0$, y $f(x)=1$ si $x \textgreater 0$.
Primeramente, vemos que si $S_k=a_{n(k-1)+1}+...+a_{nk}$ entonces es fácil ver que $S_k=k-1$, pues $0 \le S_1 \textless ... \textless S_{n+1} \le n$. Luego, obtenemos que $a_1=...=a_n=0$ y $a_{n^2+1}=...=a_{n^2+n}=1$, ¿no? Ajá.
Luego hacemos una inducción, ¿no? Ajá, demostraré que $a_{nk+1}=0$ si $k \le n-1$ es natural. Para $k=1$, asumimos que $a_{n+1}=1$ y llegamos a una contradicción con $S_2=1 \Rightarrow a_{n+2}=...=a_{2n}=0$ y $1=a_{n+1}=a_2+...+a_{n+1} $$ \textless a_{n+2}+...+a_{2n+1} = a_{2n+1} $$ \le 1$.
Para el paso inductivo suponemos que $a_{n(k-1)+1}=0$ y $a_{nk+1}=1$ para llegar a una contradicción. Entonces $S_{k+1}=k \Rightarrow a_{nk+2} + ... + a_{n(k+1)} = k-1$ y similarmente $a_{n(k-1)+2}+...+a_{nk} = k-1$. Entonces $k=a_{n(k-1)+2}+...+a_{nk}+a_{nk+1} \textless $$ a_{nk+2} + ... + a_{n(k+1)}+a_{n(k+1)+1} \le k$. Contradicción. Ajá. Así, se completa la inducción y $a_{nk+1}=0$ si $k \le n-1$. Ajá.
Luego con $S_n=n-1$ observamos que $a_{n(n-1}+2}=...=a_{n^2}=1$. Básicamente, ahora hacemos la inducción "de vuelta" para mostrar que $a_{nk}=1$, usamos $S_2$, hacemos ping-pong con la inducción, donde las raquetas son $S_k=k-1$, y llegamos a la conclusión que puse arriba.
Por ejemplo para $4$ es $00000001001101111111$
Formalmente, tendrías que hacer dos inducciones de inducciones entrelazadas, una par la ida y una para la vuelta. Pero la verdad, que flojera.
y para 5 es $00000$, $00001$, $00011$, $00111$, $01111$, $11111$. La dividí en bloques para que se entienda mejor.
Publicar un comentario