Let be a positive integer. A pair of -tuples with integer entries is called an exquisite pair if Determine the maximum number of distinct -tuples with integer entries such that any two of them form an exquisite pair.
Solution
The maximum is . First, we construct an example with -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 . ・ ・ - - - For example, for we have the tuples . 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 and a sequence with zero entries in the same places. But in this case one 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 distinct non-zero -tuples of real numbers, some two of them satisfy . Proof of Lemma. We proceed by induction. The statement is easy for since for every three non-zero numbers there are two of them with the same sign. Assume that the statement is true for and consider tuples with entries. Since we are working with tuples of real numbers, we claim that we may assume that one of the tuples is . Let us postpone the proof of this claim for the moment. If one of the remaining tuples has a negative last entry, then and 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 -tuples and yield the same -tuple, then and we are done. The remaining case is that all the -tuples yield distinct -tuples. Then at most one of them is the zero -tuple, and thus we can use the inductive hypothesis on of them. So we find and 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 . Fix one of the tuples . Set a real number for which x 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 |A| AA_{i}A whose last non-zero entry appears in the i, which will finish our proof since . Proceeding by contradiction, suppose that 2 i+1A_{i} has three or more tuples whose only non-zero entry is in the i, a contradiction. So there are at most two such tuples. We remove them from . Now, for each of the remaining tuples , if it has a positive th coordinate, we keep as it is. If it has a negative th coordinate, we replace it with the opposite tuple 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 and that have the same first 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 coordinates, but then by the Lemma we find two tuples and for which In any case, we obtain This yields a final contradiction to the exquisite pair hypothesis.