Let $n$ be an integer. For pair of integers $0 \leq i,$ $j\leq n$ there exist real number $f(i,j)$ such that: 1) $ f(i,i)=0$ for all integers $0\leq i \leq n$ 2) $0\leq f(i,l) \leq 2\max \{ f(i,j), f(j,k), f(k,l) \}$ for all integers $i$, $j$, $k$, $l$ satisfying $0\leq i\leq j\leq k\leq l\leq n$. Prove that $$f(0,n) \leq 2\sum_{k=1}^{n}f(k-1,k)$$
Problem
Source: Polish Mathematical Olympiad finals 2021 P2
Tags: function, Functional inequality
07.04.2021 17:41
This problem was proposed by Burii.
13.04.2021 10:26
In the statement it should be $$f(0,n) \leq \textcolor{red}{2}\sum_{k=1}^{n}f(k-1,k)$$
22.04.2021 20:06
Hope this is correct.
29.06.2021 07:53
phoenixfire wrote:
Hope this is correct. i think you are incorrect.
29.06.2021 08:18
Dianademon wrote: i think you are incorrect. It would interest me to know what you feel I have done incorrectly.
29.06.2021 14:36
phoenixfire wrote: Dianademon wrote: i think you are incorrect. It would interest me to know what you feel I have done incorrectly. Ok,when you use inductive hypothesis,that should be f(0,n-1) instead of f(1,n).In other words, I think induction should not be able to solve this problem.
12.06.2022 00:57
We induct on $n$. Case $n=1$ is obvious. Suppose the claim is true for all $j<n$ for some $n \geq 2$. Suppose the claim is not true for $n$. Suppose $f(0,n) \leq 2 f(0,k)$ and $f(0,n) \leq 2f(k,n)$ for some $k \in \{1,\ldots, n-1\}$. Then also $f(0,n) \leq f(0,k)+f(k,n)$. However, by inductive hypothesis we have $f(0,k) \leq 2f(0,1)+2f(1,2)+\ldots+2f(k-1,k)$, and $f(k,n) \leq 2f(k,k+1)+2f(k+1, k+2)+\ldots+2f(n-1,n)$, and we reach a conradiction and we're done. Thus, for every $k$, either $2f(0,k)<f(0,n)$ or $2f(k,n)<f(0,n)$. Suppose that $f(0,n) \leq 2f(0,k)$ for some $1 \leq k \leq n$. Note that $f(0,n) \leq 2 \max \{f(0, k-1), f(k-1, k), f(k, n)\}$. If the maximum out of those three numbers is $f(k,n)$, we reach a contradiction since then $f(0,n) \leq 2f(0,k)$ and $f(0,n) \leq 2f(k,n)$. If the maximum is $f(k-1, k)$ we also have an obvious contradiction. Suppose the maximum is $f(0,k-1)$. Then $f(0,n) \leq 2f(0,k-1)$. we can repeat the argument to get $f(0,n) \leq f(0, k-2)$. Repeating this argument gives us $f(0,n) \leq 2f(0,1)$, which is obviously a contradiction. Thus, the claim also holds for $n$, which completes the inductive step.
30.03.2024 17:29
Lemma: Suppose that a function $f(i,j)$ for $0\leq i \leq j \leq n$ satisfies the conditions in the problem. Then a function $g(i-k,j-k)=f(i,j)$ for $k \leq i \leq j \leq n$ also does. Proof: Obvious. Solution: Proof by induction. For $n=1$ the statement is obvious. Now suppose it is true for all numbers less than $n$ where $n \geq 2$ and all functions satisfying the conditions of the problem the statement is true. Now, we have two cases: Case 1: for some $k \in \left \lbrace 1,...,n \right \rbrace$ there hold inequalities $$f(0,n) \leq 2f(0,k), \quad f(0,n) \leq 2f(k,n).$$Then, by the inductive hypothesis: $$f(0,k) \leq 2(f(0,1)+\cdots+f(k-1,k))$$and by the inductive hypothesis and the lemma for $g(i-k,j-k)=f(i,j)$: $$f(k,n)=g(0,n-k) \leq 2(g(0,1)+\cdots+g(n-k-1,n-k))=2(f(k,k+1)+\cdots+f(n-1,n)).$$Adding those equalities completes the proof. Case 2: for every $k \in \left \lbrace 1,...,n-1 \right \rbrace$ there holds one of the inequalities $$f(0,n) > 2f(0,k) \quad \vee \quad f(0,n) > 2f(k,n).$$ Case 2a: for some $k \in \left \lbrace 1,...,n-1 \right \rbrace$ we have $f(0,n) \leq 2f(0,k)$, let $k$ be minimal such that this holds. Then we get $$f(0,n) \leq 2 \textrm{max} \left \lbrace f(0,k-1), f(k-1,k), f(k,n) \right \rbrace =2f(k-1,k) \leq 2(f(0,1)+\cdots+f(k-1,k)+\cdots+f(n-1,n)),$$because inequalities $f(0,n) \leq 2f(0,k-1)$ or $f(0,n) \leq 2f(k,n)$ can't hold. Case 2b: for some $k \in \left \lbrace 1,...,n-1 \right \rbrace$ we have $f(0,n) \leq 2f(k,n)$, let $k$ be maximum such that this holds. Then we get $$f(0,n) \leq 2 \textrm{max} \left \lbrace f(0,k),f(k,k+1),f(k+1,n) \right \rbrace = 2f(k,k+1) \leq 2(f(0,1)+\cdots+f(k,k+1)+\cdots+f(n-1,n),$$because inequalities $f(0,n) \leq 2f(k+1,n)$ or $f(0,n) \leq 2f(0,k)$ can't hold. Case 2c: for every $k$ we get $f(0,n) > 2f(0,k) \quad \wedge \quad f(0,n) > 2f(k,n)$. Then $$f(0,n) \leq 2\textrm{max} \left \lbrace f(0,k),f(k,k),f(k,n) \right \rbrace =2f(k,k)=0 \leq 2(f(0,1)+\cdots+f(n-1,n))$$and we are done.