RSS Feed
Precedenta
Următoarea

Problema 319

08 Ianuarie 2011

Șiruri mărginite


Fie x1, x2,..., xn un șir de lungime n astfel încât:

  • x1 = 2
  • pentru toate valorile 1 < in : xi-1 < xi
  • pentru toate valorile lui i și j unde 1 ≤ i, jn : (xi) j < (xj + 1)i

Sunt doar 5 astfel de șiruri de lungime 2, mai exact: {2,4}, {2,5}, {2,6}, {2,7} și {2,8}.
Sunt 293 astfel de șiruri de lungime 5; trei exemple sunt date mai jos:
{2,5,11,25,55}, {2,6,14,36,88}, {2,8,22,64,181}.

Fie t(n) numărul de astfel de șiruri de lungime n.
Îți este dat t(10) = 86195 și t(20) = 5227991891.

Află t(1010) și introdu ca răspuns restul împărțirii acestui număr la 109.


>> Vezi problema originală <<