2
$\begingroup$

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?

  • 0
    For s$i$mplicities sake I'll limit the questio$n$ to this particular problem only.2012-02-15

1 Answers 1

2

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