IMO ShortList 2003, number theory problem 1

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMO ShortList 2003, number theory problem 1

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 2003, number theory problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Oct 4, 2004, 9:29 PM • 10 Y

Y by Davi-8191, ValidName, Adventure10, TFIRSTMGMEDALIST, megarnie, HWenslawski, Perceval, megahertz13, vsamc, Mango247

Let $m$ be a fixed integer greater than $1$ . The sequence $x_0$ , $x_1$ , $x_2$ , $\ldots$ is defined as follows:
$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 $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ .

Proposed by Marcin Kuczma, Poland

Attachments:

This post has been edited 1 time. Last edited by djmathman, May 27, 2018, 3:50 PM
Reason: changed display according to https://anhngq.files.wordpress.com/2010/07/imo-2003-shortlist.pdf

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#2 h Oct 4, 2004, 10:10 PM • 2 Y

Y by Adventure10, Mango247

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#3 h Oct 6, 2004, 7:07 AM • 2 Y

Y by Adventure10, Mango247

I know it has been discussed beofre, but what's the question?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#4 h Oct 6, 2004, 7:32 AM • 2 Y

Y by Adventure10, Mango247

http://www.mathlinks.ro/Forum/viewtopic.php?t=5643

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#5 h Oct 6, 2004, 7:34 AM • 2 Y

Y by Adventure10, Mango247

When I click that it tells me something like "we're moving to a better forum.." or "URL not found..". Does this happen to anyone else?

This post has been edited 1 time. Last edited by grobber, Oct 8, 2004, 1:11 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#6 h Oct 6, 2004, 8:01 AM • 2 Y

Y by Adventure10, Mango247

Not to me...

Here is the address:

Mathlinks Forum Index -> Problem Solving -> MathLinks Olympiad Forum -> Advanced Section -> Number Theory -> Number Theory Proposed & Own Problems -> Sequence

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

308 posts

#7 h Oct 6, 2004, 9:43 AM • 2 Y

Y by Adventure10, Mango247

...question is:

Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

543 posts

#8 h Aug 6, 2014, 7:26 PM • 10 Y

Y by AmirAlison, huricane, Nelu2003, Myriam2003, mira74, yayitsme, centslordm, Jalil_Huseynov, CahitArf, Adventure10

I claim that the answer is $k = m - 1$ .

Lemma 1: $k \geq m$ is impossible

Proof: Consider the sequence modulo $m$ . Assume the contrary, so that there is a string of $m$ consecutive $0$ 's somewhere in the sequence. Using the recursive formula, we find that the element of the sequence immediately before the string of $0$ 's is also a $0$ . Continuing in this fashion, we have that every element of this sequence is eqivalent to $0 \pmod m$ , contradiction.

Lemma 2: $k = m - 1$ is obtainable.

Proof: Again consider the sequence modulo $m$ . Extend the sequence so that now the sequence is $\dots x_{-3}, x_{-2}, x_{-1}, x_0, x_1, x_2, \dots$ so that the recursive formula holds for all $i \in \mathbb{Z}$ . Since $2^{m - 1} - \sum_{n = 0}^{m - 2}2^n = 1$ we have that $x_{-1} = 1$ . It is then easy to see that $x_{-2} = x_{-3} = \dots = x_{-m} = 0$ . Since the sequence is infinite and since there are only $m ^ m$ sequences of length $m$ whose elements are in $\mathbb{Z}_m$ , we have because the sequence is defined recursively that the sequence taken modulo $m$ is totally periodic (by the Pidgeonhole Principle). Therefore we can find a string of $m - 1$ $0$ 's in the sequence where the subscripts of the $x$ 's are all positive, as desired.

Therefore the claim is proven.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

Sx763_

#9 h Sep 24, 2015, 5:04 PM • 2 Y

Y by centslordm, Adventure10

Is it true?
Xm+i = 2^i * (2^m-1) that is easy by induction
and for m=2^a, a>=1, and i>a we get that Xm+i is divisible by m
conclusion, we have infiniely k

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1446 posts

