Maths Olympiad Prep

Library / /22 of 48

Algebra Difficulty 7.5 National olympiad, round 2 Find the answer

Let nn be a positive integer. A pair of nn-tuples \left(a_{1}, \ldots, a_{n}\right)and(b1,,bn) and \left(b_{1}, \ldots, b_{n}\right) with integer entries is called an exquisite pair if a1b1++anbn1\left|a_{1} b_{1}+\cdots+a_{n} b_{n}\right| \leq 1 Determine the maximum number of distinct nn-tuples with integer entries such that any two of them form an exquisite pair.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The maximum is n2+n+1n^{2}+n+1. First, we construct an example with n2+n+1nn^{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 nn. ・ ()(*)(,1,)(*, 1, *) - (,1,)(*,-1, *) - (,1,,1,)(*, 1, *, 1, *) - (,1,,1,)(*, 1, *,-1, *) For example, for n=2n=2 we have the tuples (0,0),(0,1),(1,0),(0,1),(1,0),(1,1),(1,1)(0,0),(0,1),(1,0),(0,-1),(-1,0),(1,1),(1,-1). The total number of such tuples is 1+n+n+(n2)+(n2)=n2+n+11+n+n+\binom{n}{2}+\binom{n}{2}=n^{2}+n+1. For any two of them, at most two of the products aibia_{i} b_{i} are non-zero. The only case in which two of them are non-zero is when we take a sequence (,1,,1,)(*, 1, *, 1, *) and a sequence (,1,,1,)(*, 1, *,-1, *) with zero entries in the same places. But in this case one aibia_{i} b_{i} is 1 and the other -1. This shows that any two of these sequences form an exquisite pair. Next, we claim that among any n2+n+2n^{2}+n+2 tuples, some two of them do not form an exquisite pair. We begin with lemma. Lemma. Given 2n+12 n+1 distinct non-zero nn-tuples of real numbers, some two of them \left(a_{1}, \ldots, a_{n}\right)and(b1,,bn) and \left(b_{1}, \ldots, b_{n}\right) satisfy a1b1++anbn>0a_{1} b_{1}+\cdots+a_{n} b_{n}>0. Proof of Lemma. We proceed by induction. The statement is easy for n=1n=1 since for every three non-zero numbers there are two of them with the same sign. Assume that the statement is true for n1n-1 and consider 2n+12 n+1 tuples with nn 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)a=(0,0, \ldots, 0,-1). Let us postpone the proof of this claim for the moment. If one of the remaining tuples bb has a negative last entry, then aa and bb 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 nn-tuples bb and cc yield the same (n1)(n-1)-tuple, then b1c1++bn1cn1+bncn=b12++bn12+bncn>0b_{1} c_{1}+\cdots+b_{n-1} c_{n-1}+b_{n} c_{n}=b_{1}^{2}+\cdots+b_{n-1}^{2}+b_{n} c_{n}>0 and we are done. The remaining case is that all the nn-tuples yield distinct (n1)(n-1)-tuples. Then at most one of them is the zero (n1)(n-1)-tuple, and thus we can use the inductive hypothesis on 2n12 n-1 of them. So we find bb and cc for which (b1c1++bn1cn1)+bncn>0+bncn>0\left(b_{1} c_{1}+\cdots+b_{n-1} c_{n-1}\right)+b_{n} c_{n}>0+b_{n} c_{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)a=(0,0, \ldots, 0,-1). Fix one of the tuples x=(x1,,xn)x=\left(x_{1}, \ldots, x_{n}\right). Set a real number \varphi for which \tan \varphi=\frac{x_{1}}{x_{2}}.Changeeachtuple. Change each tuple a=\left(a_{1}, a_{2}, \ldots, a_{n}\right)(including (including x),tothetuple ), to the tuple (a1cosφa2sinφ,a1sinφ+a2cosφ,a3,a4,,an)\left(a_{1} \cos \varphi-a_{2} \sin \varphi, a_{1} \sin \varphi+a_{2} \cos \varphi, a_{3}, a_{4}, \ldots, a_{n}\right)Astraightforwardcalculationshowsthatthefirstcoordinateofthetuple A straightforward calculation shows that the first coordinate of the tuple xbecomes0,andthatalltheexpressionsoftheform becomes 0, and that all the expressions of the form a_{1} b_{1}+\cdots+a_{n} b_{n}arepreserved.Wemayiteratethisprocessuntilalltheentriesof are preserved. We may iterate this process until all the entries of xexceptforthelastoneareequalto0.Wefinishbymultiplyingalltheentriesinallthetuplesbyasuitableconstantthatmakesthelastentryof 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 xequalto1.Thispreservesthesignofalltheexpressionsoftheform equal to -1. This preserves the sign of all the expressions of the form a_{1} b_{1}+\cdots+a_{n} b_{n}.Weproceedtotheproofofourclaim.Let. We proceed to the proof of our claim. Let Abeasetofnonzerotuplesamongwhichanytwoformanexquisitepair.Itsufficestoprovethat 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.Wecanwrite. We can write Aasadisjointunionofsubsets as a disjoint union of subsets A_{1} \cup A_{2} \cup \ldots \cup A_{n},where, where A_{i}isthesetoftuplesin is the set of tuples in Awhoselastnonzeroentryappearsinthe whose last non-zero entry appears in the ithposition.WewillshowthatAi2i th position. We will show that \left|A_{i}\right| \leq 2 i, which will finish our proof since 2+4++2n=n2+n2+4+\cdots+2 n=n^{2}+n. Proceeding by contradiction, suppose that \left|A_{i}\right| \geq 2 i+1.If. If A_{i}hasthreeormoretupleswhoseonlynonzeroentryisinthe has three or more tuples whose only non-zero entry is in the ithposition,thenfortwoofthemthisentryhasthesamesign.Sincethetuplesaredifferentandtheirentriesareintegers,thisyieldstwotuplesforwhichaibi2 th 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 \left|\sum a_{i} b_{i}\right| \geq 2, a contradiction. So there are at most two such tuples. We remove them from AiA_{i}. Now, for each of the remaining tuples aa, if it has a positive ii th coordinate, we keep aa as it is. If it has a negative ii th coordinate, we replace it with the opposite tuple a-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 aa and bb that have the same first i1i-1 coordinates and thus a1b1++ai1bi1=a12++ai12>0a_{1} b_{1}+\cdots+a_{i-1} b_{i-1}=a_{1}^{2}+\cdots+a_{i-1}^{2}>0 and thus is at least 1 (the entries are integers). The second case is that no two tuples have the same first i1i-1 coordinates, but then by the Lemma we find two tuples aa and bb for which a1b1++ai1bi11a_{1} b_{1}+\cdots+a_{i-1} b_{i-1} \geq 1 In any case, we obtain a1b1++ai1bi1+aibi2a_{1} b_{1}+\cdots+a_{i-1} b_{i-1}+a_{i} b_{i} \geq 2 This yields a final contradiction to the exquisite pair hypothesis.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.