# numbers of subsets for a set $A$ for which the equation $x+y=2n+1$ hasn't solutions.

Find the numbers of subsets for the set: $\displaystyle A= \{1,2,\ldots,2n\}$ for which the equation $\displaystyle x+y=2n+1$ has not solutions.

I have no idea. Thanks for your help.

-
For problems like this, if you have no better idea, do it by hand for $n=1$ and $n=2$. Often you get an idea how it works, then can generalize from there. –  Ross Millikan Sep 6 '12 at 21:03

Break the set $\{1,2,\dots,2n\}$ into the $n$ pairs $\{1,2n\},\{2,2n-1\},\dots,\{n,n+1\}$; any solution to $x+y=2n+1$ must have $\{x,y\}$ equal to one of these $n$ pairs. Thus, you’re looking for the subsets of $\{1,2,\dots,2n\}$ that contain at most one member of each pair. In how many ways can you do this? If you get stuck, mouse-over the spoiler protected bit below.

To form such a subset you must make a $3$-way choice for each pair: take neither member, take the smaller member, or take the larger member. Thus, the total number of such subsets is $3^n$.

-
I have a question, where you wrote $\{1,n\},\{2,n-1\}$ it should be $\{1,2n\},\{2,2n-1\}$, no ? –  Iuli Sep 6 '12 at 21:10
@Iuli: It should indeed; thanks for catching that. –  Brian M. Scott Sep 6 '12 at 21:19
Hint: divide the numbers in $A$ into pairs that sum to $2n+1$. How many pairs are there? How many elements of each pair can be in your subset?