Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Ross Millikan Sep 6 '12 at 21:03

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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