Problem 5

Let

n

be a positive integer. A pair of

n

-tuples

(a_1,\ldots,a_n)

and

(b_1,\ldots,b_n)

with integer entries is called an exquisite pair if

|a_1b_1+\cdots+a_nb_n|\le1

. Determine the maximum number of distinct

n

-tuples with integer entries such that any two of them form an exquisite pair.

Step 3 of 5: A positivity lemma by induction

Previous step Next step

\text{Lemma: among } 2n+1 \text{ nonzero real } n\text{-tuples, some two have } a_1b_1+\cdots+a_nb_n>0

Detailed analysis

Lemma: given $2n+1$ distinct nonzero $n$ -tuples of real numbers, some two of them $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ satisfy $a_1b_1+\cdots+a_nb_n>0$ . This is proved by induction on $n$ (trivial for $n=1$ , since among three nonzero reals two share a sign); for the inductive step, a rotation of coordinates reduces to the case where one tuple is $(0,\ldots,0,1)$ , and either some other tuple has negative last entry (done), or all remaining tuples have non-negative last entry and dropping that coordinate applies the inductive hypothesis to the $2n-1$ resulting $(n-1)$ -tuples (with care when two coincide).