(a) Unless I'm making a mistake, just take $$x = \prod_{i=1}^{x-1}\left(1+\frac{1}{i}\right)$$

a) Only need to prove this for the primes. To prove that this is possible for a prime $p$, start with the fraction $\frac{p}{p-1}$, and note that we can write $p-1$ as a product of these numbers by induction.

For (b), one construction is to let $n = 2^e+1$ for $e \equiv 5 \pmod{10}$ and let $x = 11$, $y = n/11$. Evidently, $f(xy) = e+1$. We now contend $f(11) = 5$. 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. To finish, note that \[ f(11) + f(n/11) \ge 5 + \log_2(n/11) = 1 + \log_2(16n/11) > 1 + e. \]

$(a)$. Just notice $$x = \left(1 + \frac{1}{x - 1}\right)\left(1 + \frac{1}{x - 2}\right)\cdots\left(1 + 1\right) = \left(\frac{x}{x - 1}\right)\left(\frac{x - 1}{x - 2}\right)\cdots\left(2\right) = x$$ $(b)$. Let $x = 13 \cdot 2^n$ and $y = 5$ for arbitrary $n$. We shall prove that $f(x) + f(y) > f(xy)$. First notice that $$65\cdot 2^n = \frac{65}{64} \cdot 2^{n + 6}$$ Because both $\frac{65}{64}$ and $2$ belong to $A$ it follows that $f(xy) = f(65 \cdot 2^n) \leq n + 7$. Now notice that $x = 13 \cdot 2^n > 2^{n + 3}$ and therefore $f(x) \geq n + 4$, because $2$ is the largest element of $A$. If $f(x) = n + 4$ holds then we must have $x = 2^{n + 3}\left(1 + \frac{1}{k}\right)$, because $x \neq 2^{n + 4}$ and $2^{n + 2}\left(\frac{3}{2}\right)^2 < 13 \cdot 2^n$. However it is not difficult to verify that this is impossible. Thus $f(x) \geq n + 5$. Now if we had $f(xy) \geq f(x) + f(y)$ then $f(5) = f(y) \leq 2$ should hold. However $5 > 2^2$ implies that $f(5) > 2$, a contradiction.

(b) We have $$f(33\cdot 2^n)=n+6<n+7=f(3\cdot 2^n)+f(11).$$

For (b), we can also take $x=3$ and $y=\frac{2^k+1}3$ for large odd $k$. Indeed, it is easy to see that $f(3)=2$, and we know that $f(2^k+1)\le k+1$ as $2^k+1=\left(1+\frac11\right)^k\left(1+\frac1{2^k}\right)$. Hence, if $f(2^k+1)\ge f(3)+f\left(\frac{2^k+1}3\right)$, it follows that $f\left(\frac{2^k+1}3\right)\le k-1$. Suppose that $\frac{2^k+1}3=\left(1+\frac1{a_1}\right)\left(1+\frac1{a_2}\right)\cdots\left(1+\frac1{a_{k-1}}\right)$ with $a_1\le a_2\le\cdots\le a_{k-1}$, where we allow $a_i=\infty$ so the term contributes nothing. Then note that $a_1=a_2=\cdots =a_{k-2}=1$, as otherwise $\left(1+\frac1{a_1}\right)\left(1+\frac1{a_2}\right)\cdots\left(1+\frac1{a_{k-1}}\right)\le\left(1+\frac11\right)^{k-3}\left(1+\frac12\right)^2=9\cdot 2^{k-5}=\frac{27\cdot 2^{k-5}}3<\frac{2^k}3<\frac{2^k+1}3$, contradiction. But now, we have that $1+\frac1{a_{k-1}}=\frac{2^k+1}{3\cdot 2^{k-2}}\implies a_{k-1}=\frac{3\cdot 2^{k-2}}{2^{k-2}+1}$, which is not an integer for large $k$.

a) trivial b) The key idea is that take the $f(x)$ expansion from $x$ and $f(y)$ expansion from $y$, we can mix them into $f(x)+f(y)$ expansion for $xy$, so $f(xy)\le f(x)+f(y)$, so this problem is all about finding some $x, y$ that "naive combining" is not optimal. To do so use bare hands to gain some exact values of $f$. Some attempts are $f(2^n)=n, f(2^n+1)=n+1, f(x)\ge \lceil \log_2(x) \rceil$. But how should I find such pair $(x,y)$, and yet showing that combining is not optimal? Shrinking the expansion might not be easy. Then the next key idea is looking at the other side instead. Let's fix $x, xy$ with something we know instead, and $y$ is something we don't know. A good choice will be take $x, xy$ to have the form $2^k+1$ and $y$ is not. Smallest such pair corresponds to $(x,y)=(3,11)$ and we want to prove $f(11)>4$. Now this easy by case work: four $2$'s gives $16$, fail, three $2$'s gives $12$ or something at most $\frac{4}{3}\times 8<11$, fail, otherwise at most $(\frac{3}{2})^2\times 4<11$, fail. Good, so we have $(x,y)=(3,11)$ works. Of course, $(x,y)=(3\cdot 2^n, 11)$ will now work as well then. This is because $3\cdot 2^n=\frac{3}{2}2^{n+1}$ and $f(3\cdot 2^n)\ge \log_2(3\cdot 2^n)>n+1$, so $f(3\cdot 2^n)=n+2$. Likewise $f(33\cdot 2^n)=n+6$, so $f(33\cdot 2^n)=n+6<n+7=f(11)+f(3\cdot 2^n)$.

b) It is easy to see that $f(11)=f(17)=f(20)=5$ and $f(31)=7$, thus we have that $$f(11\cdot 31)=f(341) \le 1+f(340) \le 11<f(11)+f(31)$$Suppose that $f(xy)<f(x)+f(y)$ for finitely many pairs of integers, thus for any number $X$ bigger than a large enough $M$ we will have that $f(X)=f(a)+f\left(\frac{X}{a}\right)$ , where $a$ is any divisor of $X$. Now let $m>M$ and $n>M$ be integers. $$f(11)+f(31)+f(mn)=f(11)+f(31)+f(m)+f(n)=f(11n)+f(31m)=f(341mn)=f(341)+f(mn) \ \ \ \text{contradiction}$$

Key idea: $f(2^n + 1) = n+1$, so set $xy = 2^n+1$ and make something like $$n+1 = f(2^n+1) \le \lceil \log_2 x \rceil + \lceil \log_2 y \rceil < f(x)+f(y)$$ To do this, find stuff like $f(11)=5 > 4 = \lceil \log_2 (11) \rceil$ and you are good to go.

a) Just take $x= \left(1+\frac{1}{1} \right) \left(1+\frac{1}{2} \right) \cdots \left(1+\frac{1}{x-1} \right)$. b) Let us consider some cases. If $f(2x) < f(x)+1 = f(x)+f(2)$ for infinitely many $x \in \mathbb{Z}_{\ge 2}$, then we are done. If there is no $x$ such that $f(2x)<f(x)+1$, then $f(2x)=f(x)+1$ for all $x$ (just add the factor $\left(1+\frac{1}{1} \right)$ in the representation of $x$). Then if $f(xy)<f(x)+f(y)$, we have $f(2xy)=f(xy)+1 < f(x)+f(y)+1 = f(2x)+f(y)$, so we can construct infinitely many pairs: if $(x,y)$ works, so does $(2x,y)$. In this case, we are done because $(11,31)$ works. If there exists $x$ so that $f(2x)<f(x)+1$ and such numbers are finite, call $X$ the greater of these numbers. Then $2X>X \implies$ $f(4X)=f(2X)+1 < f(X)+2=f(X)+f(4)$ and it easily follows by induction that $f(2^k \cdot X)<f(X)+f(2^k)$ for all $k \in \mathbb{Z}_{\ge 2}$, then we are finally done.

Is $f(x)+f(y)-f(xy)$ unbounded?

b) Choose $x=7$, $y=7\cdot 2^n$. First we’ll prove that $f(7\cdot 2^n)\geq n+4$. Clearly $f(7\cdot 2^n)\geq n+3$, so it suffices to prove that $n+3$ factors are impossible. If at least $n+2$ factors are $2$, then it’s impossible by easy casework. If at most $n+1$ factors are $2$, then the product is at most $2^{n+1}\cdot(\frac{3}{2})^2$, which is too small. Now $49=\frac{49}{48}\cdot\frac{3}{2}\cdot 2^5$, so $f(49)\leq 7$. Thus $f(49\cdot 2^n)\leq n+7<n+8\leq f(7)+f(7\cdot 2^n)$

a) we can see that $x= \left(\frac{2}{1} \right) \left(\frac{3}{2} \right) \cdots \left(\frac{x}{x-1} \right)$ works. b) we can see that solutions of the form $(x,y)=(\frac{2^k+1}{3},3.2^n)$ work where k is odd and $f(2^k+1\cdot 2^n)\leq n+k+1<\lceil\ log_2 2^k+1\rceil+\lceil\ log_2 2^n\rceil <f(2^k+1)+f(2^n)$ so we can have $(x,y)=(43,3.2^n)$ $\boxed{Claim}$ $\boxed{f(43)>7}$ $\boxed{Proof}$ lets assume on the contrary that $f(43)=7$ so we need to approach it by counting the number of $2$"s it has. if it has three or lesser $2$'s we get a contradiction as $43>8\cdot(\frac{3}{2})^2$ if it has four $2$"s or more then there must be a term whose numerator is a multiple of 43 largest such term is $\frac{43}{42}$ However we again easily get a contradiction.$\square$ So using our claim $f(129.2^n)\leq n+8< \lceil\ log_2 43\rceil+\lceil\ log_2 3.2^n\rceil=n+8<n+9< f(43)+f(3.2^n)$ $Q.E.D \square$ @below when i was searching for solutions We could see that $f(2^k+1)$ and$f(2^k)$ had fixed values so the idea was to resolve 2^k+1 into factors.

The solutions for B are nice; but how did you get there (I understand your solution, but during a comp what takes you to that!)!

For part b), first see that $f(xy) \leq f(x)+f(y)$. Suppose that $f(2^n+1) = f(3) + f\left(\frac{2^n+1}{3}\right)$, for every $n>N$. Note that $$2^n+1 = \left(\frac{2^n+1}{2^n}\right)\cdot \left(\frac{2}{1}\right) \cdot \left(\frac{2}{1}\right) \cdots \left(\frac{2}{1}\right)$$Then, we have that $f(2^n+1) \leq n+1$. Thus, as $f(3) = 2 \Rightarrow f\left(\frac{2^n+1}{3}\right) \leq n-1$. Let $t$ be the number of times the factor $\left(1+\frac{1}{1}\right) = 2$ is used in the minimal representation of $\frac{2^n+1}{3}$. Then, $t \leq n-1$. Notice that: $$\frac{2^n}{3} < \frac{2^n+1}{3} \leq 2^t\cdot \left(\frac{3}{2}\right)^{n-1-t} = \frac{3^{n-1-t}}{2^{n-1-2t}}$$$$\Rightarrow \left(\frac{4}{3}\right)^{n-t} < 2 \Rightarrow n-t \leq 2$$$$\Rightarrow n-2 \leq t \leq n-1$$Lets look such cases: 1) $\underline{t = n-1:} $ $\Rightarrow \frac{2^n+1}{3} = 2^{n-1}$, which is false for $n > 1$. 2) $\underline{t = n-2:} $ $\Rightarrow \frac{2^n+1}{3} = 2^{n-2}\cdot\left(\frac{k+1}{k}\right) \Rightarrow k = \frac{3.2^{n-2}}{2^{n-2}+1}$, which is clearly not an integer for $n>4$. Then, we conclude that $f(2^n+1) < f(3) + f\left(\frac{2^n+1}{3}\right)$, for every $n$. $\blacksquare$ P.S: The motivation to think in $2^n+1$ was that we can bound its $f$ with a linear expression, by bulling the 2 factors out of the denominator of $\frac{2^n+1}{2^n}$. Then, we would have bounded most of the big divisors of $2^n+1$, eliminating the chances of an equality in $f(xy) \leq f(x)+f(y)$.

Part b: if $f(xy)<f(x)+f(y)$ for only finitely many $(x,y),$ then for all $xy\ge N$ for some $N,$ $f(xy)=f(x)+f(y).$ Now let $n>N$ and let $x,y$ be any two integers $\ge 2$; we write $f(xyn)$ in two ways. $f(xyn)=f(xy)+f(n),$ but $f(xyn)=f(x)+f(yn)=f(x)+f(y)+f(n).$ This means $f(xy)=f(x)+f(y)$ for all $x,y\ge 2,$ and now we no longer need the size restriction $xy\ge N.$ So now if we can find any pair $(x,y)$ for which $f(xy)\ne f(x)+f(y),$ we have a contradiction and there must be infinitely many pairs. Using the assumption $f(xy)=f(x)+f(y),$ it is not too difficult to find $f(6)=3,f(7)=4,f(8)=3.$ Then $f(48)=6$ and $f(49)=8$; but $f(x+1)\le 1+f(x) \ \forall x,$ contradiction. Therefore $x=y=7$ creates a contradiction and $f(xy)<f(x)+f(y)$ must hold for infinitely many $x,y.$

(a) \[x=2\cdot\frac{3}{2}\cdot\frac{4}{3}\cdots\frac{x}{x-1}.\] (b) Let $n\equiv2\pmod4$ with $n\geq6$ and pick $x=5,y=\frac{2^n+1}{5}$. For any integer $m\geq2$, let $S_m$ be a multiset of positive integers such that \[m=\displaystyle\prod_{k\in S_m}\left(1+\frac{1}{k}\right)\]and $\left|S_m\right|=f\left(m\right)$. Then \[m=\displaystyle\prod_{k\in S_m}\left(1+\frac{1}{k}\right)\leq\displaystyle\prod_{k\in S_m}2=2^{f\left(m\right)},\]so $f\left(m\right)\geq\log_2m$. So for any nonnegative integer $j$, $f\left(2^j+1\right)\geq j+1$. But \[2^j+1=\frac{2^j+1}{2^j}\cdot\underbrace{2\cdot2\cdots2}_{j},\]so $f\left(2^j+1\right)\leq j+1$ and thus $f\left(2^j+1\right)=j+1$. Then $f\left(2^n+1\right)=n+1$ and $f\left(5\right)=3$ since $5=2^2+1$. Now, observe that \[f\left(\frac{2^n+1}{5}\right)\geq\log_2\frac{2^n+1}{5}>\log_22^{n-3}=n-3,\]so $f\left(\frac{2^n+1}{5}\right)\geq n-2$. Suppose $f\left(\frac{2^n+1}{5}\right)=n-2$; let $b$ elements of $S_{\frac{2^n+1}{5}}$ be larger than $1$, so it has $n-2-b$ elements that are $1$. Then \[\frac{2^n+1}{5}=2^{n-2-b}\displaystyle\prod_{\substack{k\in S_m \\ k>1}}\left(1+\frac{1}{k}\right)\leq2^{n-2-b}\left(\frac{3}{2}\right)^b=2^{n-2}\left(\frac{3}{4}\right)^b,\]so \[\left(\frac{3}{4}\right)^b\geq\frac{2^n+1}{5\cdot2^{n-2}}>\frac{4}{5}.\]When $b\geq1$, this inequality is false, so $b=0$. Then $\frac{2^n+1}{5}=2^{n-2}$, but the LHS is odd while the RHS is even, contradiction. So $f\left(\frac{2^n+1}{5}\right)>n-2$. Thus, \[f\left(xy\right)=f\left(2^n+1\right)=n+1=3+\left(n-2\right)<f\left(5\right)+f\left(\frac{2^n+1}{5}\right)=f\left(x\right)+f\left(y\right).\]Choosing any $n$ as specified will work, so there are infinitely many pairs $\left(x,y\right)$ that work.

achen29 wrote: The solutions for B are nice; but how did you get there (I understand your solution, but during a comp what takes you to that!)! Here is my motivation. - The inequality we want to prove is in form $f(xy) < f(x)+f(y)$. So we need both lower and upper bound of $f$ (of course for some specific form). - The trivial lower bound is $f(x)\ge\log_2 x$, which is not tight for many cases. One example is $x=7$ which you can prove that $f(7)=4$. Generalizing, $f(p)\geqslant 1+\log_2(p-1)$ for arbitrary primev$p$. - So we find some points where $f$ is a bit larger than $\log_2 x$. Now, the next key step is to realize that on the other hand, $\log_2$ bound is tight for $2^k+1$ (i.e. $f(2^k+1) = k+1$). - So we want $xy$ to be $2^k+1$ and $x$ be a prime (which $x=11$ works). This gives the solution.

For part $\text{b}$ we consider $x=y=2^{3k-1}+3$ for $k \geq 1$. Firstly clearly $f(2^{3k-1}+3)>3k-1$ as the max element in $A$ is $2$. We claim $f(2^{3k-1}+3) \geq 3k+1$ for contradiction assume $f(2^{3k-1}+3)=3k$ then: $$2^{3k-1}+3=x_1 \cdot x_2 \cdot \cdots \cdot x_{3k}$$As $2^{3k-1}+3 \equiv 2^{-1}+3 \equiv 0 \pmod{7}$ so it follows $\exists v_{7} \left (x_i \right) \geq 1$ WLOG let this be $x_1=\frac{7y}{7y-1}$ for some $y$ As $7y-1 \neq 2^{\alpha}$ by considering $\pmod{7}$ hence $\exists_{i \neq 1} x_i \neq 2$. WLOG let $x_2 \neq 2$ then: $$2^{3k-1}+3=x_1 \cdot x_2 \cdot \cdots \cdot x_{3k} \leq \frac{7}{6} \cdot \frac{3}{2} \cdot 2^{3k-2}<2^{3k-1}$$Which is a contradiction so $f(2^{3k-1}+3) \geq 3k+1$. Now we let: $$X=2^{3k-1}+4=\frac{2^{3k-3}+1}{2^{3k-3}} \cdot \underbrace{2 \cdots 2}_{3k-1}$$$$Y=2^{3k-1}+2=\frac{2^{3k-2}+1}{2^{3k-2}} \cdot \underbrace{2 \cdots 2}_{3k-1}$$Each contains $3k$ fractions. Using also that: $$\frac{\left( 2^{3k-1}+3 \right)^2}{\left( 2^{3k-1}+3 \right)-1}=\frac{\left( 2^{3k-1}+3 \right)}{\left (2^{3k-1}+2 \right) \left(2^{3k-1}+4 \right)}=\frac{\left( 2^{3k-1}+3 \right)}{XY}$$From this we see: $$\left( 2^{3k-1}+3 \right)^2=\frac{\left( 2^{3k-1}+3 \right)^2}{\left( 2^{3k-1}+3 \right)-1} \cdot X \cdot Y$$And hence $f \left(\left( 2^{3k-1}+3 \right)^2 \right) \leq 6k+1$ so: $$f(xy)=f \left(\frac{\left( 2^{3k-1}+3 \right)^2}{\left( 2^{3k-1}+3 \right)-1} \right) \leq 6k+1<2(3k+1)=f(x)+f(y)$$

Part (a) is utterly trivial. I had the $(3, \frac{2^k + 1}{3})$ solution on my blog, but I feel like this is also quite nice: It is clear by concatenation that $f(xy) \le f(x) + f(y) \quad (1)$ for all $x, y \ge 2$. Since $f(33) < f(3) + f(11)$ [citation needed], there is at least one bad pair $(x, y)$ with $f(xy) < f(x) + f(y) \quad (*)$. Suppose there are finitely many bad pairs, and choose $(x, y)$ with $x + y$ maximal. Choose $N > x, y$; then by maximality and (1) we have $$f(x) + f(N) = f(xN)$$$$f(xy) + f(N) = f(x y N)$$Add $f(N)$ to both sides of $(*)$ to get $$f(xy N) < f(x N) + f(y),$$which again contradicts the maximality of $(x, y)$!

@some posts above asking for motivation, the way I did it was trying to approximate f(x) by looking at binary expansion of x, where f(x) is approximately (number of digits)+(number of digits 1)-2 e.g. $49=110001=2\times \frac32\times 2\times2\times2\times 2\times \frac{49}{48}$. To find construction i multiplied a bunch of numbers in binary until i got something that works (count digits i guess) $111\times111=11001$ which is $7\times 7=49$ and you can look at the rest of the construction in post #13.

(a) It is quite trivial. We can easily check $$\prod_{k=1}^{x-1} (1+\frac {1}{k}) = \prod_{k=1}^{x-1} (\frac {k+1}{k}) = \frac{2}{1} \frac{3}{2} \frac{4}{3} \cdots \frac{x-1}{x-2} \frac{x}{x-1} = x$$ (b) One construction is $x=7$, $y=2^n . 7$ It is obvious that $f(7)=4$ and $f(2^n)=n$. So, $f(2^n . 7) = n+4$ [It can be proved that $2^n . 7$ can't be expressed as the product of less than $n+4$ terms of $A$] Now, $49=\frac{49}{48} \frac{3}{2} \frac{2}{1} \frac{2}{1} \frac{2}{1} \frac{2}{1} \frac{2}{1}$ So, $f(2^n . 49) \le n+7 < n+4 + 4 = f(2^n . 7) + f(7)$

Here's my solution: a. Multiplication of first $n$ element of $A$ is $\prod_{k=1}^n{\frac{k+1}{k}}=k+1$ for all $n\in N$.Thus proved. b. Consider the number $T:=2^{2n+1}+1$. Obviously $3\mid T$ since $T\equiv2\times2^{2n}+1\equiv2+1\equiv0.$ Now set $x=3$, $y=\frac{T}{3}$. Notice that $$T=\frac{2^{2n+1}+1}{2^{2n+1}}\times\frac{2}{1}\times\frac{2}{1}\times...\times\frac{2}{1}$$($\frac{2}{1}$ appears $2n+1$ times.) So, $f(T)\le2n+2$ But it's obvious that $f(3)=2$. Now we want to prove that $f (y)>2n $ for all integer $n\ge2$.If this hold,then $ f(x)+f(y)> 2n+2 \geq f(T) $ i.e. $f(x)+f(y)>f(xy)$ also hold. Now notice \begin{align*} T&=3\times(2^{2n}-2^{2n-1}+2^{2n-2}-...-2^1+2^0)\\&=3\times(2^{2n-1}+2^{2n-3}+...+2^3+2^1+1) \end{align*}So, $y=1+\sum_{i=1}^n{2^{2i-1}}$ The largest element of $A$ is $2$, second largest $\frac{3}{2}$ Assume $ f(y)> 2n $ is not true for all integer $n\ge2$. But $2^{2n-1}<y$ implies $f(y)\ge 2n$. So,if that's not true,then $f(y)$ will be equal to $2n$ If we multiply $2$ from $A$, $2n$ times,that will be $2^{2n}$. But $y>\sum_{i=0}^{2n-1}{2^i}=2^{2n}-1>2^{2n}$. So we can use $2$ from $A$ at most $2n-1$ times. when we use $2$, $2n-1$ times to get $y$,then $$y=2^{2n-1}\times\frac{t+1}{t}.$$Since $y$ integer,$t$ should be a power of $2$.It's easy to check that $t$ can't be greater than $2$ also when $t=2$ then $ y< 2^{2n-1}\times\frac{t+1}{t} $ for all $n\ge2.$ So we can use $2$ at most $2n-2$ times to get $y$. But notice that-that will be less than or equal to \begin{align*} 2^{2n-2}\times(1+\frac{1}{u})\times(1+\frac{1}{v})\\&\le2^{2n-2}\times\frac{9}{4}\\&=2^{2n-1}+2^{2n-3}\\&<y \end{align*}From here we get that our assumption was wrong. So $ f(y)> 2n $. Thus the prof is complete.

Wow this problem is a troll. I explain the reason in the remark. BarishNamazov wrote: Consider the set \[A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.\] Prove that every integer $x \geq 2$ can be written as the product of one or more elements of $A$, which are not necessarily different. For every integer $x \geq 2$ let $f(x)$ denote the minimum integer such that $x$ can be written as the product of $f(x)$ elements of $A$, which are not necessarily different. Prove that there exist infinitely many pairs $(x,y)$ of integers with $x\geq 2$, $y \geq 2$, and \[f(xy)<f(x)+f(y).\](Pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if $x_1 \neq x_2$ or $y_1 \neq y_2$). The part $a$ is given just to show that the function $f$ in part $b$ is well defined and not cause confusion. Anyways note that $$x=\prod_{k=1}^{x-1} \left( 1+\frac{1}{k} \right)$$and so this is done. Now part $b.$ Note that $f(xy) \le f(x)+f(y)$ always holds true since the terms used to obtain $x$ and the terms used to get $y$ can be multiplied to each other to get $xy.$ Define the set $$\mathbf{S}:=\{(x,y) \in \mathbb{Z}_{\ge 2} \times \mathbb{Z}_{\ge 2} | f(xy) \ne f(x)+f(y)\}$$It suffices to show that $\mathbf{S}$ is infinite. Note that $f(x)>2$ for all $x>3.$ Claim: $\mathbf{S}$ is non-empty. Proof: Assume not, then $f(ab)=f(a)+f(b)$ for all $a,b \ge 2.$ Now since $33=\tfrac{33}{32} \cdot 2^5,$ hence $f(33) \le 6.$ Thus $$2+f(11)=f(3)+f(11)=f(33) \le 6 \implies f(11) \le 4$$Hence, there are four numbers in $A$ that multiply to give $11.$ Since $11$ is a prime, hence one of the numerators must be a multiple of $11,$ say it is $11k.$ Then the corresponding denominator $11k-1$ should be cancelled by the next $3$ terms and so we get $f(11k-1) \le 3.$ Now if $1 \ne p$ divides $(11k-1),$ then $3 \ge f(11k-1)>f(p),$ absurd. Hence $11k-1$ is a prime greater than $3.$ But again a numerator-denominator analysis gives a contradiction. $\square$ Now assume on the contrary that $\mathbf{S}$ is finite. Then there exists an integer $M$ such that $f(xn)=f(x)+f(n)$ holds true for all $x>M.$ Fix any such $x>M,$ and so for any $a,b \ge 2,$ $$f(ab)+f(x)=f(ab \cdot x)=f (a \cdot bx)=f(a)+f(bx)=f(a)+f(b)+f(x)$$And so we get $f(ab)=f(a)+f(b)$ for all $a, b \ge 2,$ which implies that $\mathbf{S}$ must be empty, a contradiction by the claim. $\square$ Remark: At first, I thought of constructing $x,y$ that satisfy the problem's conditions. So I tried to put bounds on $f$ and realized that $f$ behaves in a pretty interesting and arbitrary manner, which is weird for an olympiad. For example I discovered: $$\lceil \log_{2} \mu \rceil \le f (\mu) \le \lfloor \log_{2} \mu \rfloor+\frac{\mu-2^{\lfloor \log_{2} \mu \rfloor}}{\nu_2(\mu-2^{\lfloor \log_{2} \mu \rfloor})}$$I proved the upper bound but couldn't prove the lower. The upper one is derived by showing $f(2^n+2^zk) \le n+k.$ Of course, the bound can be improved by changing the expression inside $f$ to something more general, but I soon figured out that bounding is a bad idea for this question. And then after about an hour of playing with $f,$ I found that contradiction would work better, in fact, a lot better. After about $10$ minutes I showed that $\mathbf{S}$ must be empty, but man, proving this was not possible was hard. It took me about an hour to find the right numbers to work with to prove my claim. But the problem was really nice!

Here's a solution for $(b)$ with some motivation: Note that $f(n) \geq log_2 n$ (each element of $A$ is $\leq 2$). Also note $f(n+1) \leq f(n) + 1$ (multiply by $1+1/n$). Now, suppose the problem claim is false. Then, there exists $N$ such that for all $n \geq N$, if $n = ab$ with $a, b \geq 2$, then $f(n) = f(a) + f(b)$ Now we prove that $f(ab) = f(a) + f(b)$ for all $a, b \geq 2$. Indeed, take $k \geq 2$ such that $ak \geq N$. Then, $f(ab) + f(k) = f(abk) = f(ak) + f(b) = f(a) + f(k) + f(b)$, so $f(ab) = f(a) + f(b)$. Now, note $f(2) = 1, f(3) = 2$. Consider $f(513) \leq f(512) + 1 = 10$ Also, $f(513) = f(27) + f(19) = 6 + f(19)$ Thus, $f(19) \leq 4$. But $log_2 19 > 4$, a contradiction. And we're done. Motivation: The first two inequalities are motivated by (and are obvious on) trying to get some rudimentary bounds on the values of $f(n)$. The $f(ab) = f(a) + f(b)$ part is obvious once we try to do a proof by contradiction and come up with the idea of $N$. Finally, the way I came up with $513$ was by looking at numbers of the form $2^k + 1$. The motivation to do so is that our $log_2 n$ bound holds strict for $n$ of the form $2^k$, which in turn gives us a somewhat good bound on $f(2^k + 1)$, which can be computed in another way for non-prime $2^k + 1$.

MarkBcc168 wrote: - The trivial lower bound is $f(x)\ge\log_2 x$, which is not tight for many cases. One example is $x=7$ which you can prove that $\boxed{f(7)=5}$. Generalizing, $f(p)\geqslant 1+\log_2(p-1)$ for arbitrary primev$p$. $7=7/6 *3/2*2*2$

(a) $x = \tfrac21\cdot \tfrac32\cdots \tfrac{x}{x-1}$. (b) We claim $f(11)=5$, which we can get from $11=\tfrac{11}{10}\cdot \tfrac{5}{4}\cdot (\tfrac21)^3$. Suppose $f(11) \le 4$. If we used at most 2 of $\tfrac21$, then the maximum number we can get is $(\tfrac21)^2\cdot (\tfrac32)^2=9$. So we need to use exactly 3 of $\tfrac21$ (we can't use 4). Then $11 = (\tfrac21)^3 \cdot \tfrac{11}{8}$, but $\tfrac{11}{8} \not \in A$, contradiction. Hence $f(11)=5$. We also claim that $f(3\cdot 2^k) = k+2$, for any $k\ge 0$, which is achieveable by $3\cdot 2^k = \tfrac32 \cdot (\tfrac21)^{k+1}$. Suppose $f(3\cdot 2^k) \le k+1$. The maximum number we can get with $k+1$ elements of $A$ is $(2/1)^{k+1} = 2^{k+1} < 3\cdot 2^k$, contradiction. Now, simply notice \[ 33\cdot 2^k = \frac{33}{32} \cdot \left(\frac21\right)^{k+5} \implies f(33\cdot 2^k) \le k+6, \]while

https://artofproblemsolving.com/community/c6h1260754p6542783 irie

EGMO 2018 P2 wrote: Consider the set \[A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.\] Prove that every integer $x \geq 2$ can be written as the product of one or more elements of $A$, which are not necessarily different. For every integer $x \geq 2$ let $f(x)$ denote the minimum integer such that $x$ can be written as the product of $f(x)$ elements of $A$, which are not necessarily different. Prove that there exist infinitely many pairs $(x,y)$ of integers with $x\geq 2$, $y \geq 2$, and \[f(xy)<f(x)+f(y).\](Pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if $x_1 \neq x_2$ or $y_1 \neq y_2$). For (a) we obviously have $\displaystyle x=\prod_{i=1}^{x-1} \displaystyle (1+\dfrac{1}{x})$ Let's now tackle (b). We will prove that $x=13 \cdot 2^n, y=5$ work, for all $n \in \mathbb{N}$. We start off with a Claim. Claim: $2^{f(x)} \geq x$ for all $x \geq 2$. Proof: Obviously, each term of the product is $\leq 2$ hence $x \leq 2^{f(x)}$, as desired $\blacksquare$ To the problem, we want to prove that $f(13 \cdot 2^n)+f(5)>f(65 \cdot 2^n)$. Note that $$65 \cdot 2^n=(1+\dfrac{1}{1})^{n+6} \cdot (1+\dfrac{1}{64})$$hence $f(65 \cdot 2^n) \leq n+7 \, (*)$ In addition, using the Claim we obtain $$ 2^{f(13 \cdot 2^n)}>13 \cdot 2^n>2^{n+3} \Rightarrow f(13 \cdot 2^n) \geq n+4 \, (**)$$In fact, we prove that $f(13 \cdot 2^n) \neq n+4$. Suppose that $f(13 \cdot 2^n)=n+4$. Let $n+k$ with $k \in \mathbb{Z}$ be the number of $(1+\dfrac{1}{1})$ factors existing in the product. Obviously, $n+k \leq n+4 \Rightarrow k \leq 4$ Then, $$13 \cdot 2^n=2^{n+k} \cdot (1+\dfrac{1}{s_1})(1+\dfrac{1}{s_2}) \cdots (1+\dfrac{1}{s_{4-k}})$$with $s_1,s_2, \ldots, s_{4-k} \geq 2$, hence $$13 \cdot 2^n \leq 2^{n+k} \cdot (\dfrac{3}{2})^{4-k},$$which rewrites as $2^{2k-4}>13 \cdot 3^{k-4}$. If $k \geq 0$, then $k \in \{1,2,3,4 \}$, hence by inspection we have $k=4$, therefore $13 \cdot 2^n=2^{n+4},$ which is a contradiction. If $k<0$, let $k=-x$ with $x>0$. The inequality easily rewrites as $1>\dfrac{81}{208} >\dfrac{4^x}{3^x}>1,$ which is again a contradiction. Therefore, $f(13 \cdot 2^n) \neq n+4$, as desired. Hence, combining the latter with $(**)$ we obtain $f(13 \cdot 2^n) > n+4$. Now, from the Claim $$2^{f(5)} >5 >4 \Rightarrow f(5) \geq 3 $$ Combining now all the above we obtain $$f(13 \cdot 2^n)+f(5) > n+4+f(5) \geq n+7 \geq f(65 \cdot 2^n),$$as desired. Hence, there exist infinitely many pairs $(x,y)$ that satisfy the desired.

For part a note that: $$x=\prod_{k=1}^{x-1} 1+\frac{1}{k}$$for all $x$. Now we look at part b. First notice that $f(x)+f(y) \geq f(xy)$, which is obviously true. Now define: $$S=\{(x,y) \mid x,y \in \mathbb{Z}_{\geq 2}, f(xy)<f(x)+f(y)\}$$in other words, $S$ is the set of all pairs $(x,y)$ that satisfy $f(xy)<f(x)+f(y)$ (with $x,y \geq 2$). It is equivalent to show that $S$ is infinite. Claim: $S$ is nonempty. Proof: Consider the number $33=3\cdot 11$. We see that $f(3)=2$ since $3=\tfrac{2}{1}\cdot\tfrac{3}{2}$, and obviously $3$ can't be expressed in fewer terms. We can also see that $f(11)=5$. First, $11=\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{5}{4}\cdot\tfrac{11}{10}$. To see why $11$ cannot be expressed as the product of less than $5$ terms, note that any expression must use a fraction less than or equal to $\tfrac{11}{10}$ (otherwise the numerator of the result will not be divisible by 11), so the maximum obtainable number with $4$ terms is $\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{11}{10}=8.8<11$. Now we can see that $33=\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{2}{1}\cdot\tfrac{33}{32}$, so $f(33)=6$. Then we have: $$7=f(3)+f(11)>f(33)=6$$so $(3,11)$ and $(11,3)$ are in $S$. Now that we know $S$ is nonempty, we will prove that it is infinite with a proof by contradiction. Suppose $S$ is finite (and nonempty, of course), and let $(x,y)$ be the element of $S$ with the largest $x$-value. If there are multiple, we can just pick any one. We have: $$f(x)+f(y)>f(xy) \implies f(x)+f(y)+f(xy)>f(xy)+f(xy)$$Since $y \geq 2$ we have $(xy,xy) \not \in S$, so $f(xy)+f(xy)=f(x^2y^2)$. We also have $(xy,x) \not \in S$, so $f(xy)+f(x)=f(x^2y)$. Finally, we have $(x^2y,y) \not \in S$, so $f(x^2y)+f(y)=f(x^2y^2)$. But this implies: $$f(x)+f(y)+f(xy)=f(x^2y)+f(y)=f(x^2y^2)=f(xy)+f(xy)$$which contradicts $f(x)+f(y)+f(xy)>f(xy)+f(xy)$. Therefore there cannot exist an element $(x,y)$ of $S$ with a maximal $x$-value, so $S$ is finite as desired. $\blacksquare$

Lemma: If $2^{t+1}>a_1a_2...a_n \geq 2^t$ and $2^{e_i+1}> a_i \geq 2^{e_i}$ then $\sum e_i = t$. We will prove this by induction. For our basis, $n=1$ trivially works. So, for the inductive step, assume this result holds for some $n$. We have. $2^{t+1}>a_1a_2...a_n \geq 2^t \Rightarrow \sum e_i = t$ Now, taking $2^{e_{n+1}+1}> a_{n+1} \geq 2^{e_{n+1}}$ we get $2^{t+1+e_{n+1}}>a_1a_2...a_na_{n+1} \geq 2^{t+e_{n+1}}$ and $\sum e_i = t+e_{n+1}$. Completing the induction $\blacksquare$ Claim 1: if $n>2^k$ then $f(n)>k$. Let us prove this by strong induction. Basis: $f(3)=2>1$ Inductive step: Suppose that for all $n<N$ and $N>2^{\ell}$ where $N$ is not a power of $2$, if this relation holds. We get two cases. Case 1: $f(N)=f(N-1)+1$. Clearly, by our hypothesis $f(N-1)> \ell$ so $f(N)> \ell$. Case 2: $f(d_1d_2d_3...d_m)=f(d_1)+f(d_2)+f(d_3)+ \cdots +f(d_m)$ where $d_1d_2d_3...d_m=N$. But, by our lemma, $f(d_1)+f(d_2)+f(d_3)+ \cdots +f(d_m) > \ell$. Completing the induction $\blacksquare$ Take $K$ to be a positive integer where $2^K+1$ is not prime. Let $2^K+1=ab$. Claim 2: $f(2^K+1)=K+1$ By claim 1, $f(2^K+1) > K \iff f(2^K+1) \geq K+1$. Equality is always acheived since $f(2^K+1)=f(2^K)+1$ $\blacksquare$ Finally, we get back to the problem with all this framework. Let us prove $f(2^K+1) < f(a)+f(b)$ $\iff K+1<f(a)+f(b)$. Clearly, $2^{K+1}> 2^K+1> 2^K$. Let $2^{A+1}> a \geq 2^A$ and $2^{B+1}> b \geq 2^B$ we get $A+B=K$ by our lemma and $f(a) \geq A+1$ and $f(b)>B$ by claim 1. So, $f(a)+f(b) > A+B+1 =K+1$ and we are done. $\blacksquare$

For part (b), can't we just take $(2^n+1,2^{2n}-2^n+1)$ for large $n$? Then, $f(x)=n+1$ and $f(xy)=3n+1$, and it's quite easy to show that $3 \cdot 2^{2n-2}<f(2^{2n}-2^n+1)<2^{2n}$ for large $n$, so $2^{2n}-2^n+1$ is not representable in $2n$ products.

The condition is essentially saying that there are infinitely many numbers that can be constructed more efficently than splitting them into two smaller ones in some way. We will be trying to use the number $2^n+1$ for some $n$. This is because using 2s is the most efficient, so once we put down the initial factor of $\frac{2^n+1}{2^n}$ we can just spam 2s. Claim: $f(11)=5$. This is achieved by $(11/10)(5/4)(2)(2)(2)$. Clearly, $f(11)\geq4$ since $11>2^3$. Suppose FTSOC that $f(11)=4$. Now, one of the four factors must have a factor of 11 in the numerator, and thus be at most 11/10, so the other three factors must have a product at least 10, absurd since $2^3$ is only 8. Now, we claim that for any positive integer $k$, $$x=11,y=\frac{2^{10k+5}+1}{11}$$works ($y$ is an integer by FLT). Note that $$2^{10k+5}+1=\frac{2^{10k+5}+1}{2^{10k+5}}\cdot 2^{10k+5},$$which means $f(xy)\leq 10k+6$. Furthermore, $$f(y)\geq \lceil \log_2(y) \rceil = 10k+2,$$but since $f(x)=5$ we have that $f(x)+f(y)\geq 10k+7$, so thus this works and we are done since we can pick infinitely many $k$.

Part (a) is vacuous. For part (b), we use the construction $(x, y) = (5 \cdot 2^n, 13 \cdot 2^n)$. Notice that $f(n) \geq \left \lceil \log_2 n \right \rceil$ because every term of the form $1+\frac 1k$ is bounded above by $2$. In particular, for equality to hold, the expansion of the product yielding $n$ may not contain two terms $a, b$ such that $ab < 2$. By the two above observations, it follows that $f(5 \cdot 2^n) = n+3$ and $f(13 \cdot 2^n) = n+5$; the latter follows because the expansion of $13 \cdot 2^n$ contains a $a = \frac{13}{12}$ term or smaller, and there must exist another term $b \neq 2$ or $b \leq \frac 32$. Then $ab < 2$ and it follows $f(13 \cdot 2^n) = n+4$ is impossible. However, $f(xy) = f(65 \cdot 2^{2n}) = 2n+7$, and hence $$f(xy) = 2n+7 < (n+3)+(n+5) < f(x)+f(y).$$

$\textcolor{blue}{\text{Claim} \hspace{0.1cm} f(x) \geq \lceil \log_2 x \rceil}$ This is clearly true as every term in the product is $\leq 1+\frac{1}{1}=2$ $\textcolor{blue}{\text{Claim} \hspace{0.1cm} f(33)<f(3)+f(11)}$ By the previous claim $f(3)\geq 2$ which can be achieved with $f(3)=\left(1+\frac{1}{2}\right)\left(1+\frac{1}{1}\right)$ $f(33)\geq 6$ which can be achieved with $f(3)=\left(1+\frac{1}{32}\right)\left(1+\frac{1}{1}\right)^5$ $f(11)\geq 4$, but as $11$ need to be in the numerator then one terms needs to be $\left(1+\frac{1}{11k-1}\right)$, but $f(11k-1)\geq 4$ and so $f(11)\geq 5$, which is achieved at $f(11)=\left(1+\frac{1}{10}\right)\left(1+\frac{1}{4}\right)\left(1+\frac{1}{1}\right)^3$ So \[6=f(33)<f(3)+f(11)=7\]With this we finish as \[f(2^{2\theta}\cdot 33)=2\theta+f(33)<\theta+f(3)+\theta+f(11)=f(2^\theta\cdot 3)+f(2^\theta\cdot 11)\]