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:

  1. S_n=1 para 0 \le n \le 2011;
  2. 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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

3 Comentarios

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

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *