Maths Olympiad Prep

Library / /14 of 45

Combinatorics Difficulty 8.4 Shortlist Prove it United States

Determine whether or not there exist two different sets AA, BB, each consisting of at most 201122011^2 positive integers, such that every xx with 0<x<10 < x < 1 satisfies the following inequality:
aAxabBxb<(1x)2011. \left| \sum_{a \in A} x^a - \sum_{b \in B} x^b \right| < (1-x)^{2011}.

Solution

The answer is yes. We will show that a pair of such sets exists. Rewrite the desired inequality as
aA(1y)abB(1y)b<y2011(34) \left| \sum_{a \in A} (1-y)^a - \sum_{b \in B} (1-y)^b \right| < y^{2011} \quad (34)
for every yy such that 0<y<10 < y < 1.

Step 1: First, we show that there exist two different sets AA', BB' of 201122011^2 positive integers each such that for k=0,1,2,,2011k = 0, 1, 2, \dots, 2011, we have
aA(ak)=bB(bk).(35) \sum_{a \in A'} \binom{a}{k} = \sum_{b \in B'} \binom{b}{k}. \quad (35)
Let NN be a large positive integer whose value will be determined later. For any subset SS of {1,2,,N}\{1, 2, \dots, N\} having 201122011^2 elements, form the 2011-tuple
c(S)=(sS(s1),sS(s2),,sS(s2011)). c(S) = \left( \sum_{s \in S} \binom{s}{1}, \sum_{s \in S} \binom{s}{2}, \dots, \sum_{s \in S} \binom{s}{2011} \right).
The first element of c(S)c(S) is an integer between 11 and 20112N2011^2 N; the second lies between 11 and 20112N22011^2 N^2, and so forth. Thus there are at most
20114022N1+2++2011=20114022N(20122) 2011^{4022} \cdot N^{1+2+\dots+2011} = 2011^{4022} \cdot N^{\binom{2012}{2}}
possible values that c(S)c(S) can take on. On the other hand, the number of possible sets SS is (N20112)\binom{N}{2011^2}, which is greater than 20114022N(20122)2011^{4022} \cdot N^{\binom{2012}{2}} when NN is sufficiently large. Hence, by the pigeonhole principle, some two subsets AA' and BB' have c(A)=c(B)c(A') = c(B'). These are our sets AA' and BB' satisfying (35).

Step 2: Now consider expanding the binomials in the expression
aA(1y)abB(1y)b. \sum_{a \in A'} (1-y)^a - \sum_{b \in B'} (1-y)^b.
By (35), all the terms of degree less than or equal to 20112011 cancel, meaning that all remaining terms have degree 20122012 or higher. Let MM be the sum of the absolute values of the coefficients of all the remaining terms. We thus have
aA(1y)abB(1y)bMy2012(36) \left| \sum_{a \in A'} (1-y)^a - \sum_{b \in B'} (1-y)^b \right| \leq M y^{2012} \qquad (36)
for all yy with 0<y<10 < y < 1.

Step 3: Finally, we claim that
(1y)M<1My(37) (1 - y)^M < \frac{1}{My} \qquad (37)
for all yy. For example, this follows from the AM-GM inequality, via
My(1y)M(My+(1y)++(1y)MM+1)M+1=(MM+1)M+1<1. My(1-y)^M \leq \left( \frac{My + \overbrace{(1-y) + \dots + (1-y)}^{M}}{M+1} \right)^{M+1} = \left( \frac{M}{M+1} \right)^{M+1} < 1.

Step 4: To finish, let A={a+MaA}A = \{a + M \mid a \in A'\} and B={b+MbB}B = \{b + M \mid b \in B'\}. Multiplying (36) and (37) gives (34) for this choice of AA and BB, as required.

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.