Solution APMO 2017 (Problem 5)
Let n be a positive integer. A pair of n-tuples with integer entries is called an exquisite pair if
- Proving that we have to dissect R into at least (n + 1) smaller rectangles ( solution Problem 1 shortlist Problem IMO 2014 about Combinatorics )
- Solving segment problem in line and point ( Solution number 7 shortlist problem of combinatoric in IMO 2016)
- Solution problem 1 of Geometry Shortlist Problem in IMO 2015
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
Solution. First, we construct an example with 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 . For any two of them,
at most two of the products 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 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
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
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
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 . Set a real number for which . Change each tuple (including x), to the tuple
A straightforward calculation shows that the first coordinate of the tuple x becomes 0, and that all the expressions of the form 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 .
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 . We can write A as a disjoint union of subsets , where is the set of tuples in A whose last non-zero entry appears in the ith position. We will show that , which will finish our proof since
Proceeding by contradiction, suppose that . 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 contradiction. So there are at most two such tuples. We remove them from .
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
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
In any case, we obtain
This yields a final contradiction to the exquisite pair hypothesis.