Japan Mathematical Olympiad

$\left[\frac{47}{2}\cdot 3^{667}-\frac{3}{2}\right]$

For $(a_1,a_2,\dots ,a_n)$ satisfying the condition of the problem, let us put $A_0=1$ and $$S(a_1,a_2,\dots ,a_n)=A_1+A_2+\cdots +A_n.$$

Lemma 1. For $(a_1,a_2,\dots ,a_n)$ which yields the maximum possible value of $S(a_1,a_2,\dots ,a_n)$, we must have $a_i\ge a_{i+1}$ for each $i$ satisfying $1\le i\le n-1$.

Proof of Lemma 1. Suppose there exists a $k$ with $1\le k\le n-1$, for which $a_k<a_{k+1}$. Let us define an $n$-tuple of positive integers $(b_1,b_2,\dots ,b_n)$ by setting $$b_i=a_i\text{ if }i\ne k,k+1;b_k=a_{k+1},b_{k+1}=a_k.$$ Since $b_1+b_2+\cdots +b_n=2008$, $(b_1,b_2,\dots ,b_n)$ satisfies the condition of the problem. To prove the Lemma, therefore, it is enough to show that $S(a_1,a_2,\dots ,a_n)<S(b_1,b_2,\dots ,b_n)$. Let us put $B_i=b_1{b}_2\dots b_i$ for each $i$. It is clear that $A_i=B_i$ holds for each $i\ne k$. We also have $$B_k-A_k=(a_{k+1}-a_k)A_{k-1}>0,$$ and therefore, the Lemma is proved.

Lemma 2. If $(a_1,a_2,\dots ,a_n)$ with $a_1+a_2+\cdots +a_n=2008$ gives the maximum possible value to $S(a_1,a_2,\dots ,a_n)$, then $a_i\le 3$ must hold for each $i$, $1\le i\le n$.

Proof of Lemma 2. Suppose there exists a $k$ with $1\le k\le n$, for which $a_k\ge 4$. We may assume that $a_1\ge 4$ in view of Lemma 1. Let us define an $n+1$ tuple $(c_1,c_2,\dots ,c_{n+1})$ by setting $$c_1=a_1-2;c_2=2;c_i=a_{i-1}\text{ (for }2<i\le n+1).$$ Since $c_1+c_2+\cdots +c_{n+1}=2008$, to prove the Lemma it is enough to show that $S(a_1,a_2,\dots ,a_n)<S(c_1,c_2,\dots ,c_{n+1})$. Let us set $Q=\frac{A_2+A_3+\cdots +A_n}{A_1}$. Then we have $$S(a_1,a_2,\dots ,a_n)=a_1+Q{a}_1.$$ We also have $$S(c_1,c_2,\dots ,c_{n+1})=(a_1-2)+2(a_1-2)+2Q(a_1-2).$$ From these identities and from the fact that $a_1\ge 4$ it follows that $$S(c_1,c_2,\dots ,c_{n+1})=S(a_1,a_2,\dots ,a_n)=(2a_1-6)+Q(a_1-4)>0,$$ which establishes the claim of the Lemma.

Lemma 3. There exists a combination $(n,a_1,a_2,\dots ,a_n)$ giving $S(a_1,a_2,\dots ,a_n)$ the maximum value and having the additional property that 1 appears among $a_1,a_2,\dots ,a_n$ at most once.

Proof of Lemma 3. Suppose $S(a_1,a_2,\dots ,a_n)$ attains the maximum possible value, and suppose there are two or more 1's among $a_1,a_2,\dots ,a_n$. We may assume that $a_{n-1}=a_n=1$ in view of Lemma 1. Let us define an $n-1$ tuple $(d_1,d_2,\dots ,d_{n-1})$ by $$d_i=a_i(i<n-1);d_{n-1}=2.$$ Then, $d_1+d_2+\cdots +d_{n-1}=2008$. For each $k$ with $1\le k\le n-1$, let $D_k=d_1{d}_2\dots d_k$. We then have $A_k=D_k$ when $1\le k\le n-2$. We also have $D_{n-1}=2A_{n-2}$. Furthermore, from the fact that $a_{n-1}=a_n=1$ it follows that $A_{n-1}=A_n=A_{n-2}$. Consequently, we have $S(a_1,a_2,\dots ,a_n)=S(d_1,d_2,\dots ,d_{n-1})$. This shows that if there are two or more 1's among $a_1,a_2,\dots ,a_n$, then we can introduce $d_1,d_2,\dots ,d_{n-1}$ to reduce the number of 1's among $a_1,a_2,\dots ,a_n$ while keeping the maximality of the value $S(a_1,a_2,\dots ,a_n)$. We can reduce the number of 1's further, if necessary, by starting with $d_1,d_2,\dots ,d_{n-1}$ and going through the same procedure. Thus, there is a combination $(n;a_1,a_2,\dots ,a_n)$ of positive integers which give the maximum value of $S(a_1,a_2,\dots ,a_n)$ with the additional property that 1 appears among $a_1,a_2,\dots ,a_n$ at most once.

