2

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

Hamid Reza Ebrahimi
  • 3,445
  • 13
  • 41

1 Answers1

2

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.

JimmyK4542
  • 54,331