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.

Given the set $\textbf{S}=\{\frac{1}{2},\frac{1}{4},\frac{1}{6},\frac{1}{8},\frac{1}{10},\frac{1}{12},\frac{1}{14}\}$, find a subset such that the sum of all the elements equals to 1

The answer to this question is relatively easy to obtain, however, I am not happy with my approach. Basically my question is, is there an analytical approach to solve this problem?

My approach:

$\frac{1}{2}$ must be an element of the subset since $\frac{1}{4}+\frac{1}{6}+\frac{1}{8}+\frac{1}{10}+\frac{1}{12}+\frac{1}{14}<1$. Using similar logic I also deduced that $\frac{1}{4}$ must be a member of the subset. However, after this, my approach was literally guesswork. I was lucky however and knew that $\frac{1}{6}+\frac{1}{12}=\frac{1}{4}$ which allowed me to solve the problem. However, the latter approach (the guesswork part) was only successful because the given set was small enough for a brute force approach and I was lucky to know $\frac{1}{6}+\frac{1}{12}=\frac{1}{4}$. If the set was bigger however, and lets say the sum of the elements of the subset had to be 99.5 instead of 1 it would take a lot longer to solve.

Is there a more rigorous way to solve this question?

share|improve this question
2  
2  
It really depends on what you mean by "this type of question", in general it is an NP-Complete problem. But if the numbers in the set have a certain form, for example $\{1/(2*n)\}$ then there might be a way to do it efficiently. –  aelguindy Feb 15 '12 at 13:09
    
For simplicities sake I'll limit the question to this particular problem only. –  E.O. Feb 15 '12 at 22:30
add comment

1 Answer

up vote 2 down vote accepted

According to the comments, OP is limiting the question to the particular problem. In that case, here's one useful observation: if some fraction is used in which the denominator is divisible by some prime $p$, then at least one more fraction must be used with denominator divisible by $p$; otherwise, there's no way to cancel out that $p$ from the denominator to get a sum of $1$.

It follows that you can't use $1/10$, since $10$ is the only denominator that is a multiple of $5$; similarly, the prime $7$ rules out the use of the fraction $1/14$.

In fact, if some denominator is divisible by some power of a prime, then there must be another denominator divisible by a power at least that big. That means you can't use $1/8$, since $8$ is the only denominator divisible by such a big power of $2$.

So you are left with only $1/2,1/4,1/6,1/12$.

share|improve this answer
add comment

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.