International Mathematical Olympiad

We solve the problem for $n$-tuples for any $n⩾3$: we will show that the answer is $s=3$, regardless of the value of $n$.

First, let us briefly introduce some notation. For an $n$-tuple $\mathbf{v}$, we will write ${\mathbf{v}}_i$ for its $i$-th coordinate (where $1⩽i⩽n$). For a positive integer $n$ and a tuple $\mathbf{v}$ we will denote by $n\cdot \mathbf{v}$ the tuple obtained by applying addition on $\mathbf{v}$ with itself $n$ times. Furthermore, we denote by $\mathbf{e}(i)$ the tuple which has $i$-th coordinate equal to one and all the other coordinates equal to zero. We say that a tuple is positive if all its coordinates are positive, and negative if all its coordinates are negative.

We will show that three tuples suffice, and then that two tuples do not suffice.

Three tuples suffice. Write $\mathbf{c}$ for the constant-valued tuple $\mathbf{c}=(-1,\dots ,-1)$. We note that it is enough for Lucy to be able to make the tuples $\mathbf{e}(1),\dots ,\mathbf{e}(n),\mathbf{c}$; from those any other tuple $\mathbf{v}$ can be made as follows. First we choose some positive integer $k$ such that $k+{\mathbf{v}}_i>0$ for all $i$. Then, by adding a positive number of copies of $\mathbf{c},\mathbf{e}(1),\dots ,\mathbf{e}(n)$, she can make $$k\mathbf{c}+(k+{\mathbf{v}}_1)\cdot \mathbf{e}(1)+\cdots +(k+{\mathbf{v}}_n)\cdot \mathbf{e}(n)$$ which we claim is equal to $\mathbf{v}$. Indeed, this can be checked by comparing coordinates: the $i$-th coordinate of the right-hand side is $-k+(k+{\mathbf{v}}_i)={\mathbf{v}}_i$ as needed.

Lucy can take her three starting tuples to be $\mathbf{a},\mathbf{b}$ and $\mathbf{c}$, such that ${\mathbf{a}}_i=-i^2,{\mathbf{b}}_i=i$ and $\mathbf{c}=-1$ (as above).

For any $1⩽j⩽n$, write $\mathbf{d}(j)$ for the tuple $2\cdot \mathbf{a}+4j\cdot \mathbf{b}+(2j^2-1)\cdot \mathbf{c}$, which Lucy can make by adding together $\mathbf{a},\mathbf{b}$ and $\mathbf{c}$ repeatedly. This has $i$-th term $$\begin{array}{rl}\mathbf{d}(j{)}_i& =2{\mathbf{a}}_i+4j{\mathbf{b}}_i+(2j^2-1){\mathbf{c}}_i\\ & =-2i^2+4ij-(2j^2-1)\\ & =1-2(i-j{)}^2\end{array}$$ This is 1 if $j=i$, and at most -1 otherwise. Hence Lucy can produce the tuple $1=(1,\dots ,1)$ as $\mathbf{d}(1)\vee \cdots \vee \mathbf{d}(n)$.

She can then produce the constant tuple $0=(0,\dots ,0)$ as $1+\mathbf{c}$, and for any $1⩽j⩽n$ she can then produce the tuple $\mathbf{e}(j)$ as $\mathbf{d}(j)\vee 0$. Since she can now produce $\mathbf{e}(1),\dots ,\mathbf{e}(n)$ and already had $\mathbf{c}$, she can (as we argued earlier) produce any integer-valued tuple.

Two tuples do not suffice. We start with an observation: Let $a$ be a non-negative real number and suppose that two tuples $\mathbf{v}$ and $\mathbf{w}$ satisfy ${\mathbf{v}}_j⩾a{\mathbf{v}}_k$ and ${\mathbf{w}}_j⩾a{\mathbf{w}}_k$ for some $1⩽j,k⩽n$. Then we claim that the same inequality holds for $\mathbf{v}+\mathbf{w}$ and $\mathbf{v}\vee \mathbf{w}$: Indeed, the property for the sum is verified by an easy computation: $$(\mathbf{v}+\mathbf{w}{)}_j={\mathbf{v}}_j+{\mathbf{w}}_j⩾a{\mathbf{v}}_k+a{\mathbf{w}}_k=a(\mathbf{v}+\mathbf{w}{)}_k.$$ For the second operation, we denote by $\mathbf{m}$ the tuple $\mathbf{v}\vee \mathbf{w}$. Then ${\mathbf{m}}_j⩾{\mathbf{v}}_j⩾a{\mathbf{v}}_k$ and ${\mathbf{m}}_j⩾{\mathbf{w}}_j⩾a{\mathbf{w}}_k$. Since ${\mathbf{m}}_k={\mathbf{v}}_k$ or ${\mathbf{m}}_k={\mathbf{w}}_k$, the observation follows.

As a consequence of this observation we have that if all starting tuples satisfy such an inequality, then all generated tuples will also satisfy it, and so we would not be able to obtain every integer-valued tuple.

Let us now prove that Lucy needs at least three starting tuples. For contradiction, let us suppose that Lucy started with only two tuples $\mathbf{v}$ and $\mathbf{w}$. We are going to distinguish two cases. In the first case, suppose we can find a coordinate $i$ such that ${\mathbf{v}}_i,{\mathbf{w}}_i⩾0$. Both operations preserve the sign, thus we can not generate any tuple that has negative $i$-th coordinate. Similarly for ${\mathbf{v}}_i,{\mathbf{w}}_i⩽0$.

Suppose the opposite, i.e., for every $i$ we have either ${\mathbf{v}}_i>0>{\mathbf{w}}_i$, or ${\mathbf{v}}_i<0<{\mathbf{w}}_i$. Since we assumed that our tuples have at least three coordinates, by pigeonhole principle there exist two coordinates $j\ne k$ such that ${\mathbf{v}}_j$ has the same sign as ${\mathbf{v}}_k$ and ${\mathbf{w}}_j$ has the same sign as ${\mathbf{w}}_k$ (because there are only two possible combinations of signs).

Without loss of generality assume that ${\mathbf{v}}_j,{\mathbf{v}}_k>0$ and ${\mathbf{w}}_j,{\mathbf{w}}_k<0$. Let us denote the positive real number ${\mathbf{v}}_j/{\mathbf{v}}_k$ by $a$. If ${\mathbf{w}}_j/{\mathbf{w}}_k⩽a$, then both inequalities ${\mathbf{v}}_j⩾a{\mathbf{v}}_k$ and ${\mathbf{w}}_j⩾a{\mathbf{w}}_k$ are satisfied. On the other hand, if ${\mathbf{w}}_j/{\mathbf{w}}_k⩽a$, then both ${\mathbf{v}}_k⩾(1/a){\mathbf{v}}_j$ and ${\mathbf{w}}_k⩾(1/a){\mathbf{w}}_j$ are satisfied. In either case, we have found the desired inequality satisfied by both starting tuples, a contradiction with the observation above.