#10 h Jun 23, 2021, 2:19 PM • 2 Y

Y by centslordm, Mango247

We claim that the answer is $k=\boxed{m-1}$ . First, we will prove that there cannot be $m$ consecutive multiples of $m$ . Suppose there was, and the earliest copy of $m$ consecutive elements divisible by $m$ was from $x_{i+1}$ to $x_{i+m}$ , with $i$ being a nonnegative integer. Then notice that $x_i=x_{i+m}-x_{i+m-1}-\ldots-x_{i+1}$ , which must be a multiple of $m$ , so $x_i$ to $x_{i+m-1}$ is a set of $m$ consecutive elements divisible by $m$ , a contradiction as we said $x_{i+1}$ to $x_{i+m}$ was the first such set.

Now we prove that for all $m$ , there exists $m-1$ consecutive elements divisible by $m$ . Extend the definition of $x_n$ to negative numbers using the recursion $x_i=x_{i+m}-x_{i+m-1}-\ldots-x_{i+1}$ , which is already true for all nonnegative integers $i$ , by extending this definition to all negative integers $i$ as well. Using this, we get $x_{-1}=1$ and $x_{-2}=x_{-3}=\ldots=x_{-m}=0$ . Now let $y_i$ be the remainder of $x_i$ when divided by $m$ , and consider the ordered $m$ -tuple $(y_{i+1}, y_{i+2}, \ldots, y_{i+m})$ for all nonnegative integers $i$ .

Because there are only $m^m$ possible ordered $m$ -tuples, there are infinitely many duplicates by the Pigeonhole principle. Suppose that two nonnegative integers $i$ and $j$ with $j-i\ge m$ are such duplicates, thus $y_{i+k}=y_{j+k}$ for all $1\le k\le m$ . Then, using the recursion both forwards and backwards, we get $y_{i+k}=y_{j+k}$ for all integers $k$ . Using $k=-i-p$ for $2\le p\le k$ , we get $y_{-p}=y_{j-i-p}$ . However, because $y_{-p}=0$ , we get that $y_{j-i-p}=0$ for all $2\le p\le m$ . Since $j-i>m, j-i-p$ must be positive for all $2\le p\le m$ , so $y_n$ is $0$ for $m-1$ consecutive positive integer elements, and these elements correspond with $m-1$ consecutive elements that are multiples of $m$ , and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1721 posts

oVlad

#11 h Oct 22, 2021, 6:55 AM

Y by

We claim that $k=m-1.$

If there are at least $m$ consecutive terms of the sequence divisible by $m$ , say, $x_{i+1},x_{i+2},...,x_{i+m}$ then $x_{i+m}=x_{i+m-1}+...+x_{i+1}+x_i$ implies that $m$ divides $x_i$ as well. Continuing this process, we get that $m$ must divide $x_0=1$ which is a contradiction.

Now to prove that $m-1$ works, observe that $x_{i+m},x_{i+m-1},...,x_{i+1}$ only depend on $x_i, x_{i-1},...,x_{i-m+1},$ i.e. the previous $m$ terms, and thus, by looking at blocks of $m$ elements, since there are finitely many possibilities for them (the terms are reduced modulo $m$ ) we can deduce that eventually we will get $(2^0,2^1,...,2^{m-1})_m$ again so the previous $m$ terms will be $(1,0,0...,0)_m$ so there are $m-1$ terms divisible by $m.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5542 posts

#12 h Feb 6, 2022, 3:47 PM

Y by

Ans is $\boxed{m-1}$ .

Consider sequence $\pmod m$ .

First we will show that $k=m$ is impossible (also proves it for $k>m$ ).

Suppose there were $m$ consecutive zeros. Let $i$ be the last of these $m$ values so that $x_i=0$ . Then $x_{i-m}$ , which is the term before these zeros is also $0$ . Repeating this process gives every element is $0\pmod m$ , a contradiction.

