FE Marathon!

For discussing Olympiad Level Algebra (and Inequality) problems
nimon
Posts:8
Joined:Sat Mar 27, 2021 7:30 am
Re: FE Marathon!

Unread post by nimon » Fri Apr 02, 2021 11:13 am

can you suggest me any book for solving this kind of function problem.

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Solution to P24

Unread post by Anindya Biswas » Fri Apr 02, 2021 2:16 pm

~Aurn0b~ wrote:
Tue Mar 30, 2021 11:39 am
$\textbf{Problem 24}$

Find all functions $f : \mathbb{N}\rightarrow \mathbb{N}$ satisfying following condition:
\[f(n+1)>f(f(n)), \quad \forall n \in \mathbb{N}.\]
Warning : Don't click, graphical violence ahead...
We will prove by induction that $f(n)=n$ for all $n\in\mathbb{N}$
  • Induction Hypothesis :
    $f(n)=n$ for all $n\in\{1,2,3,\dots,k\}$ and $1,2,3,\dots,k\not\in S_k=\{f(k+1),f(k+2),f(k+3),\dots\}$
  • Base case :
    Let $S_0=\{f(1),f(2),f(3),\dots\}$ be the range of $f$.
    Let $f(m+1)$ be the least element of the set $S_1=\{f(2),f(3),f(4),\dots\}$
    Since $f(f(m))<f(m+1)$, we conclude $f(f(m))\not\in S_1$. But since $f(f(m))\in S_0$, that means $f(m)=1\Longrightarrow 1\in S_0$.
    $\therefore \min{S_0}=1$. Since $1\not\in S_1, 1\in S_0\setminus S_1\Longrightarrow f(1)=1$.
  • Inductive Step :
    Let's denote the set $S_{i}=\{f(i+1),f(i+2),f(i+3),\dots\}$
    Note that $S_k=\{f(k+1),f(k+2),f(k+3)\dots,\}\subseteq\{k+1,k+2,k+3,\dots\}$ by our induction hypothesis.

    Let $m\in\{k+1,k+2,k+3,\dots\}$ such that $f(m+1)=\min{S_{k+1}}=\min{\{f(k+2),f(k+3),f(k+4),\dots\}}$
    Since $f(m+1)>f(f(m))$, we conclude $f(f(m))\not\in S_{k+1}$. But since $f(f(m))\in S_k$, that means $f(m)=k+1\Longrightarrow k+1\in S_k$
    $\therefore \min{S_k}=k+1$
    We can also see that $k+1\not\in S_{k+1}$. Because, if $k+1\in S_{k+1}$ then $\min{S_{k+1}}=k+1$ which contradicts the fact that there exist a smaller element in $\{k+1,k+2,k+3,\dots\}$ which does not belong to $S_{k+1}$.
    $\therefore k+1\in S_k\setminus S_{k+1}\Longrightarrow k+1=f(k+1)$
So, our claim is proved by mathematical induction. $\text{Q.E.D.}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Problem 25

Unread post by Anindya Biswas » Sat Apr 03, 2021 9:54 pm

Find functions $f:\mathbb{N}\to\mathbb{N}$ such that \[f(n)+f(f(n))+f(f(f(n)))=3n\ \ \ \forall n\in\mathbb{N}\]
Where $\mathbb{N}$ is the set of all positive integers
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Problem 25

Unread post by Asif Hossain » Sat Apr 10, 2021 10:16 pm

Anindya Biswas wrote:
Sat Apr 03, 2021 9:54 pm
Find functions $f:\mathbb{N}\to\mathbb{N}$ such that \[f(n)+f(f(n))+f(f(f(n)))=3n\ \ \ \forall n\in\mathbb{N}\]
Where $\mathbb{N}$ is the set of all positive integers
Again 2 days passed no solution :roll:
Hmm..Hammer...Treat everything as nail

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: Problem 25

Unread post by ~Aurn0b~ » Sat Apr 10, 2021 10:31 pm

Anindya Biswas wrote:
Sat Apr 03, 2021 9:54 pm
Find functions $f:\mathbb{N}\to\mathbb{N}$ such that \[f(n)+f(f(n))+f(f(f(n)))=3n\ \ \ \forall n\in\mathbb{N}\]
Where $\mathbb{N}$ is the set of all positive integers
$\textbf{Solution 25}$
Its ez to see that its an injective function.

Plugging $n=1 \ \Rightarrow \ f(1)+f(f(1))+f(f((1)))=3 \ $ $\Rightarrow f(1)=f(f(1))=f(f(f(1)))=1$

