48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Consider a sequence ($a_i$) satisfying the conditions. For arbitrary integers $0\le k\le l\le n^2+n$ denote $S(k,l]=a_{k+1}+\cdots +a_l$. (If $k=l$ then $S(k,l]=0$.) Then condition (b) can be rewritten as $S(i,i+n]<S(i+n,i+2n]$ for all $0\le i\le n^2-n$. Notice that for $0\le k\le l\le m\le n^2+n$ we have $S(k,m]=S(k,l]+S(l,m]$.

By condition (b), $$0\le S(0,n]<S(n,2n]<\cdots <S\left(n^2,n^2+n\right]\le n.$$ We have only $n+1$ distinct integers in the interval $[0,n]$; hence, $$S(vn,(v+1)n]=v\text{for all }0\le v\le n.\text{\hspace{1em}(2)}$$ In particular, $S(0,n]=0$ and $S\left(n^2,n^2+n\right]=n$, therefore $$\begin{array}{rl}{a}_1& =a_2=\dots =a_n=0\\ a_{n^2+1}& =a_{n^2+2}=\dots =a_{n^2+n}=1\end{array}\text{\hspace{1em}(3)(4)}$$ Subdivide sequence ($a_i$) into $n+1$ blocks, each consisting of $n$ consecutive terms, and number them from 0 to $n$. We show by induction on $v$ that the $v$th block has the form $$(\underset{n-v}{\underbrace{0\dots 0}}\underset{v}{\underbrace{1\dots 1}})$$ The base case $v=0$ is provided by (3).

Consider the $v$th block for $v>0$. By (2), it contains some "ones". Let the first "one" in this block be at the $u$th position (that is, $a_{u+vn}=1$). By the induction hypothesis, the $(v-1)$th and $v$th blocks of $\left(a_i\right)$ have the form $$(\underset{n-v+1}{\underbrace{0\dots 0}})(\underbrace{0\dots 0}1\ast \dots \ast )$$ where each star can appear to be any binary digit. Observe that $u\le n-v+1$, since the sum in this block is $v$. Then, the fragment of length $n$ bracketed above has exactly $(v-1)+1$ ones, i.e. $S(u+(v-1)n,u+vn]=v$. Hence, $$v=S(u+(v-1)n,u+vn]<S(u+vn,u+(v+1)n]<\cdots <S\left(u+(n-1)n,u+n^2\right]\le n;$$ we have $n-v+1$ distinct integers in the interval $[v,n]$, therefore $S(u+(t-1)n,u+tn]=t$ for each $t=v,\dots ,n$.