Now we will show that $k=m-1$ always holds. Extend the sequence so that the same formula holds for all $i\in \mathbb{Z}$ and indices can also be negative. So $2^{m-1}=x_{m-1}=2^{m-1}-1+x_{-1}\implies x_{-1}=1$
Thus, $x_{-2}=x_{-3}=\ldots=x_{-m}=0$ . Consider in $\pmod m$ , the ordered $m$ -tuples $(x_i, x_{i+1}, \ldots,x_{i+m})$ . Since there are only $m^m$ distinct such tuples, there must be infinitely many duplicates.

Now if we have a tuple $(x_i, x_{i+1}, \ldots, x_{i+m})$ , we can find $x_{i-1}$ and go all the way back to the tuple $(x_{-m},\ldots, x_{-1})\equiv (0,0,0,\ldots,0,0,1)$ .

Now with the duplicate, we can go back the same amount and find another $m$ -tuple that is $(0,0,0\ldots,0,0,1)$ , but this time the indices are positive.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1677 posts

awesomeming327.

#13 h Mar 8, 2022, 11:49 PM

Y by

Consecutive terms in fibonacci sequences starting with powers of two.

Define a sequence $y_0,y_1,y_2,\dots$ that is equivalent to the sequence $x_0,x_1,x_2,\dots$ modulo $m.$ Note that by pigeonhole principle there must exist a term $y_k$ with $k>0$ such that $\left(y_0,y_1,y_2,y_3,\dots,y_{m-1}\right)=\left(y_k,y_{k+1},\dots,y_{k+m-1}\right)$ Now, we see that $\left(y_k,y_{k+1},\dots,y_{k+m-1}\right)=\left(1,2,4,\dots,2^{m-1}\right)$ so $y_{k-1}=1,$ $y_{k-2}=0$ and $y_{k-i}=0$ for $i=2,\dots,m$ since $0+0+0+\dots+1+1+2+\dots+2^i=2^{i+1}.$ This makes a sequence of $m-1$ consecutive terms divisible by $m$ and we cannot get $m$ consecutive terms divisible by $m$ because then the cycle in $y_k$ would just always be $0,$ which would necessarily imply that $y_0=0$ which is clearly false as $y_0=1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1878 posts

#14 h Apr 13, 2022, 7:34 PM

Y by

My Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

107 posts

#15 h Jul 2, 2022, 4:51 PM

Y by

The answer is $m-1$ .
Claim: It is impossible for $m$ consecutive terms in this sequence to be all divisible by $m$ .
Proof. Assume not, and say that the first time $m$ consecutive terms in this sequence are all divisible by $m$ are indices $x_{i-m}, x_{i-m+1}, \ldots, x_{i-1}$ . It is clear that $i-m \geq 1$ , and so $x_{i-m-1} = x_{i-1} - \sum\limits_{j = 1}^{m} x_{i-1-j}$ is also divisible by $m$ . However, this means that $x_{i-m-1}, x_{i-m}, \ldots, x_{i-2}$ are all divisible by $m$ , contradiction. $\blacksquare$
Now, we show the significantly harder step: that there exists some $m-1$ consecutive numbers in the sequence all divisible by $m$ .
Claim: There exists some $l$ such that $x_{l+i} \equiv x_{i} \pmod{m}$ (i.e., the sequence is periodic $\pmod{m}$ .)
Proof. We first show that the sequence is eventually periodic. There only exist finitely many possible strings of integers from $1$ to $m$ of length $m$ , so there exist some distinct positive integers $a$ and $b$ such that $x_{a-i} \equiv x_{b-i} \pmod{m} [i \in \mathbb{Z}; \; 1 \leq i \leq m]$ However, by the recursion, this also implies $x_a \equiv x_b \pmod{m}$ , $x_{a+1} \equiv x_{b+1} \pmod{m}$ , etc. However, wlogging $a < b$ , we can also take this recursion back to show that $x_0 \equiv x_{b-a} \pmod{p}$ , and in general that $x_k \equiv x_{b-a+k} \pmod{p}$ , which proves the claim by setting $l = b-a$ . $\blacksquare$