Plugging $n=2 \ \Rightarrow \ f(2)+f(f(2))+f(f((2)))=6 \ $ , As the function is injective, none of the term can be $=1$ [ As an example, if $f(f(2))=1 \Rightarrow f(f(2))=1=f(f(1)) \Rightarrow 2=1$ ]

So these 3 terms have to be at least 2. Therefore,
$f(2)=f(f(2))=f(f(f(2)))=2$,

Going on like this we'll have on every step,
$f(n)=f(f(n))=f(f(f(n)))=n.\blacksquare$

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Problem 25

Unread post by Anindya Biswas » Sat Apr 10, 2021 11:01 pm

~Aurn0b~ wrote:
Sat Apr 10, 2021 10:31 pm
Anindya Biswas wrote:
Sat Apr 03, 2021 9:54 pm
Find functions $f:\mathbb{N}\to\mathbb{N}$ such that \[f(n)+f(f(n))+f(f(f(n)))=3n\ \ \ \forall n\in\mathbb{N}\]
Where $\mathbb{N}$ is the set of all positive integers
$\textbf{Solution 25}$
Its ez to see that its an injective function.

Plugging $n=1 \ \Rightarrow \ f(1)+f(f(1))+f(f((1)))=3 \ $ $\Rightarrow f(1)=f(f(1))=f(f(f(1)))=1$

Plugging $n=2 \ \Rightarrow \ f(2)+f(f(2))+f(f((2)))=6 \ $ , As the function is injective, none of the term can be $=1$ [ As an example, if $f(f(2))=1 \Rightarrow f(f(2))=1=f(f(1)) \Rightarrow 2=1$ ]

So these 3 terms have to be at least 2. Therefore,
$f(2)=f(f(2))=f(f(f(2)))=2$,

Going on like this we'll have on every step,
$f(n)=f(f(n))=f(f(f(n)))=n.\blacksquare$
Yeah, but this last statement can be nicely proven by induction.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: FE Marathon!

Unread post by ~Aurn0b~ » Sun Apr 11, 2021 10:10 am

$\textbf{Problem 25}$

Find all functions $f:\mathbb Z\rightarrow \mathbb Z$ such that, for all integers $a,b,c$ that satisfy $a+b+c=0$, the following equality holds:
\[f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a).\](Here $\mathbb{Z}$ denotes the set of integers.)

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Problem 26

Unread post by Asif Hossain » Tue Apr 27, 2021 10:25 pm

~Aurn0b~ wrote:
Sun Apr 11, 2021 10:10 am
$\textbf{Problem 25}$

Find all functions $f:\mathbb Z\rightarrow \mathbb Z$ such that, for all integers $a,b,c$ that satisfy $a+b+c=0$, the following equality holds:
\[f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a).\](Here $\mathbb{Z}$ denotes the set of integers.)
For the sake to continue the marathon, This is 2012 IMO P4. I am posting the next problem.
Problem 26
Find all functions $f:\mathbb{R} \to \mathbb{R}$ such that $f(x^2-y^2)=xf(x)-yf(y)$
Hmm..Hammer...Treat everything as nail

Zeta
Posts:4
Joined:Fri Mar 18, 2022 2:26 am

Re: FE Marathon!

Unread post by Zeta » Wed Sep 28, 2022 2:47 pm

Let $P(x,y)$ denote the original equation.
$P(0,0)\Rightarrow f(0)=0.$
$P(-x,y)\Rightarrow f(x)=-f(x) \Rightarrow f \text{ is odd.}$
WLOG $x,y \geq 0.$
$P(x,0)\Rightarrow f(x^2)=xf(x) \Rightarrow f(x^2-y^2)=f(x^2)-f(y^2)$
$\Rightarrow f(x^2)=f(x^2-y^2)+f(y^2).$
$\exists z\geq 0: z^2=x \Rightarrow f(x)=f(x-y)+f(y).$
$P(2z,z)\Rightarrow f(2z)=2f(z).$
$P(z+1,z)\Rightarrow f(2z+1)=(z+1)f(z+1)-zf(z).~~~~~(*)$
$P(2z+1,1)\Rightarrow f(2z+1)=f(2z)+f(1)=2f(z)+f(1).$
$P(z+1,1) \Rightarrow (z+1)f(z+1)-zf(z)=(z+1)(f(z)+f(1))-zf(z)=f(z)+(z+1)f(1).$
$(*) \Rightarrow 2f(z)+f(1)=f(z)+(z+1)f(1) \implies f(z)=zf(1) ~~~\forall z\geq 0.$
$f$ is odd give that it holds for all real $z.$
So $\boxed{f(x)=cx},$ where $c=f(1),$ which fits. $\blacksquare$

Post Reply