Solution APMO 2017 (Problem 5)

Problem 5.

 

Let n be a positive integer. A pair of n-tuples (a_1,...,a_n)\text{ and }(b_1,...,b_n) with integer entries is called an exquisite pair if

Also Read:

\left |a_1b_1+...+a_nb_n\right |\leq 1.

Determine the maximum number of distinct n-tuples with integer entries such that any two of them form an exquisite pair.

Answer: The maximum is n^2+n+1

Solution. First, we construct an example with n^2+n+1 n-tuples, each two of them forming an exquisite pair. In the following list, ∗ represents any number of zeros as long as the total number of entries is n.

• (∗)

• (∗, 1, ∗)

• (∗, −1, ∗)

• (∗, 1, ∗, 1, ∗)

• (∗, 1, ∗, −1, ∗)

For example, for n = 2 we have the tuples (0, 0), (0, 1), (1, 0), (0, −1), (−1, 0), (1, 1), (1, −1). The total number of such tuples is 1+n+n+\begin{pmatrix}n\\2\end{pmatrix}+\begin{pmatrix}n\\2\end{pmatrix}=n^2+n+1. For any two of them,

2 2

at most two of the products a_ib_i are non-zero. The only case in which two of them are non-zero

is when we take a sequence (∗, 1, ∗, 1, ∗) and a sequence (∗, 1, ∗, −1, ∗) with zero entries in the

same places. But in this case one ai bi is 1 and the other −1. This shows that any two of these

sequences form an exquisite pair.

Next, we claim that among any n^2+n+2 tuples, some two of them do not form an exquisite pair. We begin with lemma.

Lemma. Given 2n + 1 distinct non-zero n-tuples of real numbers, some two of them

(a_1,a_2,...,a_n)\text{ and }(b_1,...,b_n)\text{ satisfy }a_1b_1+....+a_nb_n>0.

Proof of Lemma. We proceed by induction. The statement is easy for n = 1 since for every

three non-zero numbers there are two of them with the same sign. Assume that the statement is true for n − 1 and consider 2n + 1 tuples with n entries. Since we are working with tuples of real numbers, we claim that we may assume that one of the tuples is a = (0, 0, . … , 0, −1). Let us postpone the proof of this claim for the moment.

If one of the remaining tuples b has a negative last entry, then a and b satisfy the desired condition. So we may assume all the remaining tuples has a non-negative last entry. Now, from each tuple remove the last number. If two n-tuples b and c yield the same (n − 1)-tuple, then

b_1c_1+...+b_{n-1}c_{n-1}+b_nc_n=b_1+....+b_{n-1}+b_nc_n>0

and we are done. The remaining case is that all the n-tuples yield distinct (n − 1)-tuples. Then at most one of them is the zero (n − 1)-tuple, and thus we can use the inductive hypothesis on

2n − 1 of them. So we find b and c for which

(b_1c_1+...+b{n-1}c_{n-1})+b_nc_n>0+b_nc_n>0

The only thing that we are left to prove is that in the inductive step we may assume that one of the tuples is a = (0, 0, . . . , 0, −1). Fix one of the tuples x=(x_1,...,x_n). Set a real number \phi for which \tan \phi=\frac{x_1}{x_2} . Change each tuple a=(a_1,a_2,...,a_n) (including x), to the tuple

(a_1\cos \phi-a_2\sin \phi,a_1\sin \phi+a_2\cos \phi,a_3,a_4,...,a_n)

A straightforward calculation shows that the first coordinate of the tuple x becomes 0, and that all the expressions of the form a_1b_1+...+a_nb_n are preserved. We may iterate this process until all the entries of x except for the last one are equal to 0. We finish by multiplying all the entries in all the tuples by a suitable constant that makes the last entry of x equal to −1. This preserves the sign of all the expressions of the form a_1b_1+....+a_nb_n.

 

We proceed to the proof of our claim. Let A be a set of non-zero tuples among which any two form an exquisite pair. It suffices to prove that |A|\leq n^2+n. We can write A as a disjoint union of subsets A_1\cup A_2\cup ...\cup A_n , where A_i is the set of tuples in A whose last non-zero entry appears in the ith position. We will show that |A_i|\leq 2i, which will finish our proof since

2+4+...+2n=n^2+n.

Proceeding by contradiction, suppose that |A_i|\geq 2i+1. If Ai has three or more tuples

whose only non-zero entry is in the ith position, then for two of them this entry has the same

sign. Since the tuples are different and their entries are integers, this yields two tuples for which |a_ib_i|\geq 2, a contradiction. So there are at most two such tuples. We remove them from A_i.

Now, for each of the remaining tuples a, if it has a positive ith coordinate, we keep a as it is. If it has a negative ith coordinate, we replace it with the opposite tuple −a with entries

with opposite signs. This does not changes the exquisite pairs condition.

After making the necessary changes, we have two cases. The first case is that there are two tuples a and b that have the same first i − 1 coordinates and thus

a_1b_1+...+a_{i-1}b_{i-1}>0

and thus is at least 1 (the entries are integers). The second case is that no two tuples have the same first i − 1 coordinates, but then by the Lemma we find two tuples a and b for which

a_1b_1+...+a_{i-1}b_{i-1}\geq 1

In any case, we obtain

a_1b_1+...+a_{i-1}b_{i-1}+a_ib_i\geq 2

This yields a final contradiction to the exquisite pair hypothesis.

×

Like us on Facebook

%d bloggers like this: