Problem: Consider the set
\[ A = \left\{ 1 + \frac 1k : k = 1, 2, 3, \dots \right\}. \]
For every integer $x \ge 2$, let $f(x)$ denote
the minimum integer such that $x$ can be written as the product
of $f(x)$ elements of $A$ (not necessarily distinct).
Prove that there are infinitely many pairs of integers $x \ge 2$
and $y \ge 2$ for which \[ f(xy) < f(x) + f(y). \]

Solution: One of many constructions: let $n = 2^e+1$
for $e \equiv 5 \pmod{10}$
and let $x = 11$, $y = n/11$ be our two integers.

We prove two lemmas:
\begin{claim*}
  For any $m \ge 2$ we have
  $f(m) \ge \left\lceil \log_2 m \right\rceil$.
\end{claim*}
\begin{proof}
  This is obvious.
\end{proof}

It follows that $f(n) = e+1$, since $n = \frac{n}{n-1} \cdot 2^e$.

\begin{claim*}
  $f(11) = 5$.
\end{claim*}
\begin{proof}
  We have $11 = \frac{33}{32} \cdot \frac 43 \cdot 2^3$.
  So it suffices to prove $f(11) > 4$.

  Note that a decomposition of $11$ must
  contain a fraction at most $\frac{11}{10} = 1.1$.
  But $2^3 \cdot 1.1 = 8.8 < 11$, contradiction.
\end{proof}

To finish, note that
\[ f(11) + f(n/11) \ge 5 + \log_2(n/11) = 1 + \log_2(16n/11) > 1 + e = 1 + f(n). \]

\begin{remark*}
  Most solutions seem to involve picking $n$ such that
  $f(n)$ is easy to compute.
  Indeed, it's hard to get nontrivial lower bounds other than the log,
  and even harder to actually come up with complicated constructions.
  It might be said the key to this problem
  is doing as little number theory as possible.
\end{remark*}