31st Turkish Mathematical Olympiad

Answer: $3\cdot 31-6=87$. Let us consider more general case when $31$ is replaced by $n\ge 3$: At the beginning the board contains $n$ vectors $$(1,0,0,\dots ,0),(0,1,0,\dots ,0),\dots ,(0,0,0,\dots ,1)$$ each having $n$ components and we are going get all the $n$ component vectors $$(0,1,1,\dots ,1),(1,0,1,\dots ,1),\dots ,(1,1,1,\dots ,0).$$ We will show that the minimal number of steps is $3n-6$.

First of all by two different ways we show that $3n-6$ steps are sufficient. Let $v_i^{\prime \prime }$ be a vector whose $i$-th coordinate is $1$ and all remaining $n-1$ coordinates are $0$ and let $u_i^{\prime \prime }$ be a vector whose $i$th coordinate is $0$ and all remaining $n-1$ coordinates are $1$.

First method: Induction over $n$. If $n=3$ then by applying $v_1^3+v_2^3$, $v_1^3+v_3^3$ and $v_2^3+v_3^3$ we get the $u_1^3,u_2^3$ and $u_3^3$ in $3$ steps. Assume that for $n=k$ the required vectors can be obtained in $3k-6$ steps and let $n=k+1$. At the first step by adding $v_k^{k+1}$ and $v_{k+1}^{k+1}$ we get the vector $v_k^{k+1}+v_{k+1}^{k+1}\equiv w_{k,k+1}^{k+1}$. By inductive hypothesis, starting with vectors $v_1^k,v_2^k,\dots ,v_{k-1}^k$ and $v_k^k$ after $3k-6$ steps we can get the vectors $u_1^k,u_2^k,\dots ,u_{k-1}^k$ and $u_k^k$. If we replace $v_1^k$ by $v_1^{k+1}$, $v_2^k$ by $v_2^{k+1}$, $\dots$, $v_{k-1}^k$ by $v_{k-1}^{k+1}$ and $v_k^k$ by $w_{k,k+1}^{k+1}$ and apply the same $3k-6$ steps then we will get the vectors $u_1^{k+1},u_2^{k+1},\dots ,u_{k-1}^{k+1}$

and the vector ${\vec{w}}_{k,k+1}^{k+1}$ whose last two coordinates are $0$ and the remaining coordinates are $1$. Finally by applying $v_k^{k+1}+{\bar{w}}_{k,k+1}^{k+1}$ and $v_{k+1}^{k+1}+{\bar{w}}_{k,k+1}^{k+1}$ we get the vectors $w_k^{k+1}$ and $w_{k+1}^{k+1}$. Thus, after $1+(3k-6)+2=3(k+1)-6$ steps we get required vectors $w_1^{k+1},w_2^{k+1},\dots ,w_k^{k+1}$ and $w_{k+1}^{k+1}$.

Second method: We start with steps $A_1,\dots ,A_{n-2}$, continue with steps $B_1,\dots ,B_{n-2}$ and finally end with steps $C_1,\dots ,C_{n-2}$:

$$A_1:v_1^n+v_2^n\equiv s(1,2).$$ $$A_2:u(1,2)+v_3^n\equiv s(1,2,3).$$ $$A_{n-3}:u(1,2,\dots ,n-3)+v_{n-2}^n\equiv s(1,2,\dots ,n-2).$$ $$A_{n-2}:u(1,2,\dots ,n-2)+v_{n-1}^n\equiv s(1,2,\dots ,n-1)=u_n^n.$$

$$B_1:v_n+v_{n-1}^n\equiv t(n-1,n).$$ $$B_2:t(n-1,n)+v_{n-2}^n\equiv t(n-2,n-1,n).$$ $$B_{n-3}:t(4,\dots ,n-1,n)+v_3^n\equiv t(3,4,\dots ,n).$$ $$B_{n-2}:t(3,\dots ,n-1,n)+v_2^n\equiv t(2,3,\dots ,n)=u_1^n.$$

$$C_1:v_1^n+t(3,\dots ,n-1,n)=u_2^n.$$ $$C_2:s(1,2)+t(4,\dots ,n-1,n)=u_3^n.$$ $$C_{n-2}:s(1,2,\dots ,n-2)+v_n^n=u_{n-1}^n.$$ Thus, by applying $(n-2)+(n-2)+(n-2)=3n-6$ steps we obtain the vectors $u_1^n,u_2^n,\dots ,u_n^n$.

Now we show that at least $3n-6$ are necessary. For $n\ge 3$, let $f(n)$ be the minimal possible number of steps. By induction we will show that $f(n)\ge 3n-6$. If $n=3$ then it can be readily shown that $f(3)\ge 3$. Suppose that for $n=k$ we have $f(k)\ge 3k-6$. Let us go over steps made for $n=k+1$. Let A be the step when the vector $v_{k+1}^{k+1}$ was used for the first time. In this step the vector $v_{k+1}^{k+1}$ was added to a vector $r(m)$ such that for some $1\le m\le k$ $m$th coordinate of $r(m)$ is non-zero. In order to get the vector $u_m^{k+1}$ whose only $0$ coordinate is $m$th coordinate, the vector $v_{k+1}^{k+1}$ will be used at least once more. Let B be one of these steps. Let C be step when the vector $u_m^{k+1}$ whose only $0$ coordinate is $k+1$st coordinate is obtained. In the sequence of steps made for $n=k+1$ by removing steps A, B, C and erasing $k+1$st coordinates of all vectors we can get all required vectors for $n=k$. Therefore, $f(k+1)-3\ge f(k)\ge 3k-6$ and hence $f(k+1)\ge 3(k+1)-6$. We are done.