Claim: [Magic] If $l$ is the length of the period, then $x_{kl-m}, x_{kl-m+1}, \ldots, x_{kl-2}$ are all divisble by $m$ for any positive integer $k$ . (This claim clearly finishes).
Proof. Assume $kl \geq m$ . It is clear to see that
$x_{kl} \equiv 1 \pmod{m}, x_{kl+1} \equiv 2 \pmod{m}, \ldots, x_{kl+m-1} \equiv 2^{m-1} \pmod{m}$ Working backwards gives us $x_{kl - 1} \equiv 2^{m-1} - \sum\limits_{i=0}^{m-2} 2^i \equiv 1 \pmod{m}$ , $x_{kl-2} \equiv 2^{m-2} - \sum\limits_{i=0}^{m-3} - 1 \equiv 0 \pmod{m}$ , and so on. In general, for integer $2 \leq j \leq m$ , $x_{kl - j} \equiv 2^{m-j} - \sum\limits_{i=0}^{m-j-1} - 1 \equiv 0 \pmod{m}$ using the given recursion. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

966 posts

lrjr24

#16 h Jul 21, 2022, 8:27 PM

Y by

We claim the answer is $m-1$ .
If $k \ge m$ , consider the first block of $m$ terms, $x_{i+1},x_{i+2},\dots x_{i+m}$ that are all divisible by $m$ . This block obviously can't contain $x_1$ so $i \ge 1$ . We thus have that by definition $x_i$ is divisible by $m$ contradicting the fact that it's the first block of $m$ terms.

We now prove that $k=m-1$ is achievable. Extend $\{x_i\}$ to the negatives so that the recursive definition still holds. We get that $x_{-1}=1$ and $x_{-i}=0$ for all $2 \le i \le n$ . If we prove that $\{x_i\}$ is periodic $\pmod{m}$ we will be done. Let $y_i := x_i \pmod{m}$ . Consider the $m^m$ $m$ -tuples where all the numbers are nonnegative and less than $m$ . By PhP, we have that there is a $m$ -tuple that appears more than once. However we can note that the sequence $y_i$ is fully determined by this $m$ -tuple, so the sequence will be the same from these $m$ -tuples just shifted, which implies the sequence is periodic and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4175 posts

#17 h Aug 3, 2022, 3:37 AM

Y by

The answer is $m-1$ .

Suppose for the sake of contradiction that $a$ is the minimum possible such that $x_a$ through $x_{a+m-1}$ are all multiples of $m$ . Since $x_0$ is not a multiple of $m$ , we have that $a\geq1$ . Therefore, by the recursive rule, $x_{a-1}$ is also a multiple of $m$ , contradicting minimality.

Extend the sequence back $m-1$ terms, and they are all zeroes. There are only finitely many sequences of $m$ residues modulo $m$ , so this sequence repeats and therefore contains $m-1$ consecutive zeroes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DakuMangalSingh

72 posts

DakuMangalSingh

#18 h Aug 4, 2022, 3:36 PM

Y by

ISL Marabot Solve
Claim : $k < m$

Proof : FTSOC, $k\geq m$ . Now we consider the sequence mod $m$ . So, the sequence contains at least $m$ consecutive $0$ . In any such $m$ tuple with all $0$ , let $x_y$ be the first number which is $0$ mod $m$ . So, $x_{y-1}\neq 0$ and $x_{y+1},\dots x_{y+m-1}=0$ mod $m$ . But now, $x_{y+m-1}=x_{y+m-2}+\dots+ x_y+ x_{y-1}$ mod $m$ , which gives $x_{y-1}=0$ mod $m$ . Contradiction.

Claim : $k=n-1$

