As a remark, David originally proposed this FE with $\mathbb{R}_+$ instead of $\mathbb{N}{}$ which doesn't change the problem too much. Edit: @below trust me, it doesn't change much. Once somebody else posts a solution, I will also post the original submission.

oVlad wrote: As a remark, David originally proposed this FE with $\mathbb{R}_+$ instead of $\mathbb{N}{}$ which doesn't change the problem too much. My solution (which I have yet to verify if its correct or not) uses the well-ordering property of natural numbers, so i'm not too sure it doesnt change it too much.

i sorry in advance for my bad english and no latex. as a new user i am not allowed to add images. also i think my idea maybe works for R+ as well proceeding by contradiction, we can first conclusion that f(x) > x+O(1) for all x by seeing that x+y \ne 2x+f(y) . using this in the original bound we can get f(x) > 2x+O(1). and we can repeat this to get f(x) > 2^k x + O(1). if we make the O(1) bounding more precise we can make it fixed over k and it will solve the problem as f cannot be too big

AshAuktober wrote: Let $f: \mathbb{N} \to \mathbb{N}$ be an arbitrary function. Prove that there exist two positive integers $x$ and $y$ which satisfy $f(x+y) \le f(2x+f(y))$. (Proposed by David Anghel, Romania) This feels funny -- please tell me if something's wrong. We will prove that there are no functions $f: \mathbb{N} \to \mathbb{N}$ satisfying $f(x+y) > f(2x+f(y))$ for all $x,y \in \mathbb{N}$ which immediately proves the conclusion. Let $P(x,y)$ be the assertion of $x$ and $y$ to the given functional inequality. Claim 01. $f(x) \ge x$ for all $x \in \mathbb{N}$. Proof. If there exists $\ell \in \mathbb{N}$ such that $f(\ell) < \ell$, then we may take $P(\ell - f(\ell), \ell)$ and get a contradiction as we will get $f(2\ell - f(\ell)) > f(2 \ell - f(\ell))$. Therefore, we must have $f(x) \ge x$ for all $x \in \mathbb{N}$. Claim 02. For any $k \in \mathbb{N}, x, y \in \mathbb{N}$, we have $f(x+y) > 2^{k}x + f^{k}(y)$. Proof. We'll prove this by induction on $k \ge 1$. The base case $k = 1$ is done above, i.e. $f(x+y) > 2x + f(y)$. Suppose that the statement now holds true for $k = \ell \in \mathbb{N}$, we'll prove this for $k = \ell + 1$. By the inductive hypothesis, we have $f(x+y) > 2^{\ell}x + f^{\ell}(y)$ for any $x,y \in \mathbb{N}$. By plugging in $x := 2x$ and $y := f(y)$, we obtain \begin{align*} f(x+y) &> f(2x + f(y)) \\ &> 2^{\ell}(2x) + f^{\ell}(f(y)) = 2^{\ell + 1}x + f^{\ell + 1}(y) \end{align*}which is what we wanted. This finishes the problem immediately, Using Claim 02 on $y = 1$, we obtain $f(x + 1) > 2^k x + f^k(1) \ge 2^k x + 1$ for any $k \in \mathbb{N}$, which gives us a contradiction. Note. I'm also pretty sure the argument above works all fine in $x,y \in \mathbb{R}^+$ with maybe some minor changes.

[Could be wrong] Assume FtSoC there exists $f$ such that $f(x+y) > f(2x+f(y)) \forall x, y$. Then we get $$f(x+1) > f(2x + f(1)),$$and clearly $x + 1 < 2x + f(1)$. Similarly $$f((2x + f(1) - 1) + 1) > f(4x + 3f(1) - 1)$$and $4x + 3f(1) - 1 > 2x + f(1)$. Continuing similarly for a large enough number of iterations (say $k > f(x+1)$), we obtain a value in the range of $f$ that is at most $f(x+1) - k$, which is impossible as that value is negative and therefore not in $\mathbb{N}$. $\square$

Can you post the other problems?

Mathological03 wrote: Can you post the other problems? feeling too tired but sure, ig I'll post one more today.

