Let $ n$ be positive integer, $ A,B\subseteq[0,n]$ are sets of integers satisfying $ \mid A\mid + \mid B\mid\ge n + 2.$ Prove that there exist $ a\in A, b\in B$ such that $ a + b$ is a power of $ 2.$
Problem
Source: Chinese TST 2007 4th quiz P3
Tags: function, induction, combinatorics proposed, combinatorics
cosinator
03.01.2009 19:33
First, we prove that there exists a bijective function $ f: [0,n]\to[0,n]$ such that $ f(f(t))=t$ and such that $ t+f(t)=2^k$ for nonnegative integer $ k$. Call such a function good. We prove there exists a good function by induction on $ n$. This is obviously true for $ n=1$. Then $ f(0)=1,f(1)=0$.
We are given the set $ [0,n]$ with $ 2^{a-1}\le n<2^a$. Assume there exists such a function for all $ m\le n-1$. Then we construct $ f$ for $ [0,n]$ as follows: For $ 2^{a}-n\le t\le n$, let $ f(t)=2^a-t$. By the inductive hypothesis, we are garunteed a good function $ g(t)$ for $ t< 2^a-n$ and so we let $ f(t)=g(t)$ for $ t<2^a-n$.
Now on to the main proof. We prove a more general statement that any set of integers $ S$ ($ |S|\ge1$) subject to a good function with $ A,B\subseteq S$ and with $ |A|+|B|\ge |S|+1$ there must exist $ a\in A,b\in B$ with $ a+b$ a power or $ 2$. We prove this by induction on $ |S|$. For $ |S|=1$ both $ A$ and $ B$ must equal $ S$ but since the unique element $ s\in S$ has the property that $ f(s)=s$, we have $ s+s$ is a power of 2.
Assume the claim holds for $ |S|\le n$. Suppose there exists a set $ S$ with $ |S|=n+1$ and $ A,B\subseteq S$ such that there do not exist $ a\in A,b\in B$ with $ a+b$ a power of $ 2$. We are given that $ |A|+|B|\ge n+2$. Since there are only $ n+1$ elements in $ S$, there exists an element in $ A\cap B$. Let this element be $ e_1$. Then $ f(e_1)$ cannot be in either $ A$ or $ B$. Thus, $ A,B\subseteq S/f(e_1)$. Consider $ A_1=A/e_1$ and $ B_1=B/e_1$. We have $ A_1,B_1\subseteq S/\{e_1,f(e_1)\}$. Obviously, $ e_1\ne f(e_1)$ and so $ |A_1|+|B_1|\ge n$ and $ |S/\{e_1,f(e_1)\}|=n-1$. By the inductive hypothesis on the set $ S/\{e_1,f(e_1)\}$ and the function $ f$, this is impossible. Contradiction!