Maths Olympiad Prep

Library / /34 of 144

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

Let mm be a fixed integer greater than 11. The sequence x0x_0, x1x_1, x2x_2, \ldots is defined as follows:
xi={2iif 0im1;j=1mxijif im.x_i = \begin{cases}2^i&\text{if }0\leq i \leq m - 1;\\\sum_{j=1}^mx_{i-j}&\text{if }i\geq m.\end{cases}
Find the greatest kk for which the sequence contains kk consecutive terms divisible by mm .

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

We need to determine the greatest k k such that the sequence defined by:

xi={2iif 0im1,j=1mxijif im, x_i = \begin{cases} 2^i & \text{if } 0 \leq i \leq m - 1, \\ \sum_{j=1}^m x_{i-j} & \text{if } i \geq m, \end{cases}

contains k k consecutive terms divisible by m m .

Firstly, we observe the initial terms of the sequence x0,x1,,xm1 x_0, x_1, \ldots, x_{m-1} . These are:
x0=20=1,x1=21=2,,xm1=2m1. x_0 = 2^0 = 1, \quad x_1 = 2^1 = 2, \quad \ldots, \quad x_{m-1} = 2^{m-1}.

Next, we analyze terms where im i \geq m . For such i i , the value of xi x_i is:
xi=j=1mxij. x_i = \sum_{j=1}^m x_{i-j}.

The first few terms xi x_i for im i \geq m will therefore depend linearly on the initial terms as follows:
- xm=xm1+xm2++x0 x_m = x_{m-1} + x_{m-2} + \cdots + x_0 .
- Continuing in the same pattern, each xi x_i for im i \geq m is a sum of m m prior terms.

To investigate divisibility by m m , consider the sequence from elements x0 x_0 to xm1 x_{m-1} . In particular, initial terms like x1=2,x2=4, x_1 = 2, x_2 = 4, etc., imply none of the x0,x1,,xm1 x_0, x_1, \ldots, x_{m-1} are divisible by m m because all are powers of 2 less than 2m 2^m and m m is odd.

As we proceed with computing xm,xm+1, x_m, x_{m+1}, \ldots , each term is a combination of earlier terms:
- Note that 2m1(modm) 2^m \equiv 1 \pmod{m} by Fermat's Little Theorem (since m m is an odd integer greater than 1 and 2 2 is not divisible by m m ).
- Therefore, the sums of powers of 2, modulo m m , repeat patterns that emerge from the initial terms.

As xi x_i for im i \geq m only sums up over terms bounded within a consistent modulus pattern, the maximal contiguous streak of terms divisible by m m can only reach a certain finite length.

Since no set of the base terms x0,x1,,xm1 x_0, x_1, \ldots, x_{m-1} are divisible by m m individually, the calculation indicates a maximal streak of k=m1 k = m - 1 contiguous terms with any division pattern under m m .

Thus, the largest k k for which the sequence contains k k consecutive terms divisible by m m is:
m1. \boxed{m-1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.