GorgonMathDota wrote: This feels funny -- please tell me if something's wrong. [...] Note. I'm also pretty sure the argument above works all fine in $x,y \in \mathbb{R}^+$ with maybe some minor changes. No, it's perfectly fine. This was also the proposer's idea. The ideas in #4 and #6 also look correct. As promised, I'm posting the original submission below - for the problem with $\mathbb{R}_+.$ Solution. Assume, for the sake of contradiction, that $f(x+y)>f(2x+f(y))$ for any $x,y>0$. If there exists $\alpha{}$ such that $\alpha>f(\alpha)$, taking $y=\alpha$ and $x=\alpha-f(\alpha)$ in the latter, we get $f(2\alpha-f(\alpha))>f(2\alpha-f(\alpha))$ which is absurd. Hence, $f(x)\geqslant x$ for any $x$. We will prove inductively that for any integer $n\geqslant 0$ it is true that $f(x)\geqslant 2^nx$. The base case $n=0$ has already been proven, so now assume that the inductive step is true for some $k$. Suppose some $\alpha{}$ satisfies $f(\alpha)<2^{k+1}\alpha$. Let $f(\alpha)=2^{k+1}\alpha-\delta$ with $\delta>0$. Let $y<\min(\alpha,\delta/2^k)$ and $x=\alpha-y$ in our inequality and use the fact that $f(x)\geqslant 2^kx$ to infer \[2^{k+1}\alpha-\delta=f(\alpha-y+y)>f(2(\alpha-y)+f(y))\geqslant 2^{k+1}(\alpha-y)+2^ky,\]so $2^ky>\delta$ which contradicts the size constraint we imposed on $y$. Hence, $f(x)\geqslant 2^{k+1}x$ does hold for any $x$, so the proof of the induction step is complete. But of course, the fact that $f(x)\geqslant 2^nx$ for any $n$ leads to a contradiction, by fixing $x$ and taking $n$ to be large enough. Therefore, we cannot assume that $f(x+y)>f(2x+f(y))$ for any $x,y>0.$ Remark. The problem can be made easier by switching $\mathbb{R}_+$ with $\mathbb{N}{}$. The inductive hypothesis becomes $f(x+1)\geqslant 2^nx+1$ for any integer $n\geqslant 0$. The case $n=0$ is done the same, and going from $k$ to $k+1$ only requires taking $y=1$.

@below 1. Forgot about continuity. Well that renders my solution moot. 2. Yeah, that is fine. I am prolly correct here. 3. And I am back to being wrong.

Anulick wrote: @above Takin $\mathbb{R}^+ \to \mathbb{R}^+$ would actually make it a lot, lot easier. FTSOC, let there be a function such that $f(x+y)>f(2x+f(y))$ for all $x,y \in \mathbb{R^+}$. Taking $\lim_{x \to 0^+}$ will give us $f(y) > f(f(y))$ this implies that the function is strictly decreasing. However, by principal of infinite descent, we will be forced at some point to have $f(k)=0$ which violates the $f: \mathbb{R}^+ \to \mathbb{R}^+$ completing the proof. There's so many things problematic here. 1. How do you know $\lim_{x \to 0^+} f(x+y) = f(y)$ and $\lim_{x \to 0^+} f(2x + f(y)) = f(f(y))$, $f$ is not continuous. 2. Even so, how does $f(y) > f(f(y))$ implies $f$ is strictly decreasing. 3. How can you be forced to have $f(k) = 0$ even assuming you have $f$ is strictly decreasing? Consider the sequence $a_i = \frac{1}{i}$ which I think is a strictly decreasing, but positive sequence and thus I'm not quite sure what you meant by "some point to have $f(k) = 0$"

Pick $a$ such that $f(a)$ is minimal over all $a\geq2$. Then, $x=1$ and $y=a-1$ works.

DottedCaculator wrote: Pick $a$ such that $f(a)$ is minimal over all $a\geq2$. Then, $x=1$ and $y=a-1$ works. Having the solution for $\mathbb{R}_+$ in mind, not seeing this was an incredible blunder from both me and David.

