Maths Olympiad Prep

Library / /91 of 105

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Suppose that S1,S2,S3,S_{1}, S_{2}, S_{3}, \ldots are sets of integers such that no integer is contained in more than one SnS_{n}; every SnS_{n} has exactly two elements; and the sum of the elements of SnS_{n} is nn. Prove that there exist infinitely many values of nn with the following property: one of the elements of SnS_{n} is greater than 13n/713 n / 7.

Solution

Solution:

Consider any set SS representable as the union of nn disjoint pairs of integers such that, if any negative number m-m is in SS, then the other element of its pair (henceforth called its "partner") is 13m/6\geq 13 m / 6. Any such SS will be called "plausible" of order nn. We will work with plausible sets (and their partner decompositions) in general; later, we will show how these are relevant to the original problem.
Let SS be plausible of order nn. Then it consists of nn disjoint pairs, each of which has a nonnegative sum. Hence, the sum of the elements of SS is a nonnegative integer. Now, if we consider the set of all possible values for the sum of SS, this set consists of nonnegative integers, and it is nonempty (since at least one plausible set exists). Hence, it has a minimal element. So we can meaningfully attempt to characterize a plausible set SS (of order nn) with minimal sum.
This set consists of some negative numbers m1,m2,,mk-m_{1},-m_{2}, \ldots,-m_{k}, their (positive) partners, and 2(nk)2(n-k) other nonnegative numbers, all distinct. Clearly, for any fixed choice of the mim_{i} and their partners, the sum is minimized by choosing the extra numbers to be the 2(nk)2(n-k) smallest nonnegative integers not equal to the partner of any mi-m_{i}, so we may assume the set to be of this form. Now define f(m)=13m/6f(m)=\lceil 13 m / 6\rceil for any integer mm. We claim it is no loss to assume the partner of mi-m_{i} is f(mi)f\left(m_{i}\right) for each ii. Indeed, if not, then this partner is p>f(mi)p>f\left(m_{i}\right). If f(mi)Sf\left(m_{i}\right) \notin S, then replacing pp by f(mi)f\left(m_{i}\right) gives us a new plausible set with smaller sum than before, contradicting minimality. So f(mi)Sf\left(m_{i}\right) \in S. But then f(mi)f\left(m_{i}\right) has some partner qq. We claim we can switch partnerships, matching mi-m_{i} with f(mi)f\left(m_{i}\right) and pp with qq, so that our partnership decomposition remains plausible. Indeed, if q0q \geq 0, this is clear. If q<0q<0 then q=q= some mjf(mi)f(mj)-m_{j} \Rightarrow f\left(m_{i}\right) \geq f\left(m_{j}\right) since f(mi)f\left(m_{i}\right) is the partner of mj-m_{j}, but p>f(mi)f(mj)p>f\left(m_{i}\right) \geq f\left(m_{j}\right), so we are again safe. Moreover, in either case, neither of the pairs involved is initially of the form ml,f(ml)-m_{l}, f\left(m_{l}\right) (in the case q=mjq=-m_{j}, we cannot have f(mi)=f(mj)f\left(m_{i}\right)=f\left(m_{j}\right) because ff is injective), and after the switch, one of them is of this form, so the total number of such pairs strictly increases. So we can perform this switch as many times as necessary, and eventually, we have each mi-m_{i} partnered with f(mi)f\left(m_{i}\right).
Next, we claim that, in the context of the partnering result obtained in the previous paragraph, jS-j \in S implies iS-i \in S for 0<i<j0<i<j. Indeed, suppose a counterexample exists. If f(i)Sf(i) \notin S, then we can replace j-j and its partner by i-i and f(i)f(i) to obtain a new plausible set SS whose sum has been changed by i+f(i)+jf(j)=7i/67j/6<0\leq-i+f(i)+j-f(j)=\lceil 7 i / 6\rceil-\lceil 7 j / 6\rceil<0, contradicting minimality. So we do have f(i)Sf(i) \in S. It cannot be partnered with a negative number, since this number would have to be i-i (by injectivity of f)f) but iS-i \notin S; so it is partnered with some positive number. Then, changing this number to i-i would again give us a new plausible set with strictly smaller sum, contradiction. This proves the claim.
But this claim shows that the negative elements of SS must be exactly 1,2,,k-1,-2, \ldots,-k, and now we are in a position to estimate the sum of SS. SS consists of these negative elements, their partners f(1),,f(k)f(1), \ldots, f(k), and 2(nk)2(n-k) other, distinct "leftover" nonnegatives which are as small as possible. Let aa be the largest leftover, so 0,,a0, \ldots, a are all in SS. We claim b=6a/13kb=\lfloor 6 a / 13\rfloor \leq k; if not, then bS-b \notin S but f(b)af(b) \leq a is in SS, so it is a leftover (because if its partner is c-c, injectivity implies c=bc=b, impossible), and replacing its nonnegative partner by b-b gives a new plausible set with smaller sum, contradiction. So kbk \geq b, and it follows that fully bb of the numbers 0,,a0, \ldots, a are partners of negative numbers. Hence, the number of leftovers can be counted in two ways: a+1b=2(nk)a+1-b=2(n-k). But b6a/1312(nk)a6a/13+2=7a/13+2a26(nk1)/7b \geq 6 a / 13-1 \Rightarrow 2(n-k) \leq a-6 a / 13+2=7 a / 13+2 \Rightarrow a \geq 26(n-k-1) / 7. Now, the elements of SS consist of k,,1,0,,a-k, \ldots,-1,0, \ldots, a, and the partners of k,,(b+1)-k, \ldots,-(b+1). So the sum of these numbers is
a(a+1)2k(k+1)2+i=b+1k13i/6a(a+1)2k(k+1)2+136(k(k+1)2b(b+1)2); \frac{a(a+1)}{2}-\frac{k(k+1)}{2}+\sum_{i=b+1}^{k}\lceil 13 i / 6\rceil \geq \frac{a(a+1)}{2}-\frac{k(k+1)}{2}+\frac{13}{6}\left(\frac{k(k+1)}{2}-\frac{b(b+1)}{2}\right) ;
using the (rather crude) estimates 0a,b,k2n0 \leq a, b, k \leq 2 n and b6a/13b \leq 6 a / 13 to simplify our calculations, this is
a22k22+13k21213b2124na22+7k21213(6a/13)2124n=7a226+7k2124n26(nk1)27+7k2124n26(nk)278n+7k2124n=361k28452nk7+26n2712n \begin{gathered} \geq \frac{a^{2}}{2}-\frac{k^{2}}{2}+\frac{13 k^{2}}{12}-\frac{13 b^{2}}{12}-4 n \geq \frac{a^{2}}{2}+\frac{7 k^{2}}{12}-\frac{13(6 a / 13)^{2}}{12}-4 n=\frac{7 a^{2}}{26}+\frac{7 k^{2}}{12}-4 n \\ \geq \frac{26(n-k-1)^{2}}{7}+\frac{7 k^{2}}{12}-4 n \geq \frac{26(n-k)^{2}}{7}-8 n+\frac{7 k^{2}}{12}-4 n=\frac{361 k^{2}}{84}-\frac{52 n k}{7}+\frac{26 n^{2}}{7}-12 n \end{gathered}
=36184(k312n361)2+12742527n212nαn212n =\frac{361}{84}\left(k-\frac{312 n}{361}\right)^{2}+\frac{1274}{2527} n^{2}-12 n \geq \alpha n^{2}-12 n
where α=1274/2527>1/2\alpha=1274 / 2527>1 / 2. So we now know that any plausible set of order nn has sum αn212n\geq \alpha n^{2}-12 n.
Now let us return to the original problem statement. Suppose that the statement is false; we seek a contradiction. Let i1<i2<<ici_{1}<i_{2}<\cdots<i_{c} be the (finitely many) values of ii for which SiS_{i} has an element >13i/7>13 i / 7, and let d=i1+i2++icd=i_{1}+i_{2}+\cdots+i_{c}. Now suppose ii is not equal to any of i1,,ici_{1}, \ldots, i_{c}, and suppose mSi(m>0)-m \in S_{i}(m>0). Then the other element of SiS_{i} is i+mi+m, and we have i+mi+m \leq 13i/7m6i/7i+m13m/613 i / 7 \Rightarrow m \leq 6 i / 7 \Rightarrow i+m \geq 13 m / 6. Consequently, if we take any n>iccn>i_{c}-c, we see that the set S=(S1S2Sn+c)(Si1Si2Sic)S=\left(S_{1} \cup S_{2} \cup \cdots \cup S_{n+c}\right)-\left(S_{i_{1}} \cup S_{i_{2}} \cup \cdots \cup S_{i_{c}}\right) is plausible of order nn. So the sum of its elements is αn212n\geq \alpha n^{2}-12 n. However, this sum should also equal
(1+2++(n+c))(i1+i2++ic)=(n+c)(n+c+1)/2d (1+2+\cdots+(n+c))-\left(i_{1}+i_{2}+\cdots+i_{c}\right)=(n+c)(n+c+1) / 2-d
This is a quadratic function of nn with leading coefficient 1/21 / 2, so it will actually be less than αn212n\alpha n^{2}-12 n when nn is sufficiently large. This is our contradiction.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.