CombinatoricsDifficulty 8.4ShortlistProve itUnited States
Determine whether or not there exist two different sets A, B, each consisting of at most 20112 positive integers, such that every x with 0<x<1 satisfies the following inequality: a∈A∑xa−b∈B∑xb<(1−x)2011.
Solution
The answer is yes. We will show that a pair of such sets exists. Rewrite the desired inequality as a∈A∑(1−y)a−b∈B∑(1−y)b<y2011(34) for every y such that 0<y<1.
Step 1: First, we show that there exist two different sets A′, B′ of 20112 positive integers each such that for k=0,1,2,…,2011, we have a∈A′∑(ka)=b∈B′∑(kb).(35) Let N be a large positive integer whose value will be determined later. For any subset S of {1,2,…,N} having 20112 elements, form the 2011-tuple c(S)=(s∈S∑(1s),s∈S∑(2s),…,s∈S∑(2011s)). The first element of c(S) is an integer between 1 and 20112N; the second lies between 1 and 20112N2, and so forth. Thus there are at most 20114022⋅N1+2+⋯+2011=20114022⋅N(22012) possible values that c(S) can take on. On the other hand, the number of possible sets S is (20112N), which is greater than 20114022⋅N(22012) when N is sufficiently large. Hence, by the pigeonhole principle, some two subsets A′ and B′ have c(A′)=c(B′). These are our sets A′ and B′ satisfying (35).
Step 2: Now consider expanding the binomials in the expression a∈A′∑(1−y)a−b∈B′∑(1−y)b. By (35), all the terms of degree less than or equal to 2011 cancel, meaning that all remaining terms have degree 2012 or higher. Let M be the sum of the absolute values of the coefficients of all the remaining terms. We thus have a∈A′∑(1−y)a−b∈B′∑(1−y)b≤My2012(36) for all y with 0<y<1.
Step 3: Finally, we claim that (1−y)M<My1(37) for all y. For example, this follows from the AM-GM inequality, via My(1−y)M≤M+1My+(1−y)+⋯+(1−y)MM+1=(M+1M)M+1<1.
Step 4: To finish, let A={a+M∣a∈A′} and B={b+M∣b∈B′}. Multiplying (36) and (37) gives (34) for this choice of A and B, 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.