2
$\begingroup$

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.

  • 1
    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.2012-09-06

2 Answers 2

4

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

  • 0
    @Iuli: It should indeed; thanks for catching that.2012-09-06
3

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?