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 4 of 5: Split any exquisite family by last nonzero position

Previous step Next step

A=A_1\cup\cdots\cup A_n,\quad A_i=\{\text{tuples whose last nonzero entry is at position } i\},\quad |A_i|\le2i

Detailed analysis

Let $A$ be a set of nonzero tuples among which any two are exquisite. Write $A=A_1\cup A_2\cup\cdots\cup A_n$ , where $A_i$ is the set of tuples in $A$ whose last nonzero entry appears in position $i$ . It suffices to show $|A_i|\le2i$ for every $i$ , since $2+4+\cdots+2n=n^2+n$ , so together with the zero tuple this bounds $|A|+1\le n^2+n+1$ .