Lemma 4. There exists a combination $(n;a_1,a_2,\dots ,a_n)$ of positive integers which gives the maximum value for $S(a_1,a_2,\dots ,a_n)$ and for which there are at most three 2's among $a_1,a_2,\dots ,a_n$.

Proof of Lemma 4. Suppose there exists an $n$ tuple $a_1,a_2,\dots ,a_n$ which gives the maximum value for $S(a_1,a_2,\dots ,a_n)$ and there are $4$ or more $2$'s among $a_1,a_2,\dots ,a_n$. In view of Lemma 1, we may assume that there exists a $k$ with $1\le k\le n-3$ such that $a_k=a_{k+1}=a_{k+2}=a_{k+3}=2$. Introduce an $n-1$ tuple $(e_1,e_2,\dots ,e_{n-1})$ by defining $$e_i=a_i(i<k);3=a_i+k;i=k,k+1;i>k+1.$$ If $k>1$ call $P=A_1+A_2+\cdots +A_{k-1}$. If $k=1$, let $P=0$. Also, if $k<n-3$ let $Q=\frac{A_{k+4}+A_{k+5}+\cdots +A_n}{A_{k+3}}$, and $Q=0$ if $k=n-3$. Then, we have $$S(a_1,a_2,\dots ,a_n)=P+2A_{k-1}+4A_{k-1}+8A_{k-1}+16A_{k-1}+16Q{A}_{k-1}.$$ We also have $$S(e_1,e_2,\dots ,e_{n-1})=P+3A_{k-1}+9A_{k-1}+18A_{k-1}+18Q{A}_{k-1}.$$ It follows from these identities that we have $$S(e_1,e_2,\dots ,e_{n-1})-S(a_1,a_2,\dots ,a_n)=2Q{A}_{k-1}\ge 0.$$

Since $e_1+e_2+\cdots +e_{n-1}=2008$, the combination $(n-1;e_1,e_2,\cdots ,e_{n-1})$ satisfies the condition of the problem, and since $S(a_1,a_2,\cdots ,a_n)$ has the maximum value, $S(e_1,e_2,\cdots ,e_{n-1})$ also takes the maximum value. Therefore, if there are 4 or more 2's among $a_1,a_2,\cdots ,a_n$, then we can reduce the number of 2's without losing the maximality of the value $S(a_1,a_2,\cdots ,a_n)$. This proves the assertion of this Lemma.

Now going back to the problem, we note that, in view of Lemmas 1, 2, 3, 4, it is enough to check the following 3 cases in order to determine the maximum value of $S(a_1,a_2,\cdots ,a_n)$: $$(1)a_1=a_2=\cdots =a_{669}=3,a_{670}=1.$$ $$(2)a_1=a_2=\cdots =a_{667}=3,a_{668}=a_{669}=a_{670}=2,a_{671}=1.$$ $$(3)a_1=a_2=\cdots =a_{668}=3,a_{669}=a_{670}=2.$$ Let $X=3+3^2+\cdots +3^{667}$ and $Y=3^{667}$. Then

In the case (1): $S(a_1,a_2,\cdots ,a_n)=X+3Y+9Y+9Y=X+21Y$,

In the case (2): $S(a_1,a_2,\cdots ,a_n)=X+2Y+4Y+8Y+8Y=X+22Y$,

In the case (3): $S(a_1,a_2,\cdots ,a_n)=X+3Y+6Y+12Y=X+21Y$,

so that we have the desired maximum value to be $X+22Y=\frac{47}{2}\cdot 3^{667}-\frac{3}{2}$.