Subset of Coins with maximal value Let $ n \in \mathbb{N} $ with $ n\ge 3 $ be given. Assume that you have $ k-1 $ coins of value $ 1/k $ for all $ k \in \lbrace 2,\ldots,n \rbrace $. Now you have to choose a subset of these given coins with the following properties:
(1) The total value $ S(n) $ of all coins shall be as large as possible.
(2) There is no subset of our chosen coins that leads to a total value of exactly $ 1 $.
(This means, we have to find: 
$S(n):=\max\left\lbrace \sum_{k=2}^n \frac{x_k}{k} \, \middle| \, x_k \in \lbrace 0,1,\ldots,k-1 \rbrace, \nexists y_k \in \lbrace 0,1,\ldots,x_k \rbrace \, : \, \sum_{k=2}^n \frac{y_k}{k}=1 \,\,\,(k=2,\ldots,n) \right\rbrace $
Prove $ S(n)<(n+1)/2 $. Are there better upper bounds that can be obtained? (I doubt that there is a closed expression for $ S(n) $...)
 A: Note that if $k$ is even, say $k = 2m$, then having one coin of value $\frac{1}{m}$ is equivalent to having two coins of value $\frac{1}{k}$.  Hence we may assume $x_k \in \{ 0,1\}$ whenever $k$ is even.
Now observe that every possible denominator $k$ can be written as a power of two times an odd part; that is, $k = 2^a b$.  Grouping together the terms with the same odd part $b$, we find
$$ \sum_{ k = 2^a b, \; a \ge 0} \frac{x_k}{k} \le \frac{b-1}{b} + \sum_{a = 1}^{\log_2 \frac{n}{b}} \frac{1}{2^a b} < \frac{b-1}{b} + \sum_{a=1}^{\infty} \frac{1}{2^a b} = 1.$$
Since there are $\left\lceil \frac{n}{2} \right\rceil \le \frac{n+1}{2}$ choices for the odd part $b$, summing up these terms for some optimal $(x_k)$, we find
$$ S(n) = \sum_k \frac{x_k}{k} = \sum_{b \text{ odd}} \left( \sum_{k = 2^a b, \; a \ge 0} \frac{x_k}{k} \right) < \sum_{b \text{ odd}} 1 \le \frac{n+1}{2}. $$
At this moment I'm not sure how good an upper bound this is.  For a lower bound, I believe you can take all the coins for which $k$ is prime, which gives a bound of $S(n) \gtrapprox \frac{n}{\ln n}$.
A: Now I believe the correct answer is indeed of the order $\frac{n}{\ln n}$.  I'll be using different estimates here, and I don't think the initially requested bound $S(n) < \frac{n+1}{2}$ falls out directly, so I'm posting this as a separate answer.  Throughout the answer below, $p$ and $q$ will always be primes, so I will avoid writing this condition in any sums or products.
I'll begin with the lower bound.  I claim that we can take 
$$ x_k = \begin{cases} k - 1 &\text{if } k \text{ is prime} \\
0 &\text{otherwise} \end{cases}. $$
Why does this work?  Suppose for contradiction we had some set $P$ of primes and some positive integers $y_p \le x_p$ for which $\sum_{p \in P} \frac{y_p}{p} = 1$.  Let $m = \prod_{p \in P} p$.  Multiplying through by $m$, we have
$$ \sum_{p \in P} y_p \cdot \frac{m}{p} = m. $$
Now, for every $q \in P$, we have $q | m$, and so $q$ must divide the sum.  Moreover $q | \frac{m}{p}$ if and only if $p \neq q$, and so we must have $q | y_q$.  However, $y_q \in \{1, 2, ... q-1 \}$, so this is impossible.
What lower bound does this give us?  We have
$$ S(n) \ge \sum_{p \le n} \frac{p-1}{p} = \sum_{p \le n} \left( 1- \frac{1}{p} \right) = \pi(n) - \sum_{p \le n} \frac{1}{p}, $$
where $\pi(n)$ counts the number of primes less than or equal to $n$.  It is known that $\pi(n) \sim \frac{n}{\ln n}$ (see here) and $\sum_{p \le n} \frac{1}{p} \sim \ln \ln n$ (see here), and so we find $S(n) \gtrapprox \frac{n}{\ln n} - \ln \ln n = (1 - o(1)) \frac{n}{\ln n}.$
We will now give an upper bound of a similar form.  Earlier we observed that if $k$ is even, then we may assume $x_k \in \{0,1\}$, since two $\frac{1}{k}$ coins can be replaced by a single coin with half the denominator.  More generally, we may assume that if $p$ is the smallest prime factor of $k$, then $x_k \in \{0,1,..., p-1\}$.  Let $\sigma(k)$ denote the smallest prime factor of $k$.  This results in the upper bound
$$ S(n) \le \sum_{k = 2}^n \frac{\sigma(k)}{k}.$$
How might we evaluate such a sum?  We can start by grouping together summands with the same numerator.  That is,
$$ S(n) \le \sum_{k=2}^n \frac{\sigma(k) - 1}{k} = \sum_{p \le n} \sum_{k : \sigma(k) = p} \frac{p-1}{k} < \sum_{p \le n} \sum_{k : \sigma(k) = p} \left( \frac{k}{p} \right)^{-1}. $$
Let $S_p = \sum_{k : \sigma(k) = p} \left( \frac{k}{p} \right)^{-1}$.  In each summand, $p | k$, so we are summing over the reciprocals of integers.  A trivial upper bound is to assume all integers between $1$ and $n$ appear, giving the harmonic series:
$$ S_p \le \sum_{k \le n} \frac{1}{k} \sim \ln n. $$
For a more careful estimate, note that $\frac{k}{p}$ must be an integer whose prime factors are all at least $p$.  We can enumerate over all the summands (and many more) in the product
$$ \prod_{p \le q \le n} \left(1 + \frac{1}{q} + \frac{1}{q^2} + ... \right) = \prod_{p \le q \le n} \frac{1}{1 - \frac{1}{q}} = \prod_{p \le q \le n} \left(1 + \frac{1}{q-1} \right), $$
where the product is over all primes between $p$ and $n$. (We get every such number $\frac{k}{p}$ by choosing the appropriate power for each of its prime factors, and choosing the $1$ term for every non-factor.)
Using the exponential estimate $1 + x \le \text{exp}(x)$, we have
$$ S_p \le \prod_{p \le q \le n} \left(1 + \frac{1}{q-1} \right) \le \text{exp} \left(\sum_{p \le q \le n} \frac{1}{q-1} \right). $$
Now summing $\frac{1}{q-1}$ is essentially the same as summing $\frac{1}{q}$, and so, if $p$ is large, our earlier fact gives
$$ \sum_{p \le q \le n} \frac{1}{q-1} \approx \sum_{p \le q \le n} \frac{1}{q} = \sum_{q \le n} \frac{1}{q} - \sum_{q \le p} \frac{1}{q} \sim \ln \ln n - \ln \ln p = \ln \frac{\ln n}{\ln p}. $$
In particular, if $p \ge n^{\delta}$ (for some constant $\delta > 0$ to be fixed later), we have $\frac{\ln n}{\ln p} \le \frac{1}{\delta}$, which is constant, and hence we have $S_p \lessapprox \frac{1}{\delta}$.
Putting this together, we have the upper bound
$$ S(n) \le \sum_{p \le n} S_p = \sum_{p < n^{\delta}} S_p + \sum_{n^{\delta} \le p \le n} S_p. $$
For the first sum, with the small primes, we will use the harmonic series estimate on $S_p$.  This gives
$$ \sum_{p < n^{\delta}} S_p \lessapprox \sum_{p < n^{\delta}} \ln n = \pi\left( n^{\delta} \right) \cdot \ln n \sim \frac{n^\delta \ln n} { \ln n^{\delta} } = \frac{n^\delta}{\delta}. $$
For the second sum, we know $S_p$ is approximately $\frac{1}{\delta}$, and so
$$ \sum_{n^{\delta} \le p \le n} S_p \lessapprox \sum_{n^{\delta} \le p \le n} \frac{1}{\delta} \le \frac{\pi(n)}{\delta} \sim \frac{n}{\delta \ln n}. $$
Putting this together, we get
$$ S(n) \lessapprox \frac{n^{\delta}}{\delta} + \frac{n}{\delta \ln n}. $$
Taking $\delta = 1 - \varepsilon$ for small but fixed $\varepsilon > 0$, the first term is a lower order term, and so
$$ S(n) \lessapprox \frac{n}{(1 - \varepsilon) \ln n}, $$
essentially matching the lower bound.
