Determine whether or not there exist two different sets $A,B$, each consisting of at most $2011^2$ positive integers, such that every $x$ with $0 < x < 1$ satisfies the following inequality: \[\left| \sum_{a \in A} x^a - \sum_{b \in B} x^b \right| < (1-x)^{2011}.\]
Problem
Source: USA TST 2011 P9
Tags: inequalities, vector, pigeonhole principle, algebra unsolved, algebra
Rust
27.07.2011 08:42
Let $A=\{n+c|s_2(n) - \ even, n< 2^k\}, \ B=\{n+c|s_2(n) - \ odd, n< 2^k\}$, were $s_2(n)$ is summ of (binary) digites in base 2. Then \[\sum_{a\in A}x^a-\sum_{b\in B}x^b=x^c\prod_{m=0}^{k-1}(1-x^{2^m})<(1-x)^{2011}\] for big c,k.
dnkywin
29.07.2011 21:25
Rust wrote: Let $A=\{n+c|s_2(n) - \ even, n< 2^k\}, \ B=\{n+c|s_2(n) - \ odd, n< 2^k\}$, were $s_2(n)$ is summ of (binary) digites in base 2. Then \[\sum_{a\in A}x^a-\sum_{b\in B}x^b=x^c\prod_{m=0}^{k-1}(1-x^{2^m})<(1-x)^{2011}\] for big c,k. I don't see exactly how this helps with the problem... the minimum $k$ for which there exists a $c$ such that $x^c\prod_{m=0}^{k-1}(1-x^{2^m})<(1-x)^{2011}$ is 2011, which gives $|A|=|B|=2^{2010}>2011^2$. Here is the solution that I came up with during the actual contest:
Such a pair of sets does exist.
Consider $2011^2$-element subsets of $\{1,2,\ldots,k\}$, where $k>1$ is an integer we will define later.
For each such subset $A$ consider the 2012-element vector
\[v_A=(S_{A,0},S_{A,2},S_{A,3},\ldots,S_{A,2011})\]
where $S_{A,i}=\displaystyle\sum_{a\in A} \binom{a}{i}$.I claim for large enough $k$, there exist distinct $2011^2$-element subsets $A',B'$ of $\{1,2,\ldots,k\}$ such that $v_{A'}=v_{B'}$.
Note that for $0\le i\le 2011$,
\[0\le S_{A,i}\le 2011^2\binom{k}{i}\le Ck^{i}-1\]
where $C=1000000000$. Thus there are at most
\[\prod_{i=0}^{2011}Ck^i=C^{2012}k^{(2011)(2012)/2}\]
possibilities for the vector $v_A$. However, for large enough $k$, $\binom k {2011^2} > C^{2012}k^{(2011)(2012)/2}$, so by the Pigeonhole principle, there exist distinct $2011^2$-element subsets $A',B'$ of $\{1,2,\ldots,k\}$ such that $v_{A'}=v_{B'}$.
Now consider $P(x)=\displaystyle \sum_{a\in A'}x^{a}-\sum_{b\in B'}x^{b}$. Since $P^{(n)}(1)=S_{A',n}-S_{B',n}=0$ for $0\le n\le 2011$, $P(x)$ is divisible by $(1-x)^{2012}$. Thus there exists a real number $r<1$ such that $\vert P(x)\vert<(1-x)^{2011}$ for $r<x<1$.
Now, let $M=\max_{0<x<r}\vert\frac{P(x)}{(1-x)^{2011}}\vert$. If we take a positive integer $c$ such that $r^c<\frac1M$, then it is not hard to see that for $0<x<r$, $\vert x^cP(x)\vert<\vert x^cM(1-x)^{2011}\vert<(1-x)^{2011}$, and for $r<x<1$, $\vert x^cP(x)\vert<\vert P(x)\vert<(1-x)^{2011}$.
Now let $A=\{a+c|a\in A'\}$, $B=\{b+c|b\in B'\}$. Then
\[|\sum_{a\in A}x^{a}-\sum_{b\in B}x^{b}|=|x^cP(x)|<(1-x)^{2011}\]
for all $0<x<1$. Thus we have found sets $A,B$ that satisfy the given condition, which completes the proof.
My sources tell me this problem is by Gabriel Carroll?
Mop2018
02.05.2020 18:45
I solved it with 2 steps first step-use the pigieonhole principle to find two subsets A and B which The left hand is a multiple of The right side.(The number of element at A and should be smaller then 2011^2/2 such as B second step-try to make the inequality correct by using AM-GM and mixing A,B(times x^l for large enough l)
Aryan-23
09.07.2020 14:12
Solved with BOBTHEGR8 , MathPassionForever and biomathematics . We claim that such sets A and B do exist . Let $P(x) \stackrel {\text {def}}{:=} \text {LHS}$ . Note that if for some sets $A$ and $B$ , $P(x)$ takes the form $(1-X)^{2011+M}x^P$ ,where $M,P$ are large integers , then we are done . Taking the derivative of such a $P(x)$ 2011 times ,we note that $P^{(i)}(1)=0$ $\forall 1\leq i\leq 2011$ . In other words we need sets $A$ and $B$ such that we have $$\sum_{a\in A} \binom {a}{i}=\sum_{b\in B} \binom {b}{i} \forall 1 \leq i\leq 2011$$ To do this we consider a large natural number $N$ and bound the number of distinct values taken by $\sum_{i=0}^{j}\binom {a_i}{k}$ where $a_i \in \{1,2, \dots N\}$ and $j \leq 2011^2$ and $1\leq k \leq 2011$ . This is easy ; simply note that $$ \sum_{i=0}^{j}\binom {a_i}{k} \leq 2011^2 \binom Nk $$for a fixed $1\leq k \leq 2011$ So the number of such distinct values is atmost $$2011^{4022} \prod_{k=1}^{2011} \binom Nk$$ Also the total distinct number of $2011^2$ element subsets of $\{1,2, \dots N\}$ are $\binom {N}{2011^2}$ . For very large $N$ we have, $$\binom {N}{2011^2} > 2011^{4022} \prod_{k=1}^{2011} \binom Nk$$ So we are done by PHP $\blacksquare$
CANBANKAN
17.06.2022 06:25
We want $x^{2011+5} \mid P(1-x)$, or $(1-x)^{2011+5}\mid P(x)$. Matching coefficients, for all $0\le k\le 2014$, $\sum\limits_{a\in A} \binom ak = \sum\limits_{b\in B} \binom bk$. We can induct on $k$ to see $$\sum\limits_{a\in A} a^k = \sum\limits_{b\in B} b^k$$for all $0\le k\le 2014$.
Let $K=2011$. If $(1-x)^{K+5} x^{NK} \mid P(x)$, for a sufficiently large $N$, $|P(x)| < (1-x)^{K+1} $ for all $0<x<1$, because that polynomial has bounded coefficients.
Let $f(j,A)=\sum\limits_{a\in A} a^j$. We wish to find two sets $A,B$ with $|A|=|B|=K^2$, $A,B\subset \{1,\cdots,M\}$ such that $$\left( f(1,A), \cdots, f(K+5,A) \right) = \left( f(1,B), \cdots, f(K+5,B) \right)$$
On one hand, there are $K^2M^t$ possibilities for the value of $f(t,A)$. Therefore, there are at most $K^{2K+10} M^{\frac{(K+5)(K+4)}{2}}$ tuples.
On the other hand, there are $\binom{M}{K^2}$ possible sets. For some constant $C>\frac{1}{2 (k^2)!}$, $\binom{M}{K^2} > CM^{K^2}$. Setting $M=K^{K^K}$ suggests the tuples aren't injective. Taking $A,B$ such that they match satisfies the criteria in the problem.
It's clear that $(1-x)^{2011} \mid P(x)$, for otherwise, let $P(1-x)=cx^k+F(x)x^{k+1}$ for some polynomial $F(x)$. If $k<2011$, then for sufficiently small $x$, $|cx^k| > |F(x)x^{k+1}|+x^{2011}$, so the inequality doesn't hold.
Now, we've rewritten the problem into something more tractible. One viable approach to deal with existence is to use not have an explicit/inductive construction, but use size/counting approaches to show that this thing must exist. See GAMO P6 and Click to reveal hidden textIMO 21/6 for another example of the same technique.
HamstPan38825
14.09.2022 19:38
From AMSP Combinatorics 3: Key Lemma. We can find find two different sets $A, B$ of positive integers such that $|A| = |B| \leq 2011^2$ $\sum_{a \in A} a^i = \sum_{b \in B} b^i$ for all $1 \leq i \leq 2011$? Proof. Suppose that $A \subset \{1, 2, 3, \cdots, N\}$ for some large $N$ which we will pick later. WLOG we can suppose $A$ has $d=2011^2$ elements, so there are ${N \choose d}$ choices for $A$. Note that $${N \choose d} \approx \frac{N^{2011^2}}{d!} \approx N^{2011^2}$$for $N$ large. Synthesize a 2011-tuple $$t_A = \left(\sum_{a \in A} a, \sum_{a \in A} a^2, \cdots, \sum_{a \in A} a^{2011}\right).$$It suffices to show that there are less than ${N \choose d}$ outputs $t_S$ for some set $S$ and sufficiently large $N$. Obviously $$1 \leq \sum_{a \in A} a^i \leq N^i d$$for every $1 \leq i \leq 2011$; thus, there are a total number of tuples bounded above by $N^{\frac 12 \cdot 2011 \cdot 2010} d^{2011}$. For $N$ extremely large, this is less than $N^{2011^2}$, as required. $\blacksquare$ Let $k=2011$. Claim. The conditions in the problem are equivalent to the existence of two sets $A, B$ such that $$\sum_{a \in A} a^i = \sum_{b \in B} b^i$$for all $0 \leq i \leq k$. Proof. Translate all elements of $A$ and $B$, which we have shown exist by the previous problem, by some large integer $c$. Let $P(x)$ be the polynomial on the LHS; because we earlier calculated that $P^{'^i} (1) = 0$ for all $0 \leq i \leq k-1$, we must have $$P(x) = (x-1)^k Q(x).$$So it suffices to show that $$|x^c(1-x)Q(x)| < 1$$for any given polynomial $Q$ and some large $c$. Notice that AM-GM implies $$x^c(1-x) \leq \frac{c^c}{(c+1)^{c+1}} < \frac 1c.$$Thus, we just need to choose $c$ such that $$\frac 1c|Q(x)| < 1 \ \forall x \in (0, 1).$$For $c$ large enough, a construction must exist. $\blacksquare$