Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $$a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$$for all positive integers $k$ and $n.$ For a given positive integer $m,$ find the maximum possible value of $a_{2m}.$ Proposed by Krit Boonsiriseth
Problem
Source: ELMO 2018 #2, 2018 ELMO SL N3
Tags: algebra, Integer sequence
28.06.2018 10:21
28.06.2018 10:33
28.06.2018 10:41
Note that $a_n\mid a_{k+n}-a_k$ since $a_n\mid a_k+\cdots + a_{k+n-1}$ and $a_n\mid a_{k+1}+\cdots + a_{k+n}$; subtracting gives the claim. Write $S_n=a_1+a_2+\cdots + a_n$. Note that $a_{2m}=\boxed{2^m-1}$ is attainable via the sequence $a_{2n}=2^n-1$ and $a_{2n-1}=1$; indeed, we only need to check the divisibility condition for even $n$; note that $a_{2n}\mid a_1+\cdots + a_{2n} = 2^{n+1}-2$, $a_{2n}\mid a_{2k+2n}-a_{2k}=2^{k+n}-2^k$, and $a_{2n}\mid a_{2k+2n-1}-a_{2k-1}=0$; from this, it is easy to see the divisibility condition holds. We prove the following claims simultaneously via induction: $$S_{2m}\le 2^{m+1}-2 \text{ and } a_{2m}\le 2^m-1$$ Indeed, the base case $m=1$ is easy: note that $a_2\mid a_1+a_2=1+a_2$, so we are forced to have $a_2=1$ and $S_2=2$. Now, suppose the statement is true for $m$. First, note that $a_i\mid S_{i-1}$ in general, since $a_i\mid a_1+\cdots + a_i=S_{i-1}+a_i$. Let $S=S_{2m}$. We have $a_{2m+1}\mid S$, $a_{2m+2}\mid S_{m+1}=S+a_{2m+1}$, and $a_{2m+1}\mid a_{2m+2}-a_1=a_{2m+2}-1$. Now, note that $$a_{2m+2}\mid a_{2m+1}\left(\frac{S}{a_{2m+1}}+1\right)\mid (a_{2m+2}-1)\left(\frac{S}{a_{2m+1}}+1\right)$$Thus, $a_{2m+2}\mid \frac{S}{a_{2m+1}}+1$. But this means that $a_{2m+2}-1\le \frac{S}{a_{2m+1}}$, so $a_{2m+1}(a_{2m+2}-1)\le S=S_m$. In particular, since $a_{2m+1}$ and $a_{2m+2}$ are integers, we have $a_{2m+1}+a_{2m+2}-1\le S_m+1\le 2^{m+1}-1$ (since the sum of two integers with a product $P$ is at most $P+1$). Thus, $a_{2m+1}+a_{2m+2}\le 2^{m+1}$. Since $a_{2m+1}\ge 1$, we have $a_{2m+2}\le 2^{m+1}-1$, proving the second part of the inductive step. To prove the first part, just note that $S_{m+1}=S_m+a_{2m+1}+a_{2m+2}\le 2^{m+1}-2+2^{m+1}=2^{m+2}-2$. Thus by the inductive claim, we have $a_{2m}\le 2^m-1$ for all $m$ as desired. $\square$
28.06.2018 10:45
First observe that $\gcd (a_n,a_{n+1})=1$. Then I use induction to prove$$a_{2n} \le 2^n-1$$and $$S_{2n} \le 2^{n+1}-2$$By $\gcd (a_n,a_{n+1})=1$, we have $a_{2n}a_{2n+1} \mid S_{2n}$. Then it's enough to apply AM-GM inequality. lol, seems to be similar as above.
28.06.2018 10:57
whatshisbucket wrote: Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $$a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$$for all positive integers $k$ and $n.$ These sequences seem very interesting. Any extensions?
28.06.2018 11:01
Superguy wrote: So here is my solution. We see that in the sequence $a_n|a_k+a_{k+1}+\cdots +a_{k+n-1}$ And after replacing (k) with (k+1), $a_n|a_{k+1}+a_{k+2}+\cdots +a_{k+n}$ Subtracting both the equations we get, $$a_{n+k}\equiv a_k\pmod{a_n}-(1)$$Which gives us a generalisation for all positive integers k and n. I generate an arbitrary sequence $l_n$ Such that $l_{2i}=2^i-1$ $l_{2i+1}=1$ For all Nonnegative integers i.
Using both our claims we can conclude that $l_n$ is also a type of sequence $a_n$. Using our generalisation we get $gcd(a_{n},a_{n+1})=1$ $\implies lcm(a_n,a_{n+1})=a_n.a_{n+1}|a_1+a_2+a_3\cdots +a_n$ Now if $a_{2m}\geq 2^m$ for some sequence of type $a_n$. We get $a_{2m}.a_{2m-1}\leq a_1+a_2+a_3\cdots +a_{2m-1}$ $\implies 2^m-1\leq 2^m-1(a_{2m-1})\leq a_1+a_2+a_3\cdots +a_{2m-2}$ Now we are in a position to apply strong induction. $\boxed{Claim-(3)}$ For all sequences $a_n$ , $2^m-1>a_1+a_2+a_3+\cdots +a_{2m-2}$ $\boxed{Proof}$ We will induct on m. Base case: $m=2$ $2^2-1=3>a_1+a_2=2$ $m=3$ $2^3-1=7>a_1+a_2+a_3+a_4=6(max)$ Inductive hypothesis Assume for integers $m=(1,2,.....k)$ the statement holds true. $\implies 2^k-1> a_1+a_2+\cdots +a_{2k-2}$ We need to prove for $m=k+1$ Now for $a_{2k-1}\geq 3$ and $a_{2k}\geq 4$ $a_{2k-1}+a_{2k}\leq (a_{2k-1})(a_{2k}-1)\leq a_1+a_2+a_3+a_+\cdots a_{2k-2}<2^k-1$ (Inductive hypothesis) So in this case $a_1+a_2+\cdots a_{2k}<2^k-1+2^k-1=2^{k+1}-2<2^{k+1}-1$ For the other cases, If $\boxed{a_{2k-1}=1}$ $a_{2k}\leq a_1+a_2+\cdots +a_{2k-2}+a. _{2k-1}<2^k-1+1=2^k$ So if $2^k>a_{2k}$ then $2^k\geq a_{2k}+1$ Thus $a_1+a_2+\cdots a_{2k}<2^k-1+2^k-1+1=2^{k+1}-1$ If $\boxed{a_{2k}=1}$ $a_{2k-1}\leq a_1+a_2+\cdots +a_{2k-2}<2^k-1$ Thus again $a_1+a_2+\cdots a_{2k}<2^k-1+2^k-1+1=2^{k+1}-1$ If $\boxed{a_{2k}=2}$ then clearly $a_{2k-1}=1$ So $a_1+a_2+\cdots a_{2k}<2^k-1+3<2^{k+1}-1$ For $k\geq 2$ If $a_{2k-1}=2$ and $a_{2k}=3$, Again $a_1+a_2+\cdots a_{2k}<2^k-1+5<2^{k+1}-1$ For $k\geq 3$ So we have tackled all the cases and our inductive step is complete. $\square$ So as per our last claim we can see that the statement that $a_{2m}\geq 2^m$ for some sequence $a_n$ is false. So $$a_{2m}\leq 2^m-1$$As we can see that in sequence $l_n$ The max value of $a_{2m}$ appears as $2^m-1$. Hence we conclude that maximum possible value of $a_{2m}=2^m-1$.
28.06.2018 13:15
28.06.2018 17:43
For every even integer $n = 2m$ we will prove that $a_{n} \le 2^{m}-1$. To see this is attainable, consider the sequence \[ a_n = \begin{cases} 1 & n \text{ odd} \\ 2^{n/2}-1 & n \text{ even}. \end{cases} \]This can be checked to work, so we prove it's optimal. We have $a_2 \mid a_1+a_2 = 1+a_2 \implies a_2 = 1$. Now consider an integer $n$, and let $s = s_n = a_1 + \dots + a_n$. Then \begin{align*} a_{n+1} &\mid s \\ a_{n+2} &\mid s + a_{n+1} \\ a_{n+2} &\equiv 1 \pmod{a_{n+1}}. \end{align*}Thus, $\gcd(a_{n+2}, a_{n+1}) = 1$. So $a_{n+2} \le \frac{s + a_{n+1}}{a_{n+1}}$, and thus \[ a_{n+1} + a_{n+2} \le 1 + a_{n+1} + \frac{s}{a_{n+2}} \le s+2. \] So, we have \begin{align*} a_1 + a_2 &= 2 \\ a_3 + a_4 &\le 2+2 = 4 \\ a_5 + a_6 &\le (2+4)+2 = 8 \\ a_7 + a_8 &\le (2+4+8)+2 = 16 \\ &\vdots \\ a_{2m-1} + a_{2m} &\le 2^{m}. \end{align*}Thus $a_{2m} \le 2^{m} - a_{2m-1} \le 2^{m}-1$. Remark: [Motivational notes] It's very quick to notice $a_{n+1} \mid a_1 + \dots + a_n$, which already means that given the first $n$ terms of the sequence there are finitely many possibilities for the next one. Thus it's possible to play with ``small cases'' by drawing a large tree. When doing so, one might hope that somehow $a_n = a_1 + \dots + a_{n-1}$ is achievable, but quickly notices in such a tree that if $a_n$ is the sum of all previous terms, then $a_{n+1} = 1$ is forced. This gives the idea to try to look at the terms in pairs, rather than one at a time, and this gives the correct bound. As for extracting the equality case from this argument, there are actually two natural curves to try. We have $a_3 \mid 1+1 = 2$. If we have $a_3 = 2$ we get $a_4 = 1$, $a_5 \le 5$, but then $a_6$ actually gets stuck. But if we have $a_3 = 1$ instead, we get $a_4 = 3$, $a_5 = 1$, $a_6 = 7$, and so on; pushing this gives the equality case above, seen to work. I think it's quite unnatural to guess the correct construction before having the corresponding $s+2$ estimate.
28.06.2018 19:56
I think it's possible to completely characterize sequences $a$ for which \[ a_n \mid a_k + a_{k+1} + \cdots + a_{k+n-1} \]I would be thankful if someone could go through the attached pdf file and check if I have made any mistakes. Note. I don't think I mentioned that I call a number $n$ important if $a_n>1$and esteemed if $a_n = \sum_{i=1}^{n-1}a_i$. @below The problem only asks us to find the minimal possible value of $a_{2m}$. I found all sequences $a$ that satisfy the problem condition
Attachments:
ELMO_Type_Sequences.pdf (202kb)
28.06.2018 20:14
p_square wrote: Slight generalisation: To find maximum of $a_m$. https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYi85L2VmZmZiMDdhYzM1YTA1MDk1Yzc0MWNjOGVlMTY5MGYyMDY3NGRhLnBkZg==&rn=RUxNT18xOC5wZGY= I didn't see how you generalize it
31.07.2020 06:25
01.11.2020 05:12
03.01.2021 12:26
whatshisbucket wrote: Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $$a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$$for all positive integers $k$ and $n.$ For a given positive integer $m,$ find the maximum possible value of $a_{2m}.$ Proposed by Krit Boonsiriseth Interesting problem. I claim that the answer is $\boxed{a_{2m} \le 2^m - 1}$ achieved by the sequence: \begin{align*} \begin{cases} a_{2k + 1} &= 1 \ \ \ \ \ \ \ \ \text{for } k \in \mathbb{N} \\ a_{2k} &= 2^k - 1 \ \text{for } k \in \mathbb{N} \end{cases} \end{align*}Claim 01 (Main Claim). For any $m \in \mathbb{N}$, $a_{2m - 1} + a_{2m} \le 2^{m}$. Proof. To prove this, let us observe the sequence \[ a_n \mid a_k + a_{k + 1} + \dots + a_{k + n - 1} \]This quickly gives us \[ a_n \mid a_1 + a_2 + \dots + a_{n - 1} \ \text{and} \ a_n \mid a_{n + 1} - a_1 = a_{n + 1} - 1 \]Therefore, \[ a_n \mid a_1 + a_2 + \dots + a_{n - 1} \]\[ a_{n + 1} \mid a_1 + a_2 + \dots + a_n = a_n \left( 1 + \frac{a_1 + a_2 + \dots + a_{n - 1}}{a_n} \right) \]Since $a_{n + 1} \equiv 1 \ (\text{mod} \ a_n)$, then $\gcd(a_n, a_{n + 1}) = 1$, and hence, \[ a_{n + 1} \mid 1 + \frac{a_1 + a_2 + \dots + a_{n - 1}}{a_n} \]Therefore, we have $a_{n + 1} \le 1 + \frac{a_1 + a_2 + \dots + a_{n - 1}}{a_n}$. Now, we'll induct. The statement is true for $m = 1$, as $a_1 = a_2 = 1$. Now, suppose that the statement is true for $m = k$. Then, we have \[ a_{2k + 1} + a_{2k + 2} \le a_{2k + 1} + 1 + \frac{a_1 + a_2 + \dots + a_{2k}}{a_{2k + 1}} \le a_1 + a_2 + \dots + a_{2k} + 2 = (2^1) + (2^2) + \dots + (2^k) + 2 = 2^{k + 1}\]We are done. To finish this, notice that $1 + a_{2m} \le a_{2m - 1} + a_{2m} \le 2^m \Rightarrow a_{2m} \le 2^m - 1$, we are done. Remark. I think the hardest problem of this problem is figuring out the main claim and equality case. The main claim comes intuitively after trying to bash several small cases (drawing a diagram tree helps a lot). The main key here is the bounding part, for the bounding to be as strong as possible. The last part when inducting comes naturally (inspired a lot from 2018 A4 somehow) since the inequality focus on one variable $a_{2k + 1}$ and other terms are fixed.
12.02.2021 22:58
The answer is $2^{1009} - 1$. The construction is as follows: Let $a_{2k+1} = 1, a_{2k} = 2^{k} - 1$. It's not hard to check that this works. We will prove this is maximal. First, let $S_{n} = a_{1} + a_{2} + \ldots + a_{n}$. I claim $S_{2n-1}\leq 2^{n} - 1$. We can prove this by induction. If we let our base case be $n = 1$, we have $S_{1} = 1 \leq 2^{1} - 1 = 1$. For our inductive step, assume $S_{2n-1}\leq 2^{n} - 1$, we will prove $S_{2n + 1} \leq 2^{n+1} - 1$. First, observe that $a_{2n} | a_{2n} + \ldots + a_{1} \Rightarrow a_{2n} | S_{2n-1}$. Next, observe that \[a_{2n} | a_{2n} + \ldots + a_{1}, a_{2n+1} + a_{2n} + \ldots a_{2} \Rightarrow a_{2n} | a_{2n+1} - a_{1} = a_{2n+1} - 1\]Thus, $a_{2n+1} \equiv 1\mod a_{2n}$. Let $r$ be the number such that $a_{2n}r = S_{2n-1}$, and $k$ be the number such that $a_{2n+1} = ka_{2n} + 1$. By euclidean algorithm, $\gcd(a_{2n+1}, a_{2n}) = 1$. We also have \[a_{2n+1} = | a_{2n+1} + a_{2n} + \ldots + a_{1}, a_{2n} + S_{2n-1} = a_{2n}(r+1)\]Since $\gcd(a_{2n+1}, a_{2n}) = 1$, this means $a_{2n+1} | r+1 \Rightarrow a_{2n+1}\leq r+1$. Then, \[S_{2n+1} = S_{2n-1} + a_{2n} + a_{2n+1} \leq S_{2n-1} + a_{2n} + \frac{S_{2n-1}}{a_{2n}} + 1 \leq 2S_{2n-1} + 1 \leq 2^{n+1} - 1\]This proves our desired induction. Now, observe that \[a_{2018} | a_{2018} + a_{2017} + \ldots + a_{1} \Rightarrow a_{2018} | S_{2017}\]This means \[a_{2018}\leq S_{2017} \leq 2^{1009} - 1\]
02.04.2021 19:46
The answer is $2^m - 1$ achievable by the sequence \[ a_i = \begin{cases} 1 & i \text{ is odd} \\ 2^{i/2}-1 & i \text{ is even}. \end{cases} \] First, $a_{2m-1} \mid a_{2m} - a_1 = a_{2m} - 1$, so $\gcd(a_{2m-1}, a_{2m}) = 1$. Now since $a_{2m-1}, a_{2m} \mid a_1 + \cdots + a_{2m-1}$, we have \[a_{2m-1}a_{2m} \le a_1 + \cdots + a_{2m-1} \implies a_{2m} \le \frac{a_1 + \cdots + a_{2m-2}}{a_{2m-1}} + 1.\]So \begin{align*} a_1 + \cdots + a_{2m} &= (a_1 + \cdots + a_{2m-2}) + a_{2m-1} + \frac{a_1 + \cdots + a_{2m-2}}{a_{2m-1}} + 1\\ &\le 2(a_1 + \cdots + a_{2m-2}) +2. \end{align*}Noting that $a_2 = 1$, we inductively have $2a_{2m} \le a_1 + \cdots + a_{2m} \le 2(2^m - 1)$, giving $a_{2m}\le 2^m - 1$.
20.06.2021 07:41
In general, we have the upper bound $a_{2m} \leq 2^m - 1$, where this is achievable by letting $a_{odd} = 1$ and $a_{2k} = 2^k - 1$: a quick check shows that this sequence does indeed work. Note that $a_n \mid a_k + \ldots + a_{k + (n-1)}$ and $a_n \mid a_{k + 1} + \ldots + a_{k + n}$ hence $a_n \mid a_{k+n} - a_k$, always. Note that this means $a_{2k-1} \mid a_{2k} - 1$ for all $k$. Thus, it also follows that $a_{2k-1}, a_{2k}$ must always be relatively prime. Additionally, since the sum of any consecutive $r$ terms is divisible by $a_r$, note that $a_{2r}$ divides $a_1 + \ldots + a_{2r}$ and thus $a_1 + \ldots + a_{2r-1}$, and $a_{2r-1}$ also divides $a_1 + \ldots + a_{2r-1}$. Thus, we may arrive at the size bound\[a_{2r-1}a_{2r} \leq a_1 + \ldots + a_{2r - 1}\]for all positive integers $r$. We will induct to show that $a_{2r - 1} + a_{2r} \leq 2^r$ for all positive integers $r$. The base case is easy: note $a_2 \mid a_1 + a_2$ hence $a_2 = 1$, and $a_1 + a_2 = 2 \leq 2$. Now, we use strong induction; suppose $a_{2r - 1} + a_{2r} \leq 2^r$ up until $r = k$. Then,\[a_{2k+1}a_{2k+2} \leq (2^1 + \ldots + 2^k) + a_{2k+1} \iff a_{2k+1}(a_{2k+2} - 1) \leq 2(2^k - 1).\]It is known that if positive $ab = c$, then $a+b$ is maximized when $a$ is as small (but still positive) as possible (in fact, if they are positive integers, then $a + b \leq 1 + c$). Hence, if $a_{2k+1}(a_{2k+2} - 1) = P \leq 2(2^k - 1)$ then\[a_{2k+1} + (a_{2k+2} - 1) \leq 1 + P \leq 2^{k+1} - 1\]so indeed $a_{2k+1} + a_{2k+2} \leq 2^{k+1}$, finishing our induction. This also finishes the problem: if $a_{2r-1} + a_{2r} \leq 2^r$ for all $r$, then $a_2r \leq 2^r - 1$ for all $r$.
25.01.2022 20:44
My answer is $a_{2m}= 2^m-1$, the example is $a_{2i}=2^i-1, a_{2i-1}=1$ for all $n$ positive integer. Key claim: For all any positive integer $n$ : $a_{2n}+a_{2n-1} \leq 2^n$ Proof: We have that: $$a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}, a_n \mid a_{k+1}+a_{k+2}+\dots+a_{k+n} \implies a_n \mid a_{k+n}-a_k$$ We have that $a_1=1$ so $a_n \mid a_{n+1}-1 \implies (a_n,a_{n+1})=1$, then: $$a_n \mid a_1 + \dots+a_n $$$$ a_{n+1} \mid a_1+ \dots + a_{n+1} \implies a_{n+1} \mid a_1+ \dots + a_n $$$$ a_na_{n+1} \mid a_1+ \dots +a_n \implies a_{2n}a_{2n-1} \mid a_1+ \dots +a_{2n-1}$$And now we can prove the key claim with induction: $$a_{2n}a_{2n-1} \leq (a_1+ \dots +a_{2n-1})+a_{2n} \leq 2^1+2^2+\dots +2^{n-1} + a_{2n-1}= 2^n-2+a_{2n-1} \implies a_{2n-1}(a_{2n}-1) \leq 2^n-2$$Finally if $a_{2n} \ge 2 \implies a_{2n-1}+(a_{2n}-1)-1 \leq a_{2n-1}(a_{2n}-1) \leq 2^n-2$ this implies the claim. And if $a_{2n}=1\implies a_{2n-1} \mid a_1 + \dots + a_{2n-2} \implies a_{2n-1} \leq 2^n-2 \implies a_{2n}+a_{2n-1} \leq 2^n-1$ And with this $a_{2n}+a_{2n-1} \leq 2^n \implies a_{2n} \leq 2^n-1$ as desired. $\blacksquare$
17.05.2023 11:12
The answer is $2^m-1$ - do this by considering $a_{2n}=2^i-1$ and $a_{2n-1}=1$ for positive integers $n$. Key Claim: $a_n+a_{n+1}\leq a_1+\ldots +a_{n-1}+2=s_{n-1}+2$. Proof: If $a_n=1$ then since $a_{n+1}\mid a_1+\ldots + a_n$ we have $a_n+a_{n+1}\leq a_n + s_n=s_{n-1}+2$. If $a_{n+1}=1$ then $a_n\mid a_1+\ldots+a_{n-1}$ so $a_n+a_{n+1}\leq s_{n-1}+1\leq s_{n-1}+2$. If $a_n,a_{n+1}\neq 1$ then since $a_n\mid a_1+\ldots +a_n$ and $a_2+\ldots +a_{n+1}$ we have $a_{n+1}=ka_n+1$ for some positive integer $k$. But $a_n$ and $ka_n+1=a_{n+1}\mid s_n$ so $a_n(ka_n+1)\mid s_n$ because $\gcd(a_n,ka_n+1)=1$. Thus, $$a_n+a_{n+1}=(k+1)a_n+1\leq ka_n^2+1=a_n(ka_n+1)+1-a_n\leq s_n+1-a_n=s_{n-1}+1\leq s_{n-1}+2$$as needed. Using the claim: $a_{2m}+a_{2m-1}\leq (a_1+a_2)+\ldots+(a_{2m-3}+a_{2m-2})+2\leq 2+4+\ldots+2^m + 2\leq 2^m-2+2=2^m$. Thus, $a_{2m}\leq 2^m-a_{2m-1}\leq 2^m-1$.
26.06.2023 14:24
Here's a solution which classifies which numbers can and can't go to $1$. Denote $a_n=f(n)$. Let $\mathcal{A}$ denote the numbers whose image isn't $1$ and $\mathcal{B}$ the rest. Claim: If $a\in\mathcal{A}$, $b\in\mathcal{B}$ and $a<b$, then $b-a\in\mathcal{B}$. Proof. Then $f(a)\mid f(b-a)-1$ and $f(b-a)\mid f(a)-1$. If neither are $1$, we get $f(a)<f(b-a)<f(a)$, absurd. So if $\mathcal{A}$ has two coprime elements, $\mathcal{B}$ must be finite (linear sums of coprime numbers span $\mathbb{N}$ after some point). Well, Claim: $\mathcal{B}$ is infinite. Proof. $f(2)\mid 1$ so $f(2)=1$. Assume the contrary, and for $f(n)>1$ for $n\ge C$. Then \[f(n-1)\mid f(n)-1\text{ }(\spadesuit)\text{ and }f(n-2)\mid f(n)-1\text{ }(\heartsuit)\]so $f$ is increasing in $[C,+\infty)$ and $f$ is bounded below by some $n-c$. By the divisibility, $f(n)< (n-k)f(n-1)$ for sufficiently large $n$ depending on $k$. $f(n+1)\neq f(n)+1$ for all large $n$ we would have a contradiction because the sequence would be $\mathcal{O}(2^n)$. If $f(n-1)=f(n-2)+1$, from $(\spadesuit)$ and $(\heartsuit)$, \[f(n-1)(f(n-1)-1)\mid f(n)-1\Rightarrow f(n)>(n-1-c)f(n-1)\Rightarrow n-k>n-1-c\]and choosing $k>c+1$, we get a contradiction. Because $2018=2\cdot 1009$, and if $f(1009)\neq1$ we wouldn't get a maximum, we get $f$ at odds is $1$ and at evens \[f(2k)\mid k+f(2)+f(4)+\dots+f(2k-2)\Longrightarrow f(2k)\le 2^k-1\]and equality can hold. Thus, \[f(2018)\le\boxed{2^{1009}-1.}\]
22.07.2023 06:25
this problem makes me so happy The answer is $2^m-1$, achieved by the sequence $1,2^1-1,1,2^2-1,1,2^3-1,\ldots$. We show that this sequence satisfies the problem conditions. If $n$ is odd, then $a_n=1$, so $a_n \mid a_k+a_{k+1}+\cdots+a_{k+n-1}$. If $n$ is even, then let $a_k+a_{k+1}=2^m$. Notice that $a_{i+2}+a_{i+3}=2(a_i+a_{i+1})$ for all positive integers $i$, so $a_{k+2i}+a_{k+2i+1}=2^{m+i}$ for all positive integers $i$, so \[a_k+a_{k+1}+\cdots+a_{k+n-1}=2^m+2^{m+1}+\cdots+2^{m+n/2-1}=2^m(2^{n/2}-1)\]is divisible by $a_n=2^{n/2}-1$. Now, we show that $a_{2m} \le 2^m-1$. Let $s_n=a_1+a_2+\cdots+a_n$ for all positive integers $n$. Claim: $s_n \le 2s_{n-2}+2$ for all integers $n \ge 3$. Proof: We have $a_n \mid s_n$, so $a_n \mid s_{n-1}$. We also have $a_{n-1} \mid s_{n-1}$. Notice that $a_{n-1} \mid s_n-1$, so $a_{n-1} \mid s_n-1-s_{n-1}=a_n-1$. Thus, $\gcd(a_{n-1},a_n)=1$, so $a_n \mid s_{n-1}$ and $a_{n-1} \mid s_{n-1}$ imply $a_{n-1}a_n \mid s_{n-1}$. Therefore, we have $a_{n-1}a_n \le s_{n-1}$, or $a_{n-1}(a_n-1) \le s_{n-2}$. If $a_n=1$, then $a_{n-1} \le s_{n-2}$, so $s_n=s_{n-2}+a_n+a_{n-1} \le 2s_{n-2}+1$, as desired. If $a_n \ne 1$, then $a_{n-1}+a_n-1 \le s_{n-2}+1$ by smoothing, so $a_{n-1}+a_n \le s_{n-2}+2$, which means $s_n \le 2s_{n-2}+2$, as desired. $\square$ We have $a_2=1$, so $s_2=2$. By induction using the previous claim, we have $s_{2m} \le 2^{m+1}-2$. Since $a_{2m} \le s_{2m-1}$, we have $a_{2m} \le 2^m-1$. $\square$
08.08.2023 17:37
surprising The answer is $2^m-1$, achieved by making $a_{2i-1}=1$ and $a_{2i}=2^i-1$ for all $i \geq 1$, which can be checked to work. In general, note that $a_k \equiv a_{k+n} \pmod{a_n}$ for all positive integers $k,n$. The following claim is the the main part of the problem. Claim: We have $a_{2i-1}+a_{2i} \leq 2^i$ for all positive integers $i$. Proof: This is by strong induction, with the base case of $i=1$ being clear. For $i \geq 2$, let $a_1+\cdots+a_{2i-2}=ka_{2i-1}$. Then, we should have $a_{2i} \equiv a_1=1 \pmod{a_{2i-1}}$ and $a_{2i} \mid a_1+\cdots+a_{2i-1}=(k+1)a_{2i-1}$. Therefore, we in fact have $a_{2i} \mid k+1$, so $$a_{2i-1}+a_{2i} \leq a_{2i-1}+k+1 \leq ka_{2i-1}+2,$$where the last inequality is equivalent to $(k-1)(a_{2i-1}-1) \geq 0$. By summing the inductive hypothesis from $1$ to $i-1$, we find that $ka_{2i-1} \leq 2^i-2$, so the desired conclusion follows. $\blacksquare$ To finish, note that for our given value of $m$, we have $a_{2m} \leq 2^m-a_{2m-1} \leq 2^m-1$. $\blacksquare$
27.07.2024 19:56
17.08.2024 07:24
Really nice NT sequence problem i would say. First note that $a_n \mid a_{n+k}-a_k$ so we have $a_n \mid a_{n+1}-1$ so $\gcd(a_n, a_{n+1})=1$, also note that $a_2 \mid 1+a_2$ so $a_2=1$ and therefore $a_n \mid a_{n+2}-1$ so $\gcd(a_n, a_{n+2})=1$ as well. Now let $S_n=\sum_{i=1}^{n} a_i$, then we have $a_n \mid S_n$ but also $a_{n+1} \mid S_{n+1}=S_n+a_{n+1}$ so $a_{n+1} \mid S_n$ which means $a_na_{n+1} \mid S_n$ for all positive integers $n$. Now i claim by induction that $S_{2n} \le 2^{n+1}-2$ and $a_{2n} \le 2^n-1$ are both true simultaneously, indeed base case $n=1$ is trivial as $S_2=2$ and $a_2=1$, now suppose it's true for $n=k$, we will prove it for $n=k+1$ this way: $$a_{2k+2} \mid \frac{S_{2k+1}}{a_{2k+1}}=1+\frac{S_{2k}}{a_{2k+1}} \implies a_{2k+2} \le 1+S_{2k} \le 2^{k+1}-1$$$$a_{2k+2}a_{2k+1} \mid S_{2k+1} \implies a_{2k+1}(a_{2k+2}-1) \le S_{2k} \le 2^{k+1}-2 \implies a_{2k+1}+a_{2k+2} \le 2^{k+1} \implies S_{2k+2}=S_{2k}+a_{2k+1}+a_{2k+2} \le 2^{k+1}-2+2^{k+1}=2^{k+2}-2$$Therefore the induction is complete and our claim is true. Now to achieve equality we let $a_{2i+1}=1$ and $a_{2i}=2^i-1$ for all $i \in \mathbb Z_{>0}$ which trivially works, thus we are done .
19.08.2024 19:03