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
timon92
07.04.2021 17:41
This problem was proposed by Burii.
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)$$
phoenixfire
22.04.2021 20:06
We proceed by induction on $n$. For $n = 1$, we need to prove $f(0, 1) \leq 2f(0, 1)$ which is true due to condition $2$. Take $i=j=k=0$ and $l=1$.
Now let $n \geq 2$. Now assume that for every $m \leq n-1$ and every system of numbers $f(i, j)$ that satisfies the conditions of the problem, where $0 \leq i \leq j \leq m$, the problem is satisfied.
Consider the system $f (i, j)$, $1 \leq i \leq j \leq n$ that satisfies the conditions. We need to prove that $$f (0, n) \leq 2\sum_{k=1}^n{f(k-1,k)}.$$Now we have $f(k-1,k) \leq \sum_{k=1}^n{f(k-1,k)}$ for $1 \leq k \leq n$. Now we condiser cases.
Case 1: $f(0, 1) > \frac{\sum_{k=1}^n{f(k-1,k)}}{2}$.
Then $$f(0,n) \leq 2\max{\{f(0,0), f(0,1), f(1,n)\}}=2\max{\{f(0,1), f(1,n)\}}.$$We have $f (0, 1) \leq \sum_{k=1}^n{f(k-1,k)}$. Also, $$\sum_{k=2}^n{f(k-1,k)}=\sum_{k=1}^n{f(k-1,k)}-f(0,1) < \frac{\sum_{k=1}^n{f(k-1,k)}}{2},$$therefore by the inductive hypothesis on $f(i +1, j + 1)$, $0 \leq i \leq j \leq n - 1$ we get $$f(1,n) \leq 2 \sum_{k=2}^{n}{f(k-1,k)}<\sum_{k=1}^n{f(k-1,k)}.$$Thus we are done.
Case 2: $f(0,1) \leq \frac{\sum_{k=1}^n{f(k-1,k)}}{2}$.
Then we have $$\sum_{k=1}^{t}f(k-1,k)\leq\frac{\sum_{k=1}^n{f(k-1,k)}}{2}\leq \sum_{k=t}^{n-1}{f(k-1,k)}$$for some $1 \leq t \leq n-1$. Thus we only need prove that $$f(0,t) \leq \sum_{k=1}^n{f(k-1,k)} \textrm{ and } f(t+1,n) \leq \sum_{k=1}^n{f(k-1,k)}$$as $$f(0,n) \leq 2 \max(\{f(0,t),f(t,t+1), f(t+1,n)\}) \leq 2S.$$
Now if $t=n-1$, then we only need prove that $$f(0,n-1) \leq \sum_{k=1}^n{f(k-1,k)}$$but this follows from the inductive hypothesis on $f(i,j)$ for $1 \leq i \leq j \leq n-1$.
Now we need to check this for $t \leq n-2$. Now we apply the inductive hypothesis on $f(i,j)$ for $0 \leq i \leq j \leq t$ and we get $$f(0,t) \leq 2\sum_{k=1}^{t}{f(k-1,k)} \leq \sum_{k=1}^n{f(k-1,k)}.$$
And finally we apply the inductive hypothesis on $f(i+t+1, j+t+1)$ for $0 \leq i \leq j \leq n-(t+1)$ and we get
\[
\begin{aligned}
f(t+1,n) &\leq 2\sum_{k=(t+1)+1}^{n}{f(k-1,k)}\\ &=2\sum_{k=1}^n{f(k-1,k)}-2\sum_{k=1}^{t+1}{f(k-1,k)}\\
&\leq \sum_{k=1}^n{f(k-1,k)}\\
\end{aligned}
\]
Hope this is correct.
Dianademon
29.06.2021 07:53
phoenixfire wrote:
We proceed by induction on $n$. For $n = 1$, we need to prove $f(0, 1) \leq 2f(0, 1)$ which is true due to condition $2$. Take $i=j=k=0$ and $l=1$.
Now let $n \geq 2$. Now assume that for every $m \leq n-1$ and every system of numbers $f(i, j)$ that satisfies the conditions of the problem, where $0 \leq i \leq j \leq m$, the problem is satisfied.
Consider the system $f (i, j)$, $1 \leq i \leq j \leq n$ that satisfies the conditions. We need to prove that $$f (0, n) \leq 2\sum_{k=1}^n{f(k-1,k)}.$$Now we have $f(k-1,k) \leq \sum_{k=1}^n{f(k-1,k)}$ for $1 \leq k \leq n$. Now we condiser cases.
Case 1: $f(0, 1) > \frac{\sum_{k=1}^n{f(k-1,k)}}{2}$.
Then $$f(0,n) \leq 2\max{\{f(0,0), f(0,1), f(1,n)\}}=2\max{\{f(0,1), f(1,n)\}}.$$We have $f (0, 1) \leq \sum_{k=1}^n{f(k-1,k)}$. Also, $$\sum_{k=2}^n{f(k-1,k)}=\sum_{k=1}^n{f(k-1,k)}-f(0,1) < \frac{\sum_{k=1}^n{f(k-1,k)}}{2},$$therefore by the inductive hypothesis on $f(i +1, j + 1)$, $0 \leq i \leq j \leq n - 1$ we get $$f(1,n) \leq 2 \sum_{k=2}^{n}{f(k-1,k)}<\sum_{k=1}^n{f(k-1,k)}.$$Thus we are done.
Case 2: $f(0,1) \leq \frac{\sum_{k=1}^n{f(k-1,k)}}{2}$.
Then we have $$\sum_{k=1}^{t}f(k-1,k)\leq\frac{\sum_{k=1}^n{f(k-1,k)}}{2}\leq \sum_{k=t}^{n-1}{f(k-1,k)}$$for some $1 \leq t \leq n-1$. Thus we only need prove that $$f(0,t) \leq \sum_{k=1}^n{f(k-1,k)} \textrm{ and } f(t+1,n) \leq \sum_{k=1}^n{f(k-1,k)}$$as $$f(0,n) \leq 2 \max(\{f(0,t),f(t,t+1), f(t+1,n)\}) \leq 2S.$$
Now if $t=n-1$, then we only need prove that $$f(0,n-1) \leq \sum_{k=1}^n{f(k-1,k)}$$but this follows from the inductive hypothesis on $f(i,j)$ for $1 \leq i \leq j \leq n-1$.
Now we need to check this for $t \leq n-2$. Now we apply the inductive hypothesis on $f(i,j)$ for $0 \leq i \leq j \leq t$ and we get $$f(0,t) \leq 2\sum_{k=1}^{t}{f(k-1,k)} \leq \sum_{k=1}^n{f(k-1,k)}.$$
And finally we apply the inductive hypothesis on $f(i+t+1, j+t+1)$ for $0 \leq i \leq j \leq n-(t+1)$ and we get
\[
\begin{aligned}
f(t+1,n) &\leq 2\sum_{k=(t+1)+1}^{n}{f(k-1,k)}\\ &=2\sum_{k=1}^n{f(k-1,k)}-2\sum_{k=1}^{t+1}{f(k-1,k)}\\
&\leq \sum_{k=1}^n{f(k-1,k)}\\
\end{aligned}
\]
Hope this is correct. i think you are incorrect.
phoenixfire
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.
Dianademon
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.
square_root_of_3
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.
Piortek
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.