Thus, the end of sequence $\left(a_i\right)$ looks as following: $$(\underset{v-1}{\underbrace{u\text{ zeroes}}}\stackrel{0\dots 0}{\overbrace{0\dots 01\dots 1}})(\underset{v}{\underbrace{0\dots 01}}\stackrel{v+1}{\overbrace{0\dots \ast }}(\underset{v+1}{\underbrace{\ast \dots \ast \ast \dots \ast }})\dots (\underset{n}{\underbrace{1\dots 1}}\stackrel{n}{\overbrace{1\dots 1}})$$ (each bracketed fragment contains $n$ terms). Computing in two ways the sum of all digits above, we obtain $n-u=v-1$ and $u=n-v+1$. Then, the first $n-v$ terms in the $v$th block are zeroes, and the next $v$ terms are ones, due to the sum of all terms in this block. The statement is proved.

We are left to check that the sequence obtained satisfies the condition. Notice that $a_i\le a_{i+n}$ for all $1\le i\le n^2$. Moreover, if $1\le u\le n$ and $0\le v\le n-1$, then $a_{u+vn}<a_{u+vn+n}$ exactly when $u+v=n$. In this case we have $u+vn=n+v(n-1)$.

Consider now an arbitrary index $0\le i\le n^2-n$. Clearly, there exists an integer $v$ such that $n+v(n-1)\in [i+1,i+n]$. Then, applying the above inequalities we obtain that condition (b) is valid.

---

Alternative solution.

Similarly to Solution 1, we introduce the notation $S(k,l]$ and obtain (2), (3), and (4) in the same way. The sum of all elements of the sequence can be computed as $$S\left(0,n^2+n\right]=S(0,n]+S(n,2n]+\dots +S\left(n^2,n^2+n\right]=0+1+\dots +n.$$ For an arbitrary integer $0\le u\le n$, consider the numbers $$S(u,u+n]<S(u+n,u+2n]<\dots <S\left(u+(n-1)n,u+n^2\right].\text{\hspace{1em}(5)}$$ They are $n$ distinct integers from the $n+1$ possible values $0,1,2,\dots ,n$. Denote by $m$ the "missing" value which is not listed. We determine $m$ from $S\left(0,n^2+n\right]$. Write this sum as $S\left(0,n^2+n\right]=S(0,u]+S(u,u+n]+S(u+n,u+2n]+\dots +S\left(u+(n-1)n,u+n^2\right]+S\left(u+n^2,n^2+n\right]$. Since $a_1=a_2=\dots =a_u=0$ and $a_{u+n^2+1}=\dots =a_{n^2+n}=1$, we have $S(0,u]=0$ and $S\left(u+n^2,n+n^2\right]=n-u$. Then $$0+1+\dots +n=S\left(0,n^2+n\right]=0+((0+1+\dots +n)-m)+(n-u),$$ so $m=n-u$.

Hence, the numbers listed in (5) are $0,1,\dots ,n-u-1$ and $n-u+1,\dots ,n$, respectively, therefore $$S(u+vn,u+(v+1)n]=\{\begin{array}{ll}v,& v\le n-u-1,\\ v+1,& v\ge n-u\end{array}\text{for all }0\le u\le n,0\le v\le n-1.\text{\hspace{1em}(6)}$$ Conditions (6), together with (3), provide a system of linear equations in variables $a_i$. Now we solve this system and show that the solution is unique and satisfies conditions (a) and (b).

First, observe that any solution of the system (3), (6) satisfies the condition (b). By the construction, equations (6) immediately imply (5). On the other hand, all inequalities mentioned in condition (b) are included into the chain (5) for some value of $u$.

Next, note that the system (3), (6) is redundant. The numbers $S(kn,(k+1)n]$, where $1\le k\le n-1$, appear twice in (6). For $u=0$ and $v=k$ we have $v\le n-u-1$, and (6) gives $S(kn,(k+1)n]=v=k$. For $u=n$ and $v=k-1$ we have $v\ge n-u$ and we obtain the same value, $S(kn,(k+1)n]=v+1=k$. Therefore, deleting one equation from each redundant pair, we can make every sum $S(k,k+n]$ appear exactly once on the left-hand side in (6).

Now, from (3), (6), the sequence $\left(a_i\right)$ can be reconstructed inductively by $$a_1=a_2=\dots =a_{n-1}=0,a_{k+n}=S(k,k+n]-\left(a_{k+1}+a_{k+2}+\dots +a_{k+n-1}\right)(0\le k\le n^2)$$ taking the values of $S(k,k+n]$ from (6). This means first that there exists at most one solution of our system. Conversely, the constructed sequence obviously satisfies all equations (3), (6) (the only missing equation is $a_n=0$, which follows from $S(0,n]=0$). Hence it satisfies condition (b), and we are left to check condition (a) only.

For arbitrary integers $1\le u,t\le n$ we get $$\begin{array}{rl}{a}_{u+tn}-a_{u+(t-1)n}& =S(u+(t-1)n,u+tn]-S((u-1)+(t-1)n,(u-1)+tn]\\ & =\{\begin{array}{ll}(t-1)-(t-1)=0,& t\le n-u\\ t-(t-1)=1,& t=n-u+1\\ t-t=0,& t\ge n-u+2\end{array}\end{array}$$ Since $a_u=0$, we have $$a_{u+vn}=a_{u+vn}-a_u=\sum _{t=1}^v\left(a_{u+tn}-a_{u+(t-1)n}\right)$$ for all $1\le u,v\le n$. If $v<n-u+1$ then all terms are 0 on the right-hand side. If $v\ge n-u+1$, then variable $t$ attains the value $n-u+1$ once. Hence, $$a_{u+vn}=\{\begin{array}{ll}0,& u+v\le n\\ 1,& u+v\ge n+1\end{array}$$ according with (1). Note that the formula is valid for $v=0$ as well.

Finally, we presented the direct formula for $\left(a_i\right)$, and we have proved that it satisfies condition (a). So, the solution is complete.