The source of this problem is USAMO 2000 #1

USAMO2000#1 has much more meaning than unknown .

hmm, it rather too easy for USAMO , is it round 1 ?

harazi posted a generalization in the "Real Analysis" section, with $|x-y|$ replaced by $|g(x)-g(y)|$, the conclusion being that $g$ must be constant. Try searching, there's a solution there.

We prove by induction that if a very convex function $f$ exists, then \[\displaystyle \frac{f(x)+f(y)}{2} - f\biggl( \frac{x+y}{2} \biggr) \ge 2^n|x-y|\] for all non negative integers $n$. We are given the base case $n=0$; now, if the inequality holds for a given $n$, then for $a,b$ real, \[\displaystyle \frac{f(a)+f(a+2b)}{2} \ge f(a+b)+2^{n+1}|b|,\] \[f(a+b)+f(a+3b) \ge 2(f(a+2b)+2^{n+1}|b|),\] and \[\displaystyle \frac{f(a+2b)+f(a+4b)}{2} \ge f(a+2b)+2^{n+1}|b|,\] Summing the three enqualities and setting $x=a, y=a+4b$ completes the induction. Now we only have to notice that the inequality we have proved cannot hold for all arbitrarily large n.

Yup,gorbber,here is your solution: http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=g%28x%29-g%28y%29&t=43440

Thank you very much.