Assume that $f(x+y)>f(2x+f(y))$ $P(2^n,\underbrace{f(\dots f(f}_{n\ \text{times}} (1) \dots ))\implies f(2^n+\underbrace{f(\dots f(f}_{n\ \text{times}} (1) \dots ))>f(2^{n+1}+\underbrace{f(\dots f(f}_{n+1\ \text{times}} (1) \dots ))$ Thus \[f(2)>f(2+f(1))>f(4+f(f(1)))>...\]which is not possible since all functions are postive integers.

Without much modification this can also just be solved on $f \colon \mathbb{R}^+ \to \mathbb{R}$. FTSOC suppose not. Then $x + y = 2x + f(y)$ has no positive real sols, so $f(x) \ge x$. Fix a real $a = 0.1434$. Then once again generate a sequence $a_0 = 100, a_1 = 2(a_0 - a) + f(a), \dots, a_{i+1} = 2(a_i - a) + f(a_i)$. However, it then follows that $a_i$ is unbounded from above while $f(a_i)$ is bounded from above, contradiction.

Here is a cute solution using the restricted domain and codomain condition of $f$. For the sake of contradiction, from now on assume $f(x+y)>f(2x+f(y))$ for every $x,y \in \mathbb{N}$. Denote $P(x,y)$ as the assertion of $f(x+y)>f(2x+f(y))$. Claim 1. $f(y)\ge y \ \forall \ y \in \mathbb{N}$ Proof. Assume there exist $y \in \mathbb{N}$ such that $0<y-f(y)$. From $P(y-f(y),y)$, we get $$f(2y-f(y)) > f(2y-f(y))+1 \Rightarrow 0 > 1$$Impossible, hence $f(y)\ge y \ \forall \ y \in \mathbb{N}$. Claim 2. $f$ is strictly increasing Proof. Using the first claim, from $P(1,y)$ we get $$f(1+y) > f(2+f(y)) \ge 2+f(y) > f(y) \Rightarrow f(y+1) > f(y)$$Since the domain of $f$ is $\mathbb{N}$, $f$ is strictly increasing. Now, since $f$ is strictly increasing, from $P(x,1)$ $$f(x+1) > f(2x+f(1)) \Rightarrow x+1 > 2x + f(1) \Rightarrow 1 > x + f(1) > 1 \Rightarrow 1>1$$Impossible, hence there exist $x,y \in \mathbb{N}$ such that $f(x+y)\le f(2x+f(y))$.

Assume otherwise that $$f(2x+f(y))<f(x+y)$$As we must have $2x+f(y)\neq x+y$, we get that $y\leq f(y)$. We claim that $2^k x-2^k+1\leq f(x)$ which follows by induction $$2^k(2z-1)-2^k+1\leq f(2(z-1)+f(1)) < f((z-1)+1)\Rightarrow 2^{k+1}z-2^{k+1}+1\leq f(z)$$Thus we must have $f\equiv 1$, which clearly fails.

This is really weird. I'm not exactly confident I'm not tripping, but it looks like this argument works fine over $\mathbb{R}^+$ as well. So, assume not then we wish to find all solutions to the functional inequality, \[f(x+y) > f(2x+f(y))\]Let $P(x,y)$ denote the above assertion. Then, we can prove the following claim. Claim : For all $x \in \mathbb{R}^+$, we have that $f(x)\ge x$. Proof : Assume there exists some $x_0 \in \mathbb{R}^+$ such that $f(x_0)< x_0$. Then, $P(x_0-f(x_0),x_0)$ gives us \[f(2x_0-f(x_0))>f(2x_0-2f(x_0)+f(x_0))=f(2x_0-f(x_0))\]which is a very clear contradiction. Thus, there cannot exist such $x_0$ proving the claim. Claim : If $f(x)\ge kx$ for some constant $k$ for all $x \in \mathbb{R}^+$, then $f(x)\ge 2kx$ for all $x \in \mathbb{R}^+$ as well. Proof : Note that, for all pairs of positive reals $x>y$, \[f(x)=f((x-y)+y)> f(2(x-y)+f(y))\ge k(2(x-y)+f(y))=2kx-2ky+kf(y)\ge 2kx-2ky+ky=2kx-ky\]which implies that $f(x)\ge 2kx$ (in case it is unclear, this is because if $f(x)=2kx-\epsilon$ for some positive $\epsilon$, then picking $y<\min{x,\frac{\epsilon}{k}}$ yields a contradiction) as desired. Now, since we already have that $f(x)\ge x$ for all positive reals $x$, via the above claim we have that $f(x)\ge 2^ix$ for any positive integer $i$ which is a very clear contradiction. Thus, no functions satisfying the given inequality exist which finishes the problem.

Suppose that for all integers $x,y$ we have $f(x+y)>f(2x+f(y))$. Then, notice that $f(2x+f(y))>f(2(2x)+f(f(y)))=f(2^2x+f^2(y))$. By induction, we have $$f(x+y)>f(2x+f(y))>f(2^2x+f^2(y))>f(2^3x+f^3(y))>\dots.$$Let $a_k=f(2^k+f^k(1))$, then $a_1>a_2>a_3>\dots$. But this is impossible since a strictly decreasing sequence of positive integers does not exist.