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 5 of 5: Bound

|A_i|

by contradiction using the lemma

Previous step Next step

|A_i|\ge2i+1 \implies \exists\, a,b\in A_i:\ a_1b_1+\cdots+a_ib_i\ge2 \implies \text{contradiction}

Detailed analysis

Suppose $|A_i|\ge2i+1$ . At most two tuples in $A_i$ can have their only nonzero entry at position $i$ (three such would force two with the same sign there, giving $|a_ib_i|\ge2$ , violating exquisiteness); remove them, and negate any remaining tuple with a negative $i$ -th coordinate (this preserves exquisiteness). Among the remaining at least $2i-2$ tuples, either two share the same first $i-1$ coordinates (giving $a_1b_1+\cdots+a_{i-1}b_{i-1}\ge1$ ), or the lemma applied to their $(i-1)$ -tuple truncations gives two with $a_1b_1+\cdots+a_{i-1}b_{i-1}\ge1$ . Either way, adding the positive $i$ -th coordinate contribution $a_ib_i\ge1$ gives total dot product at least $2$ , contradicting the exquisite hypothesis. Hence $|A_i|\le2i$ , and summing over $i$ gives $|A|\le n^2+n$ , so the maximum number of pairwise exquisite tuples is $1+n^2+n=n^2+n+1$ , matching the construction.