Proof : If we generalize the sequence to its negative terms, then the sequence becomes $x_i = \begin{cases}2^i&\text{if }0\leq i \leq m - 1;\\\sum_{j=1}^mx_{i-j}\end{cases}$ .
By using $x_{m-1}=2^{m-1}$ , we get $x_{-1}= x_{m-1}-(x_{m-2}+\dots x_0)=2^{m-1}-(2^{m-1}-1)=1$ and similarly using $x_{-1}=1$ and $x_{m-2}=2^{m-2}$ , we get $x_{-2}=0$ . So, by induction, $x_{-i}=0$ for $2\leq i \leq m$ . Again, we view the sequence mod $m$ . Since it is an infinite recursive sequence, so by Pigeonhole principle, among any $m^m+1$ numbers of $m$ tuples, two are similar mod $m$ . We can easily go backward and forward from two similar $m$ tuple to other two similar $m$ tuples (because the recursive sequence is formed by any $m$ tuples). Since we have a $m$ tuple with $m-1$ 's consecutive $0$ and $1$ 's $1$ , we can go forward to another such a tuple mod $m$ . Thus, $k=m-1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3787 posts

vsamc

#19 h Jul 19, 2023, 7:47 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#20 h Jul 26, 2023, 3:47 PM • 1 Y

Y by GeoKing

The answer is $k = m - 1.$ Take the entire sequence mod $m$ to get the sequence $y_n.$ We will first note the following:

Claim: There exists an integer $M$ such that for all $n \ge M,$ we have $y_{n} = y_{n + z},$ where $z$ is some positive integer.
Proof: There are only a finite number of pairs $(y_n, y_{n+1}, \dots, y_{n+m-1}),$ so by Pigeonhole, at least two of these pairs are the same. This corresponds to the sequence being periodic at some point.

We then know that $y_M = y_{M+z}, y_{M+1} = y_{M+z+1},$ and so on, up until $y_{M+m} = y_{M+m+z}.$ Using the recursive definition for $y_n,$ we end up getting $y_{M-1} = y_{M-1+z},$ so the claim holds for all $n \ge M - 1.$ In fact, we can continue this process to get that $M = 0,$ so the sequence is periodic in such a way that after one period, we go back to $x_0 = 1.$

Now extend the sequence backwards to indices $y_{-l} = y_{z-l}$ for $1 \le l \le m,$ where the $y_i$ still follow the recurrence. Clearly $y_{-1} = 1,$ and it can be shown using induction that $y_{-l} = 0$ for all $2 \le l \le m.$ This corresponds to $y_{z-2} = y_{z-3} = \dots = y_{z-m} = 0,$ giving $m - 1$ consecutive values of $y_n$ equal to $0.$ Thus $k \ge m - 1.$

Clearly if $k \ge m,$ then all of the $y_i$ must be $0$ at some point. Because of our period property, that means that all the $y_i$ are $0,$ contradicting $y_0 = 1.$

Therefore, we must have $\boxed{k = m - 1},$ as claimed at the beginning.

This post has been edited 1 time. Last edited by EpicBird08, Aug 1, 2023, 1:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

418 posts

Sagnik123Biswas

#21 h Feb 20, 2024, 9:40 PM

Y by