Notice that we can write $ \frac{d^2 f}{dx^2}$ as \[ \lim_{h \to 0} \frac{\lim_{h \to 0} \frac{f(x+2h)-f(x+h)}{h} - \lim_{h \to 0} \frac{f(x+h)-f(x)}{h}}{h} = \lim_{h \to 0} \frac{f(x+2h)+f(x) - 2f(x+h)}{h^2} \ge \lim_{h \to 0} \frac{|h|}{h^2} = \infty\] where the operations (i.e. taking the two h's to be the same) can be justified by uniform convergence. This would only work if $ f$ is twice-differentiable, but I wonder whether there is some way to rigorize this idea?

Can somebody rate/give comments on my solution?

@ Brut: I think your solution is valid.

So your proof is better than a 'proof by example' in that it's a 'proof by lots of examples'?

CatalystOfNostalgia wrote: So your proof is better than a 'proof by example' in that it's a 'proof by lots of examples'? I don't see what you're talking about. If you're getting that impression that I drew specific graphs when coming up with my solution, you are mistaken. Rather, I drew arbitrary concave and convex graphs as I explained above. I was trying to take a more graphical approach. Otherwise, do you care to do something more constructive than make a sarcastic remark?

"Drawing an arbitrary convex function"? Erm, I don't think that's possible. His comment on your solution has merit, despite being somewhat sarcastic. You need to show that the problem is true for any $ f$, and I don't think a purely graphical approach is going to get you to that point.

MellowMelon wrote: "Drawing an arbitrary convex function"? Erm, I don't think that's possible. His comment on your solution has merit, despite being somewhat sarcastic. You need to show that the problem is true for any $ f$, and I don't think a purely graphical approach is going to get you to that point. I understand what you're saying. I guess my underlying reasoning for the graphical approach is as follows: a function can either be convex, concave, or neither, and the graphs of all three categories have particular properties common to all graphs of those types, as given by their definitions (e.g. what does it mean for a graph to be concave/convex?) I was trying to make use of those properties by considering a completely generic concave/convex function (similar to dealing with the graph of the parabola y=x^2 when you are trying to derive general results for parabolas). Then again, I was merely experimenting, so its perfectly reasonable that my approach makes use of skewed logic. I would just like to make sure I see where I go wrong.

mihail911 wrote: convex, concave, or neither, Evidentally, but such a categorization is not going to help: there's no reason to believe $ f$ is smooth, or even anywhere continuous, etc, .. graphing is a first step towards gaining some intuition about the problem, but a statement like "that this is clearly true" clearly [btw, words like "clearly" and "obviously" are almost clearly hand-waving ] lacks justification.

azjps wrote: mihail911 wrote: convex, concave, or neither, Evidentally, but such a categorization is not going to help: there's no reason to believe $ f$ is smooth, or even anywhere continuous, etc, .. graphing is a first step towards gaining some intuition about the problem, but a statement like "that this is clearly true" clearly [btw, words like "clearly" and "obviously" are almost clearly hand-waving ] lacks justification. Thanks, that makes a lot of sense.

Hmm, here is a weird solution. Let $ x>0$, and assume we have a very convex function $ f(x)$. Plugging in $ (x,-x)$ gives $ f(x)+f(-x)\ge2f(0)+4x$. Plugging in $ (x,0)$ gives $ f(\dfrac{x}{2})\le\dfrac{1}{2}f(x)+\dfrac{1}{2}f(0)-x$. Plugging in $ (-x,0)$ gives $ f(-\dfrac{x}{2})\le\dfrac{1}{2}f(x)+\dfrac{1}{2}f(0)-x$. Adding the last two gives $ f(\dfrac{x}{2})+f(-\dfrac{x}{2})\le f(x)+f(0)-2x$. We will prove by induction that $ f(x)+f(-x)\ge2f(0)+4kx$ for all $ k\in\mathbb{N}$. The base case, $ k=1$, is clear from the first line. Assume it's proven for $ k$. Plugging in $ \dfrac{x}{2}$ into the inductive hypothesis gives $ f(\dfrac{x}{2})+f(-\dfrac{x}{2})\ge2f(0)+2kx$. But combining this with the fourth line, we have $ 2f(0)+2kx\le f(\dfrac{x}{2})+f(-\dfrac{x}{2})\le \dfrac{1}{2}(f(x)+f(-x)+f(0)-2x$, and ignoring the expression in the middle we get that $ f(x)+f(-x)\ge2f(0)+2(2k+2)x=2f(0)+4(k+1)x$, completing the induction. To finish, plug in $ x=1$ and we see that $ f(1)+f(-1)\ge2f(0)+4kx$, and since $ f(0),f(-1),f(1)$ are constants (given a very convex $ f(x)$), we can take an arbitrarily large $ k$ such that the inequality becomes reversed, a contradiction. Thus a very convex function cannot exist.

Here is my proof (a bit lacking in the detail...) Let $ x_k=\frac{k}{2N}(b-a)+a$ where $ b\ge a$. Then $ x_{k+1}=2x_k-x_{k-1}$. Let $ a_k=f(x_k)$. Let $ d=\frac{2(b-a)}{N}$. Easily, we get $ (a_2-2a_1+a_0)\ge d$ $ 2(a_3-2a_2+a_1)\ge 2d$ ... $ N(a_{N+1}-2a_N+a_{N-1})\ge Nd$ $ N(a_{N+2}-2a_{N+1}-a_{N})\ge Nd$ ... $ a_{2N}-2a_{2N-1}+a_{2N-2}\ge d$ Summing, we get $ a_{2N}-2a_{N}+a_0\ge (N)(N+1)d$ or $ f(a)-2f\left(\frac{a+b}{2}\right)+f(b)\ge 2(N+1)(b-a)$ but this obviously cannot hold if we fix $ a,b$ and increase $ N$.

There's a cool solution that uses tiny differences, such as in calculus when you calculate areas or derivatives by the limit. It results in the same inequality as catalyst's as you'll see. Suppose for all $ i$ that $ \Delta i=f\left(\frac{i}{n}\right)-f\left(\frac{i-1}{n}\right)$ We also have that $ f\left(\frac{i}{n}\right)+f\left(\frac{i+2}{n}\right)\ge 2f\left(\frac{i+1}{n}\right)+\frac{4}{n}$ Which gives us $ f\left(\frac{i+2}{n}\right)-f\left(\frac{i+1}{n}\right) \ge f\left(\frac{i+1}{n}\right)-f\left(\frac{i}{n}\right)+\frac{4}{n}$. In other terms, $ \Delta (i+1)\ge \Delta i +\frac{4}{n}$ If we use this inequality for $ n$ consecutive values of $ i$, we have that $ \Delta (i+n) \ge \Delta i +4$ Now sum this for $ i=[1,n]$ to obtain $ f(2)-f(1)\ge f(1)-f(0)+4n$. Clearly this cannot hold true for all $ n$ and thus we are done.

A solution possibly identical to one of the users above (edit: seems similar to calc rulz's)

I found this solution by graphing...so graphing still has its merit?

Brut3Forc3 wrote: Can somebody rate/give comments on my solution?

Apologies for reviving, but I'm not sure if the last statement is necessarily true, because if n grows arbitrarily large, then $ g(\frac {x}{2^n})$ can also grow arbitrarily "small", so that the inequality is not necessarily violated. Or am I missing something?

I don't think you're missing anything; I think a few more details should have been given more details as to how the problem is finished from there. Anyway, here's how I'd finish it (hopefully I didn't mess up somewhere): From $ \frac {g(x)}{2} \geq 2^k g(\frac {x}{2^{k + 1}}) + |(k + 1)x|$, we have that $ g(\frac {1}{2^{k + 1}})$ must be negative for sufficiently small $ k$, or else $ g(1) = 2^k g(\frac {1}{2^{k + 1}}) + |(k + 1)| \geq |(k + 1)|$, which is unbouded. Setting $ x = - 1$ tells us that $ g(\frac { - 1}{2^{k + 1}})$ must be negative for sufficiently large $ k$. Hence, there is some $ y$ such that $ g(y)$ and $ g( - y)$ are both negative (pick some sufficiently large $ k$ such that $ g(\frac { - 1}{2^{k + 1}}) < 0$ and $ g(\frac {1}{2^{k + 1}) < 0}$.) But then, $ 0 > \frac {g(y) + g( - y)}\geq g(0) + |y - ( - y)| = |2y| \geq 0$, a contradiction.

CatalystOfNostalgia wrote: Plugging in $ (-x,0)$ gives $ f(-\dfrac{x}{2})\le\dfrac{1}{2}f(x)+\dfrac{1}{2}f(0)-x$. Adding the last two gives $ f(\dfrac{x}{2})+f(-\dfrac{x}{2})\le f(x)+f(0)-2x$. Flipped some signs here, but it seems to just be a typo (the induction is still correct).

This took me far longer than it should have D:

Does the following solution work?

mishai wrote: Does the following solution work?

It's not valid --- you can't take the derivative of $f$ without first having shown its differentiable. Unfortunate this is probably about as hard as the original problem. Asa rule of thumb, for 99% of Olympiad functional equations, derivatives/continuity type arguments won't help unless they're given conditions.

Very similar to some of the above.

We wish to prove by induction that, $$\frac{f(x)+f(y)}{2} \geq f(\frac{x+y}{2})+2^n|x-y| \quad \forall n \in \mathbb{N}_0$$The base case $n=0$ is our question statement. Inductively, $\frac{f(x)+f(y)}{2} \geq f(\frac{x+y}{2})+2^n|x-y|$. Let's call this assertion $P(x,y)$. $P(a,a+2b) \implies \frac{f(a)+f(a+2b)}{2} \geq f(a+b)+2^n|2b| = f(a+b)+2^{n+1}|b| $ $P(a+2b,a+4b) \implies \frac{f(a+2b)+f(a+4b)}{2} \geq f(a+3b)+2^n|2b| = f(a+3b)+2^{n+1}|b| $ $P(a+b,a+3b) \implies f(a+b)+f(a+3b) \geq 2f(a+2b)+2^{n+1}|2b| = 2f(a+2b)+2^{n+2}|b| $ Summing up this three inequalities, we get $\frac{f(a)+f(a+4b)}{2} \geq f(a+2b)+|b|(2^{n+1}+2^{n+1}+2^{n+2}) = f(a+2b)+2^{n+3}|b| = f(a+2b)+2^{n+1}|4b|$ Taking $x=a,y=a+4b$ completes our induction. Now $n$ can be arbitrarily large. So no such function exists.

I saw many calculus attempts in the above posts. As mentioned, they all have a flaw - the function may not be smooth, it may not have a derivative. Strictly speaking, it's true of course. But, you konow, this function is not a random one, it's convex. Those functions are very good ones, they have derivatives almost everywhere (moreover they have derivatives everywhere except at countable many points) and can be represented as $$f(x)=f(a)+\int_a^x f'(t)\,dt$$as being absolutely continuous. $f'(t)$ is defined almost everywhere and is non decreasing. This property is enough to conclude $$f(x+2h)+f(x)-2f(x+h)=o(h)$$as it was (non rigorously) pointed out in #11. Let's see why it holds. \begin{align*} \displaystyle f(x+2h)+f(x)-2f(x+h)&=f(x)+\int_x^{x+2h} f'(t)\,dt +f(x)-2f(x)-2\int_x^{x+h} f'(t)\, dt\\ &=\int_x^{x+2h} f'(t)\,dt - 2\int_x^{x+h} f'(t)\, dt\\ &=\int_{x+h}^{x+2h} f'(t)\,dt - \int_x^{x+h} f'(t)\, dt\\ &=\int_{x}^{x+h} f'(t+h)-f'(t) \,dt \end{align*}Since $ f'(t)$ is non decreasing, for any $t\in [x,x+h]$ we have: $$\displaystyle 0\le f'(t+h)-f'(t)\le \max_{u\in[x,x+2h]} f'(u)-\min_{u\in[x,x+2h]} f'(u)\le |f'(x+2h)-f(x)|$$Hence $$\displaystyle |f(x+2h)+f(x)-2f(x+h)|\le h|f'(x+2h)-f'(x)|$$Now, since $f'(x)$ in non decreasing it's continuous everywhere except on a countable set. It's enough to take a point $x$ where $f'$ is continuous and get $$\displaystyle \lim_{h\to 0}\frac{|f(x+2h)+f(x)-2f(x+h)|}{h}=0$$which contradicts to the initial condition imposed on $f$. EDIT. There is an issue with this solution. I somehow presumed the function was convex. But nothing is stated about $f$ except that so called very convex condition. Of course, $f$ is mid-point convex, but it's not enough to conclude it's convex. There are pathological counterexamples, for example via Hamel bases we could construct a "bad" solution of the Cauchy functional equation and the same function would be mid-convex but not convex. If additionally, we know $f$ is continuous (or even bounded, or even measurable), the convexity follows. Fortunately, in our case it can be fixed. Note that mid-point convexity implies $f$ is convex in the set $D$ of dyadic rational points, i.e. the points $\frac{k}{2^{\ell}}, k,\ell\in\mathbb{Z}.$ It's not difficult to obtain that the restiction of $f$ over $D$ can be extended to a continuous and convex function $\tilde{f}$ over $\mathbb{R}$ with $f(x)=\tilde{f}(x),\forall x\in D$. Since $D$ is dense in $\mathbb{R},$ the extra convex condition over $D$ implies $\tilde{f}$ is extra convex too. That's why, we can already apply the above argument to $\tilde{f}$ and get contradiction. I edited it here

Here is another solution. Fix some $h>0$ and consider the points $x_j=x_0+j\cdot h, j=0,1,\dots,n+1$ where $x_0\in\mathbb{R}, n\in\mathbb{N}$. Applying the given condition to $x=x_0+jh, y=x_0+(j+2)h$ yields $$\Delta^2_h f(x_j):=f(x_j)+f(x_{j+2})-2f(x_{j+1})\ge 4h \quad (1)$$The above notation follows the notation of corresponding finite difference of 2nd order. Note that $$\Delta^2_h f(x_j)=\Delta_h f(x_{j+1})-\Delta_h f(x_j)=(f(x_{j+2})-f(x_{j+1}))-(f(x_{j+1})-f(x_{j})).$$Hence, we can sum up $(1)$ for $j=0,1,\dots,n-1$ and telescoping it to obtain $$4nh\le \sum_{j=0}^{n-1}\Delta_h^2 f(x_j)=\Delta_hf(x_{n})-\Delta_hf(x_0)$$Putting $x_0=0,h=1/n$ for any $n\in\mathbb{N}$ it yields $$ 4\le \Delta_h f(1)-\Delta_h f(0) \quad (2)$$In case $f$ is continuous it brings us to a straightforward contradiction, since the RHS converges to $0$ as $n\to \infty.$ But, we don't know it a priori, so a few more moves are needed. Note that $f$ is convex on the set $D$ of all dyadic rational numbers $D:=\left\{\frac{k}{2^{\ell}}: k\in\mathbb{Z}, \ell\in \mathbb{N}\right\}.$ It follows (as in the case of the convex functions) the slopes, taken at these points are increasing, i.e. for any $d_1<d_2\le d_3<d_4$ in $D$ we have $$\frac{f(d_2)-f(d_1)}{d_2-d_1}\le \frac{f(d_4)-f(d_3)}{d_4-d_3}$$Thus, it yields $$\frac{f(0)-f(-1)}{1}\le \frac{\Delta_h f(0)}{h}\le \frac{f(2)-f(1)}{1}$$for any $h=2^{-n},n\in\mathbb{N}$. The same is true for $\Delta_hf(1)$ in the place of $\Delta_hf(0)$.Hence $$\max\Big(|\Delta_hf(0)|,|\Delta_hf(1)| \Big)\le C|h|$$for some constant $C>0.$ Using it back in $(2)$ we get contradiction when $h\to 0$.

Note that after shifting the function, we wlog assume that $f(0)=0$. Firstly taking $x\rightarrow 2x$ and $y=0$, then $$f(2x)\geq 2f(x)+4\vert x\vert.\quad (1)$$ Claim. If $f(x)+f(-x)\geq a\vert x\vert$, then we also conclude that $f(x)+f(-x)\geq (a+4)\vert x\vert $. Proof. Now using $(1)$ and the given condition, we obtain that $$f(2x)+f(-2x)\geq 2(f(x)+f(-x))+8\vert x\vert \geq (2a+8)\vert x\vert ,$$hence $f(x)+f(-x)\geq (a+4)\vert x\vert$. By the claim we can take $a$ incredibly large in $f(x)+f(-x)\geq a\vert x\vert$. Fixing $x$, we obtain contradiction.

Let $P(x,y)$ denote the assertion $\frac{f(x)+f(y)}{2} \geq f(\frac{x+y}{2})+|x-y|.$ We claim that there is no such function. WLOG $f(0)=0$ by shifting. $P(x,-x)\implies \frac{f(x)+f(-x)}{2} \geq 2x$ In particular $f(x/2)+f(-x/2)\geq 2x$ by setting $x=x/2.$ $P(x,0)+P(-x,0)\implies \frac{f(x)+f(-x)}{2} \geq f(x/2)+f(-x/2)+2x \geq 4x$ Iterating this $\frac 12 (f(x)+f(-x))\geq 2nx$ for positive integer $n.$ A clear contradiction after fixing $x$ and making $n$ indefinitely large.

For $b\in \mathbb R^+$ define $P(b)$ to be the statement: $(f(x+a)-f(x))-(f(x)-f(x-a))\ge ab$ for all $x\in \mathbb R, a\in \mathbb R^+$ Note that since $(f(x+a)-f(x))-(f(x)-f(x-a))$ is a real number, there exists a maximum value $b$ for which $P(b)$ is true. Now, summing these four expressions up: \begin{align*} 2((f(x+a)-f(x))-(f(x)-f(x-a)))&\ge 2ab \\ (f(x+2a)-f(x+a))-(f(x+a)-f(x))&\ge ab \\ (f(x)-f(x-a))-(f(x-a)-f(x-2a))&\ge ab \\ \end{align*}we get that $(f(x+2a)-f(x))+(f(x)-f(x-2a))\ge 4ab$, or $P(2b)$ to be exact. Since $P(b)\implies P(2b)$, $P(4)$ implies that $P(b)$ is true for infinitely large $b$, contradiction.

Nice problem

Since "very convex"ness does not care about shifting, WLOG $f(0)=0.$ Then, let $f(1)=c$. Claim: $$f(\frac{1}{2^n})\leq \frac{c}{2^n}-\frac{n}{2^{n-1}}$$for nonnegative integers $n$. We will use induction. Clearly this is true for $n=0$. We will use induction. Letting $x=\frac{1}{2^n}$ and $y=0$ we have $$f(\frac{1}{2^{n+1}})\leq \frac{f(\frac{1}{2^{n}})}{2}-\frac{1}{2^{n}}\leq \frac{c}{2^{n+1}}-\frac{(n+1)}{2^n},$$which completes the induction. Similarly, if we let $d=f(-1)$, $$f(-\frac{1}{2^n})\leq \frac{d}{2^n}-\frac{n}{2^{n-1}}.$$Now, if we plug in $x=\frac{1}{2^n}$ and $y=-\frac{1}{2^n}$, we get $$\frac{f(1/2^n)+f(-1/2^n)}{2}\geq 0+\frac{1}{2^{n-1}}.$$Thus, from the two above claims, we have $$\frac{c}{2^{n+1}}+\frac{d}{2^{n+1}}-\frac{n}{2^{n-1}}\geq \frac{1}{2^{n-1}},$$which is just $$c+d-4n\geq 4,$$which is clearly a contradiction for sufficiently large $n$, QED.

Consider the second derivative of $f$. We claim that $f''(x) \geq C$ for some positive constant $C$. This proves that the function is impossible because we would have it define two values. We can see that we have \[\frac{f(x+n) + f(x)}{2} \geq f \left( \frac{2x+n}{2} \right) + n\]. Thus we can see that over each infinitessimaly small segment of length $n$ (we choose $n$ so that $f$ is effectively linear). Notice that we must pass through the point that is $n$ units down from the midpoint of this segment (it's also perpendicular). This means that the second derivative is always greater than that constant. Note: in fact if we were to try to draw this function according to the second derivative definition, it would be a dot. $\blacksquare$ I think this should work but I am not sure

Second derivative? You even don't know if the first derivative exists!? And it may not, at least at lot of points, see #34.

Before we begin, we note that for a function $f$, the very convex condition is equivalent to $f(x)+f(y)\ge 2f(\tfrac{x+y}{2}) + 2|x-y|$, which will be used extensively below. Assume the contrary, that there exists a very convex function $f$. Proceeding under this assumption, we now prove two claims. Claim: The function $g(x)=f(x)+f(-x)$ is very convex, and achieves its minimum value at $x=0$. Proof: We have that \begin{align*} g(x)+g(y) &= f(x)+f(y)+f(-x)+f(-y) \\ &\ge 2 f(\tfrac{x+y}{2}) + 2f(\tfrac{-x-y}{2}) + 2|x-y| \\ &= 2g(\tfrac{x+y}{2}) + 2|x-y|,\end{align*}so $g$ is very convex. Also, $g(x) = f(x)+f(-x) \ge 2f(0) + 2|x| \ge 2f(0)$, so the minimum possible value of $g(x)$ is $2f(0)$, achieved at $x=0$. Consider $g(x)$ now; observe that for any real $c$, the function $g(x)+c$ is also very convex. Thus, define $h(x) = g(x)-g(0)$, which is bounded from below by $0$ and also very convex. We now prove the key, contradictory claim. Claim: For any positive integer $k$, we have $h(x)\ge 2k|x|$. Proof: We proceed by induction. We first prove the claim in the base case, $k=1$. Since $h$ is very convex and bounded below by $0$, we have \begin{align*} h(x) &= h(x)+h(0) \\ &\ge 2h(\tfrac{x}{2}) + 2|x| \\ &\ge 2|x|, \end{align*}as desired. Now, we perform the inductive step. Assume the claim holds when $k=r$, for some integer $r\ge 1$, and we will show it also holds when $k=r+1$. We have \begin{align*} h(x) &= h(x)+h(0) \\ &\ge 2h(\tfrac{x}{2}) + 2|x| \\ &\ge 2\cdot 2r|\tfrac{x}{2}| + 2|x| \\ &= 2(r+1)|x|. \end{align*}This completes the inductive step and the proof. We are now essentially done, since we have shown that for all nonzero $x$, the value of $h(x)$ must be arbitrarily large, and hence not equal to any real value. Thus, our initial assumption that a very convex function $f$ exists must be false. The proof is complete. $\blacksquare$

Suppose, for the sake of contradiction, that such a function exists. Let $P(x,y)$ denote the assertion in the problem. Note that since shifting $f$ by a constant amount doesn't affect the inequality, we may assume WLOG that $f(0) = 0$. Claim: for all positive integers $n$ and positive reals, $f(x) + f(-x) \geq (4n) \cdot x$. Proof: We use induction: Base case: Taking $P(-x,x)$ for a positive real $x$ gives us \[f(x) + f(-x) \geq 2f(0)+ 4x = 4x,\]as claimed. Inductive step: We assume that $f(x) + f(-x) \geq (4n) \cdot x$ for some $n$. Then, summing $P(x,0)$ and $P(-x,0)$ for a positive real gives us \[ f(x) + f(-x) \geq 2f( \tfrac{x}{2} ) + 2 f(- \tfrac{x}{2} ) + 4x \geq (4(n+1)) \cdot x, \]which finishes our inductive step. The claim is nonsense, so we are done.

Solution: