Olimpiada Matemática Española 2011 – Problema 6: Sucesión por recurrencia - Gaussianos

Olimpiada Matemática Española 2011 – Problema 6: Sucesión por recurrencia

Con este problema llegamos al final de la serie de problemas planteados en la XLVII Edición de la Olimpiada Matemática Española. El sexto (tercero de la segunda sesión) dice lo siguiente:

Sea $(S_n)$ , con $n \ge 0$ , la sucesión definida por:

$S_n=1$ para $0 \le n \le 2011$ ;

$S_{n+2012}=S_{n+2011}+S_n$ , para $n \ge 0$ .

Prueba que para todo entero no negativo a se cumple que $S_{2011a}-S_a$ es múltiplo de 2011.

A ver qué tal sale este último.

3 comentarios

Angel "Java" Lopez | 3 de May de 2011 | 20:53

Hmmm… hay que considerar que CADA n de 0<=n<=2011 es la semilla de una serie distinta.

Hay que demostrar que cada una de esas series, tiene la propiedad buscada.
pcrdeg | 5 de May de 2011 | 22:21

Hago una demostración no muy detallada pero que puede completase con facilidad.
Sea, para un número primo p, la sucesión S(n)tal que
S(n)=1 si n están entre 0 y p y tal que S(n+1)=S(n)+S(n-p) si n>=p.
Denotando por C(m,n) al número combinatorio m!/((n!•(m-n)!) se demuestra por inducción sobre k que S(n+k)=C(k,0)•S(n)+C(k,1)•S(n-k)+C(k,2)•S(n-2k)+…+C(k,k)•S(n-k•k)
Por tanto, S(a•p)= C(p,0)•S(ap-p)+C(p,1)•S(ap-2p)+C(p,2)•S(ap-3p)+…+C(p,p)•S(ap-(p+1)•p))
Supongamos ahora, por hipótesis de inducción, que si b<a, S(bp)-S(b) es divisible por p.
Entonces S(ap)-S(a)=
1•S(ap-p)+[ C(p,1)•S(ap-2p)+C(p,2)•S(ap-3p)+..C(p,p-1)S(ap-p•p)]+ 1•S(ap-(p+1)•p))-S(a)=
=(S(ap-p)-S(a-1))+[…]+(S(ap-p•p-p)-S(a-p-1))+(S(a-1)+S(a-p-1)-S(a))
El primer y el tercer sumando son divisibles por p por hipótesis de inducción; el sumando entre corchetes es múltiplo de p porque si 0<k<p, C(p,k) es un número primo; el último paréntesis es exactamente 0 por la definición de la sucesión.
En definitiva, S(ap)-S(a) es múltiplo de p. Como p=2011 es un número primo, el problema queda resuelto.
Daniel | 25 de May de 2011 | 09:32

Creo que hay un problema con la solución de pcrdeg, ya que la relación que pretende demostrar por inducción, para $k=1$ , es $S(n+1)=S(n)+S(n-1)$ , que no es cierta. Tal vez no haya entendido bien lo que quiere decir…

En cualquier caso, mi solución es la siguiente: supongamos que un saltamontes puede dar “pasos” de longitud $1$ , y “saltos” de longitud $k$ , siendo $k$ un entero positivo cualquiera. Sea $x_n$ el número de formas en que puede llegar desde $0$ hasta $n$ , avanzando siempre hacia la derecha y combinando pasos y saltos. Claramente, si $n<k$ , tenemos $x_n=1$ , ya que no puede dar ningún salto, y sólo puede avanzar a pasos. Para $n\geq k$ , puede comenzar dando un salto, con lo que le quedaría por recorrer una distancia $n-k$ de $x_{n-k}$ maneras posibles, o dando un paso, con lo que le quedaría por recorrer una distancia $n-1$ de $x_{n-1}$ formas posibles. Tenemos entonces que $x_n=S_n$ para $k=2012$ . Sea ahora $C$ el cociente entero de dividir $n$ entre $k$ . Tenemos entonces que el saltamontes puede dar $c$ saltos y $n-ck$ pasos, para un total de $n-c(k-1)$ avances, que se pueden distribuir de $\binom{n-c(k-1)}{c}$ formas distintas, y esto es así para cada $c\in\{0,1,2,\dots,C\}$ , es decir, tomando $k-1=p$ , y siendo $C$ el cociente entero de dividir $n$ entre $p+1$ , se tiene

$S(n)=\sum_{c=0}^C\binom{n-cp}{c}.$

Una vez establecido esto, nos basta con demostrar que, si $p$ es primo, entonces $S(pn)-S(n)$ es múltiplo de $p$ . Esto es una cuestión puramente técnica, lo postearé más adelante si me animo, a menos que alguien quiera adelantárseme.