We first claim that there cannot be $m$ consecutive terms that are all divisible by $m$ (a direct consequence of this is that there cannot be more than $m+1$ consecutive terms that are all divisible by $m$ .

Suppose for the sake of contradiction that there are $m$ consecutive terms with $x_a, x_{a+1}, x_{a+2} \dots x_{a+m-1}$ such that $a > 0$ and $x_{a} \equiv 0 \pmod{m}, x_{a+1} \equiv 0 \pmod{m} \dots x_{a+m-1} \equiv 0 \pmod{m}$ . Then note that $(x_{a-1} + x_{a} + x_{a+1} + \dots x_{a+m-2} \equiv x_{a+m-1}) \pmod{m}$ . Thus $x_{a-1} + 0 + 0 \dots + 0 \equiv 0 \pmod{m}$ . So it means that $x_{a-1} \equiv 0 \pmod{m}$ . With similar reasoning, it follows that $x_{a-2} \equiv 0 \pmod{m}, x_{a-3} \equiv 0 \pmod{m}, x_{a-4} \equiv 0 \pmod{m} \dots x_{0} \equiv 0 \pmod{m}$ . But we know that $x_0 \equiv 1 \pmod{m}$ . It cannot possibly be true that $x_0 \equiv 0 \pmod{m}$ .

Thus, we know that our answer $k$ must obey $k \leq m-1$ . Now we show that $k = m-1$ is obtainable, and once we have proven this, we have succesfully found our answer due to the upper bound we established. Suppose that we "extend" the sequence backwards. First define a new sequence $g_i = x_i \pmod{m}$ Then we would see that $g_{-1} \equiv 1 \pmod{m}, g_{-2} \equiv 0 \pmod{m}, g_{-3} \equiv 0 \pmod{m}, \dots g_{-m} \equiv 0 \pmod{m}, g_{-(m+1)} \equiv 1 \pmod{m}$ . We just need to show that the terms $g_{-m}, g_{-(m-1)} \dots g_{-2}$ appear consecutively in that order later in the sequence.

Note that due to the Pigeonhole principle, there exist positive integers $t, a, a+1, a+2, a+3 \dots a+m-1$ such that $g_{a} = g_{a+t}, g_{a+1} = g_{a+1+t}, g_{a+2} = g_{a+2+t} \dots g_{a+m-1} = g_{a+m-1+t}$ . So $g_{a+b} = g_{a+t+b}$ where $b$ has the ability to take on negative values. So there is some future index $j$ such that $g_{j}, g_{j+1}, g_{j+2} \dots g_{j+m-1}$ where $g_{j} = g_{0}, g_{j+1} = g_{1}, g_{j+2} = g_{2} \dots$ . The terms that come right before $g_{j}, g_{j+1}, \dots g_{j+m-1}$ mimic $x_{-1}, x_{-2}, x_{-3} \dots$ .

Hence, we have found $m-1$ consecutive terms that are $0 \pmod{m}$ and showed that there cannot be $m$ consecutive terms.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1251 posts

ezpotd

#22 h Oct 4, 2024, 12:15 PM

Y by

I claim that the answer is $m - 1$ . Interpret everything following modulo $m$ .

Proof we cannot get $m$ : Consider the first time we get $m$ zeroes in a row. Then reversing the relation forces the element before to also be zero, contradiction.

Proof we get $m - 1$ : Obviously, the sequence is periodic. Note that if we are given a block of $m$ elements, we can determine all the elements that come before it just by following the recursion, thus when we first see a block of $m$ elements appear twice, we know that going back some number of elements from the first block yields the starting conditions, so going back the same number of elements from the second block also yields the starting conditions, so the starting conditions appear periodically. Now reversing back from the starting conditions, we see that the $m$ elements before them are exactly $1, 0 , 0 \cdots 0$ where the $0$ is repeated $m - 1$ times.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

944 posts

#23 h Oct 5, 2024, 10:48 AM

Y by

$k \le n-1$ is true by contradiction, $k = n-1$ is true by proving periodic by PHP and looking at negative terms.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

98 posts

#24 h Mar 26, 2025, 1:17 PM

Y by

Cute problem!

The maximum is $k=m-1$ .

Optimality: If there are $m$ consecutive terms divisible by $m$ , modulo $m$ work can give the sequence has every term $0\pmod m$ , but thats a contradiction since $m>1$ doesnt divide $x_0=1$ .

Achievability: Define $x_i=0$ for $i\in \{-(m-1),-(n-2),\dots ,-1\}$ . This sequence satisfies the following recurence:
$x_i = \begin{cases}0&\text{if }-m+1\leq i \leq -1\\\ 1&\text{if }i=0\\\sum_{j=1}^mx_{i-j}&\text{if }i\geq 1.\end{cases}$ Now notice that this sequence is eventually periodic modulo $m$ by PHP on the sets of consecutive $m-1$ tuples. But now a "backtracking" argument can give us that it is periodic throughout modulo $m$ , but since the first $m-1$ terms are zero, we get that there are some consecutive $m-1$ terms that are divisible by $m$ , as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a