An easy lower bound is $n^2+n+1$: Take all $n$-tuples with entries from $\{-1,0,+1\}$, for which at most two entries are non-zero, but ignore those with two non-zero entries where the first entry is $+1$.

To prove $n^2+n+1$ is an upper bound, we use induction on $n$. In the induction step, we need to show there are at most $2n$ vectors whose last coordinate is non-zero. Let us write such vectors as $v_i = (w_i, x_i)$ with $w_i \in \mathbb{Z}^{n-1}$ and $x_i \in \mathbb{Z} - \{0\}$. Easy to see there are at most two vectors with $w_i = 0$. It thus suffices to show there are at most $2n-2$ such vectors $v_i$ with $w_i \neq \vec{0}$. Note that we can replace each $v_i$ with $-{v_i}$ without changing the exquisite property. Thus we may without loss assume every $x_i$ is a positive integer. Hence, \[ w_i \cdot w_j = v_i \cdot v_j - x_i x_j \leq 1 - x_ix_j \leq 0. \]The problem now follows from the fairly well-known result that in $\mathbb{R}^{n-1}$, at most $2n-2$ vectors can be found whose pairwise inner product is non-positive. This latter result can again be proved by induction.

Answer: $n^2 + n + 1$. The construction (which is important motivation) consists of $1 + 2n + 2\binom n2$ vectors: The zero vector. The $2n$ vectors with one coordinate $\pm 1$ and the other coordinates equal to zero. For each $1 \le i < j \le n$, the two vectors with $1$ in the $i$th coordinate and $\pm 1$ in the $j$th coordinate, and zeros elsewhere. Note that in any working set, we may freely swap $v$ with $-v$. Now we prove this is optimal. We begin with the following lemma, (which was originally supposed to be an HMIC problem before it got sniped by APMO). Lemma: Suppose we have nonzero vectors in ${\mathbb R}^n$, no two which form an acute angle. Then there are at most $2n$ unit vectors. (This is sharp, since vectors we may take coordinate axes.) Proof. By induction with trivial base case. WLOG one of the vectors is $(-1, 0, 0, \dots, 0)$. Then all other vectors or else contained in the region $x_1 \ge 0$. So project onto the $x_1 = 0$ hyperplane, discarding $(\pm 1, 0, 0, \dots 0)$ if they exist, and induct down. $\blacksquare$ For the present problem, assume for contradiction we have $n^2 + n + 2$ vectors, and thus at least $n^2 - n + 1$ vectors with at least two nonzero components. By pigeonhole principle, some component is nonzero at least $\left\lceil \frac{2(n^2-n+1)}{n} \right\rceil = 2n - 1$ times, say the first one. Then, by swapping $v$ with $-v$, we obtain $2n-1$ vectors whose first coordinate is positive and with at least one more positive coordinate. But if we drop the first coordinate, this gives $2n-1$ vectors in ${\mathbb R}^{n-1}$, so the lemma implies that two of them have positive dot product, hence dot product at least one; adding back in the first coordinate gives a contradiction.

I have heard from my country's team leader that this problem is proposed by Pakawut Jiradilok, Thailand.

This was really difficult.

There are only three people who solved this One from Korea, one from Singapore One from USA

And the one from Korea is above lol

So that means this problem must be very hard. I can't even understand what $n$-tuple means.

angiland wrote: The problem now follows from the fairly well-known result that in $\mathbb{R}^{n-1}$, at most $2n-2$ vectors can be found whose pairwise inner product is non-positive. This latter result can again be proved by induction. Could you explain this part? Thank you.

Is the lemma stated by v enhance and angiland essentially required to solve the problem or is there any other " easy to come" way to solve this problem as it is hard to come up with these solutions.

I hang my head in despair Treat the $n$-tuples as $n$ vectors $v_1, v_2, \ldots, v_n$ in $n$-space (with integer components). Our answer is $n^2 + n + 1$. The construction is easy. Lemma: Given $2n+1$ nonzero vectors in $n$-space, some two of them have positive dot product. Proof: These vectors need not have integer or rational components. The base case of $n = 1$ is trivial. Now, for the inductive step, suppose it is true for some $n = k-1$. Then, suppose we have $2k+1$ vectors $v_1, \ldots , v_{2k+1}$ in $k$-space. Rotate so that $v_1$ becomes perpendicular to the plane $x_1 = 0$ and pointing positively. Then, since all other vectors form nonpositive dot products with $v_1$, they are "underneath" or on plane $x_1 = 0$; that is, in the region $x_1 \leq 0$. Project the remaining at least $2k$ vectors $v_i$ onto the plane to $v_i'$ - if one of them is $-v_1$, then remove it. All other remaining (at least $2k-1$) vectors are up for consideration. By the inductive hypothesis, two of them have negative dot product. Since the $x_1$ coordinates of them two are both nonpositive, their product is nonnegative, so those two in the original $k$-space do indeed have positive dot product. OK. Next, if we have $> n^2 + n + 1$ vectors, we have $> n^2 - n$ nonzero or non-onaxis vectors. There must be a coordinate with more than $2(n^2 - n)/n = 2n-2$ nonzero instances, say $\geq 2n-1$. Negate the necessary amount of these $2n-1$ vectors so that this coordinate $x_j$ all become positive. Projecting on to the $x_j$ plane, we have $2n-1$ vectors in $n-1$ space, and thus two of who have positive $\geq 1$ dot product. Since the $x_j$ components of them two are both positive, it again must be $\geq 1$ for some two vectors with $\geq 2$ dot product, which is bad. done

Answer is $n^2+n+1$ Construction is $(0, \ldots, 0), (0, \ldots, 0, 1, 0, \ldots, 0), (0, \ldots, 0, -1, 0, \ldots, 0), (0, \ldots, 0, 1, 0, \ldots, 0, 1, 0, \ldots, 0), (0, \ldots, 0, 1, 0, \ldots, 0, -1, 0, \ldots, 0)$. Proof is simple by induction: I claim there can be at most $2n$ examples with nonzero last coordinate. Assume otherwise. Group them by the signs of their coordinates being $+, 0, -$. The basis vector and its negative are free to leave, and for the rest we have that each and their negative cannot coexist and are equivalent so WLOG they all have positive last coordinate. This means we removing their last coordinate to greater than $2n - 2$ vectors in $\mathbb{R}^{n-1}$, they all have nonpositive dot product with one another. However simply project onto the unit sphere, and then pick a vector and perform a basis change on it to $(0, 0, 0, \ldots, 0, -1)$ on all of the vectors, then remove its antipode if it exists. At most $2$ vectors are removed. For every other vector, read its coordinates except the final one to yield a space of greater than $2(n-1) - 2$ vectors each with pairwise nonpositive dot product. Continue this induction to $n = 1$, where we must have at least three nonzero real numbers such that every pair has nonpositive dot product. This is impossible by pigeonhole on the signs of the real numbers, finishing. Thus the induction finishes as $1+(n-1)+(n-1)^2 + 2n = 1+n+n^2$ as desired.

What if we change the setting into n-dimension vector in a finite field with order of p (a prime), how will be the new conclusion look like? Does anyone have some guess or intuition?