Prove that there exist $x,y$ so that $x+y=2^k$ if $X$ is the set of all natural(excluding $0$) numbers that are not a power of $2$ and are smaller than $1998$ and $A$ is a subset of $X$ with $997$ members Prove that there exist $x,y \in A$ so that $x+y$ is a power of $2$.The book considered $1$ a power of $2$ nad then solved it like below:
"Consider the following sets:
$\{51,1997\},\{52,1996\},\dots ,\{1023,1025\},\{1024\}$
$\{14,50\},\{15,49\},\dots ,\{31,33\},\{32\}$
$\{3,13\},\{4,12\},\{5,11\},\dots ,\{7,9\},\{8\},\{2\},\{1\}$
We have $1001$ sets by deleting powers of $2$,$5$ sets will be completely deleted(Here it assumes that $1$ is a power of $2$)So we will have $996$ sets that by choosing $997$ numbers we will have two numbers from the same set wich form a power of $2$."
Now I want to know if there exist a solution without considering $1$ as a power of $2$ or we should consider that?
 A: $1$ is a power of $2$, but we can alter the question to ask whether you can select $997$ numbers from $[1,1997]$ less $\{2,4,8,16,32,64,128,256,512,1024\}$ such that no pair of them sum to a power of $2$.  The proof given fails because you now have $997$ sets and may be able to select one number from each of them without having any pair sum to a power of $2$.  We can't be sure easily because we have to select $1$, so cannot select $3,7,15,\ldots 1023$.  Those force us to select $13,9,49,\ldots 1025$ and it could be that two of them sum to a power of $2$ or it could be that there are other constraints we cannot avoid.  We can explicitly show a list of $997$ numbers that meets the requirement.  It happens to consist of taking the higher number of each pair in the original construction plus $1$.  We choose all the numbers $1025$ through $1997$, which is $973$ of them, leaving $24$ more to choose.  We cannot take any number greater than $50$ or there will be a pair adding to $2048$ but we can take $33$ through $50$ for $18$ more.  Now we cannot take anything greater than $13$ because we would have a pair adding to $64$ but we can take $9$ through $13$.  That is a total of $996$ numbers and we add $1$ to the list.  We can see that no pair adds to a power of $2$ and are done.
A: I am unsure how to prove this question through combinatorics, but I can say this about your question.
Consider the set $Y$ of non-zero natural numbers that are less than $1998$, excluding the powers of two (but with $1 \in Y$). It should be clear that if $Y$ contains two elements of the form $(2^n - a), (2^n + a)$ then it contains two elements that sum to a power of two.
Now the largest power of two less that $1998$ is $2^{10} = 1024$ and note that $1997 - 1024 = 973$. This means that there are $973$ elements in $Y$ that we can write as $2^{10} + a$ for some non-zero natural number $a$ (where $1 \leq a \leq 973$). Then we can pair each of these numbers up with $2^{10} - a$ (where $1 \leq a \leq 973$) taking us down to the number $2^{10} - 973 = 51$.
Therefore if we pick $974$ elements of $Y$ that are greater than $50$, we will have to pick two elements that sum to a power of two.

So if $B$ is a subset of $Y$ with $|B| = 997$ such that for all $x,y \in B$ we have that $(x + y)$ is not a power of two - then $24$ of our elements must be from $\{1,...,50\}$ (otherwise at least $974$ of our elements will be greater than $50$).
Once again, the largest power of two less than $50$ is $2^5 = 32$. So we can write $18$ elements in the form $2^5 + a$, and $18$ elements in the form $2^5 - a$ (with $2^5 - 18 = 14$). Then we cannot make more than $18$ selections from $\{14,...,50\}$ otherwise once again we will pick two elements that sum to a power of two.
Then at least $6$ selections must be from the elements $\{1,...,13\}$.
Continuing this trend we find that the largest power of two in $\{1,...,13\}$ is $2^3 = 8$, giving us $5$ elements that we can write as $2^3 + a$ and $5$ elements that we can write as $2^3 - a$. So we cannot make more than $5$ selections from $\{3,...,13\}$.

In the case where $1$ IS considered a power of two, this give us a contradiction - as selecting from $\{1,...,13\}$ in $Y$ would be the same thing as selecting from $\{3,...,13\}$ (as $1 \not\in Y)$. Meaning that we have to make at least $6$ selections and no more than $5$ selections from the same set $\{3,...,13\}$. This proves the case already given.
However what you want is to treat $1$ as though it is NOT a power of two, and therefore we can keep going and find out that we have to make a single selection from $\{1\}$ - which we can do.
Following the procedure backwards, we can construct the set $B$ to be given by:


*

*$B = \{1,\color{blue}{2^3+1,...,2^3+5},\color{green}{2^5+1,...,2^5+18},\color{red}{2^{10}+1,...,2^{10}+973}\}$


This set is clearly a subset of $Y$ with $997$ members, and a simple argument can show that no pair of its elements sum to a power of two. (This proof also shows that $997$ is the largest subset that can exist with this property, when $1$ is not considered a power of two).
