Problem

Source: Chinese TST 2007 4th quiz P3

Tags: function, induction, combinatorics proposed, combinatorics



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.$