2
$\begingroup$

$A$ is a subset of $\{0,1,2,...,1997\}$ with more than 1000 members.Using pigeon hole principle prove that either $A$ has a power of 2 or consists of two distinct members whose sum equals a power of 2.
Can you generalize your solution to the set $\{0,1,2,...,n\}$??

The main difficulty here is finding suitable holes and pigeons.We have 10 powers of 2 in the main set: $2,4,...,1024$.Does a partition like $\{1,2\},\{3,4\},...$ help? After all the sum of members of each of them certainly is not power of 2...

$\endgroup$
2
$\begingroup$

Like you've said, a partition like $\{1,2\}, \{3,4\},$ etc. doesn't help since the numbers in each pair don't add up to a power of two.

The key is to partition $\{0,1,\ldots,1997\}$ into singletons that are powers of two and pairs which add up to a power of two.

Start with $\{51,1997\}, \{52,1996\}, \{53,1995\}, \ldots, \{1022,1026\}, \{1023, 1025\}$ and $\{1024\}$.

This takes care of all the integers greater than or equal to $51$.

Next, lets group $\{14,50\}, \{15,49\}, \{16,48\}, \ldots, \{30,34\}, \{31,33\}$ and $\{32\}$.

This takes care of all the integers greater than or equal to $14$.

Finally, group $\{3,13\}, \{4,12\}, \{5,11\}, \{6,10\}, \{7,9\}$ and $\{8\}$ and $\{2\}$ and $\{0,1\}$.

So we have partitioned $\{0,\ldots,1997\}$ into the singletons $\{2\}, \{8\}, \{32\}, \{1024\}$ along with $\dfrac{1998-4}{2} = 997$ pairs of numbers which add up to a power of two.

If any of the numbers $2, 8, 32, 1024$ are in the subset $A$, we're done. Otherwise, $A$ contains more than $1000$ members from $\{0,\ldots,1997\} \setminus\{2,8,32,1024\}$, which we've partitioned into $997$ pairs.

I'll let you finish the pigeonhole argument from here.

$\endgroup$
  • $\begingroup$ What about other powers of 2 like 64,128,...? $\endgroup$ – Hamid Reza Ebrahimi Dec 16 '17 at 10:35
  • $\begingroup$ Those are included in the pairs $\{64,1984\}$, $\{128,1920\}$, $\{256,1792\}$, $\{512,1536\}$. $\endgroup$ – JimmyK4542 Dec 16 '17 at 10:38
  • $\begingroup$ How could you make sure all numbers in the main set are in your partition? Can you generalize your method? $\endgroup$ – Hamid Reza Ebrahimi Dec 16 '17 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.