Skip to main content

Functional Equations 101

Let's get to the math: 

Let there be two sets $X$ and $Y$. A function from $X$ to $Y$ denoted as $f \colon X \to Y$ is assigning a value in $Y$ for every element in $X$. We say that $X$ is the domain of the function $f$ and $Y$ is the range. 

A function $f \colon X \to y$ is said to be injective if $f(x) = f(x^{\prime}) \implies x = x^{\prime}$ To put it in a more abstract way, if there is some $a \in Y$ then there is at most one $b \in X$ such that $f(b) = a$ holds true. 

A function is said to be surjective when for any $a \in Y$ there is at least one $b \in X$ such that $f(b) = a$ holds true. 

A function is bijective if for every $a \in Y$ there is exactly one $b \in X$ such that $f(b) = x$. Bijective functions are basically functions which are both injective and surjective. 

Bonus: A function $f \colon X \to X$ is known as an involution if $f(f(x)) = x \; \forall  x \in X$ 
As an exercise, the readers should try to prove that every function that is an involution is a bijective function as well.  

Let's look at some problems now: 

Problem 1: (IMO 2019) Let $\mathbb{Z}$ be the set of integers. Determine all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that, for all integers $a$ and $b$, $$f(2a)+2f(b)=f(f(a+b)).$$

Solution: The answers are $f(x)=0$ and $f(x)=2x+d$ for some $d$. 
Note that $$f(2)+2f(b) = f(f(b+1)) = f(0)+2f(b+1) \implies f(b+1)-f(b)=\frac{f(2)-f(0)}{2}.$$ This means $f$ is linear, so let $f(x)=cx+d$. We have that $$c(2a)+d+2(cb+d)=c(c(a+b)+d)+d \iff c(2a+2b)+2d = c^2(a+b)+cd,$$ which is true if the coefficients of the monomials line up, or $2c=c^2$ and $cd=2d$. From the first equation, $c=0$ or $c=2$. $c=0$ gives that $d=0$ and the solution $f(x)=0$ and $c=2$ gives that $d$ can be anything and the solution $f(x)=2x+d$. 

Problem 2:: (JMO 2021) Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for positive integers $a$ and $b,$ $$f(a^2 + b^2) = f(a)f(b) \text{ and } f(a^2) = f(a)^2$$

Solution: We claim that $f(x)=1$ is the only solution. Since $f(1^2)=f(1)^2$, this means that $f(1)=1$. We also have $f(1^2+1^2)=f(1)f(1)=1$, so $f(2)=1$. Suppose that there exists another solution. Then, we must have $f(k)\neq1$ for some $k$. Consider the smallest value of $k$. Then, $f(x)=1$ for all $x<k$. We will prove that this is impossible.

Case 1: $k$ is even
Then, substituting $a=2x$ and $b=x^2-1$, we get

$$f((2x)^2+(x^2-1)^2)=f(2x)f(x^2-1)$$
$$f((x^2+1)^2)=f(2x)f(x^2-1)$$
$$f(x^2+1)^2=f(2x)f(x^2-1)$$
$$f(x)^2f(1)^2=f(2x)f(x^2-1)$$
$$f(x)^2=f(2x)f(x^2-1)$$
Now, let $x=\frac k2$. Since $k\geq4$, we have $x\geq2$, so $a,b>0$. Since $x<k$, this gives
$$f(k)f(x^2-1)=1,$$ so since $f(k)$ is a positive integer, this means that $f(k)=1$, which is a contradiction.

Case 2: $k$ is odd
Substituting $a=2x(x+1)$ and $b=(x+1)^2-x^2=2x+1$, we get

$$f((2x(x+1))^2+((x+1)^2-x^2)^2)=f(2x(x+1))f(2x+1)$$
$$f(((x+1)^2+x^2)^2)=f(2x(x+1))f(2x+1)$$
$$f((x+1)^2+x^2)^2=f(2x(x+1))f(2x+1)$$
$$f(x+1)^2f(x)^2=f(2x(x+1))f(2x+1)$$
Now, let $x=\frac{k-1}2$. Since $k\geq3$, we have $x\geq1$, so $x+1<2x+1$ and $a,b>0$. Therefore, we have $$f(2x(x+1))f(k)=1,$$ so $f(k)=1$.

Since $f(x)=1$ obviously works, this means that the only function that satisfies the conditions is $\boxed{f(x)=1}$ for all $x\in\mathbb N$. 


Problem 3: (IMO 2010) Find all function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that for all $x,y\in\mathbb{R}$ the following equality holds:
$$f(\left\lfloor x\right\rfloor y)=f(x)\left\lfloor f(y)\right\rfloor$$ where $\left\lfloor a\right\rfloor $ is greatest integer not greater than $a.$ 

Solution: Let $x=1$. We can see that $$f(y)=f(1)\lfloor f(y)\rfloor.$$ If $f(1)=0$, we know that all $f(y)=0$, which we will check later. Plugging the equation into the original equation, $$f(1)f(\lfloor x\rfloor y)=f(x)f(y).$$ However, if we switched the order of $x$ and $y$, we would get that $$f(\lfloor x\rfloor y)=f(\lfloor y\rfloor x).\; (1)$$ Now, for all $y$ such that $y>0$, plug $$\left(\frac{y}{\lfloor y\rfloor+1},\lfloor y\rfloor +1\right)$$ into (1). We get that $$f(0)=f\left(\left(\lfloor y\rfloor+1\right) x\right)=f(y).$$ This means that $f(y)$ is constant for all nonnegative $y$. For all $y$ such that $y<0$, plug $$\left(\frac{y}{\lfloor y\rfloor-1},\lfloor y\rfloor -1\right)$$ into (1). We get that $$f(0)=f\left(\left(\lfloor y\rfloor-1\right) x\right)=f(y).$$ This means that $f(y)$ is constant for all nonpositive $y$. Therefore, we can conclude that $f(x)$ is constant. The previous $f(x)=0$ also follows this, so just let $f(x)=C$. We have that $C=C\lfloor C\rfloor$, so $C=0$ or $\lfloor C\rfloor=1$. Both of these clearly work, so we have our answer: $f(x)=C$ where $C$ can either be $0$ or have a floor of $1$.

Problem 4: (IMO 2008) Find all functions $ f: (0, \infty) \mapsto (0, \infty)$ (so $ f$ is a function from the positive real numbers) such that
$$ \frac {\left( f(w) \right)^2 + \left( f(x) \right)^2}{f(y^2) + f(z^2) } = \frac {w^2 + x^2}{y^2 + z^2}$$
holds for all positive real numbers $ w,x,y,z,$ satisfying $ wx = yz$

Solution: We claim the only solutions are $f(x)=x$ and $f(x)=\frac1x$.
Plugging in $w=x=y=z$, we get
$$\frac{2f(w)^2}{2f(w^2)}=\frac{2w^2}{2w^2}=1$$
$$f(w)^2=f(w^2)$$
It follows that $f(1)=1$.
In addition, if $wx=yz$, then
$$\frac {f(w^2) + f(x^2)}{f(y^2) + f(z^2) } = \frac {w^2 + x^2}{y^2 + z^2}.$$
Let $ab=cd$. Plugging in $w=\sqrt{a}$, $x=\sqrt{b}$, $y=\sqrt{c}$, $z=\sqrt{d}$, we get
$$\frac {f(a) + f(b)}{f(c) + f(d) } = \frac {a + b}{c + d}.$$
Let $ab=c^2$. Then, we have
$$\frac{f(a)+f(b)}{2f(c)}=\frac{a+b}{2c}$$
$$\frac{f(a)+f(b)}{a+b}=\frac{f(c)}{c}$$
Let $a=1$, $c=\sqrt{b}$, and $b\neq 1$. We get
$$\frac{f(1)+f(b)}{1+b}=\frac{f(\sqrt{b})}{\sqrt{b}}$$
$$\frac{1+f(b)}{1+b}=\frac{f(\sqrt{b})}{\sqrt{b}}$$
$$\frac{(1+f(b))^2}{(1+b)^2}=\frac{f(b)}{b}$$
This is a quadratic in $f(b)$. We can check that $f(b)=\frac1b$ and $f(b)=b$ both satisfy this equation. Since $b\neq 1$, these are distinct, so these are the only solutions, so there are no other possible values of $f(b)$.

Let $c\neq 1$. There are 2 cases.

Case 1: $f(c)=c$
Then, for all $a, b$ such that $ab=c^2$, we have
$$\frac{f(a)+f(b)}{a+b}=\frac{f(c)}{c}=1$$
If $f(a)=a$, then $f(b)=b$.
Assume towards a contradiction that $f(a)=\frac1a$ and $f(b)=\frac1b$. Then,
$$\frac1a+\frac1b=a+b$$
$$\frac{a+b}{ab}=a+b$$
$$ab=1$$
Then, $c=1$, a contradiction. So, we have $f(a)=a$ and $f(b)=b$. So, $f(x)\equiv x$.

Case 2: $f(c)=\frac1c$
Then, for all $a, b$ such that $ab=c^2$, we have
$$\frac{f(a)+f(b)}{a+b}=\frac{f(c)}{c}=\frac1{c^2}=\frac1{ab}$$
$$f(a)+f(b)=\frac{a+b}{ab}=\frac1a+\frac1b$$
If $f(a)=\frac1a$, then $f(b)=\frac1b$. Assume towards a contradiction $f(a)=a$ and $f(b)=b$. Then,
$$a+b=\frac1a+\frac1b$$
$$ab=1$$
Then, $c=1$, a contradiction. so, we have $f(a)=\frac1a$ and $f(b)=\frac1b$. So, $f(x)\equiv \frac1x$.

Problem 5: (Shortlist 2018) Let $\mathbb{Q}_{>0}$ denote the set of all positive rational numbers. Determine all functions $f:\mathbb{Q}_{>0}\to \mathbb{Q}_{>0}$ satisfying $$f(x^2f(y)^2)=f(x)^2f(y)$$ for all $x,y\in\mathbb{Q}_{>0}$

Solution: The answer is $\boxed{f\equiv 1}$, which obviously works.
Let $P(x,y)$ be the assertion. Suppose that $f(1)=c$. Then $P(1,1)$ gives that $f(c^2)=c^3$ and $P(1,c^2)$ gives $f(c^6)=c^5$. But also $P(c^2, 1)$ gives $f(c^6)=c^7$ which implies that $f(1)=1$. Then $P(1, x)$ and $P(x, 1)$ give
$$f(f(x)^2)=f(x)$$
$$f(x^2)=f(x)^2$$
or that $f(x)=f(f(x)^2)=f(f(x))^2$. Then $f(x)$ is a $2^n$th power for arbitrarily large $n$, implying that $\boxed{f\equiv 1}$, and we are done. 

Problem 6: (EGMO 2021) Find all functions $f:\mathbb{Q}\to\mathbb{Q}$ such that the equation
$$f(xf(x)+y) = f(y) + x^2$$ holds for all rational numbers $x$ and $y$.

Solution: Let $P(x,y)$ denote the assertion that $$f(xf(x)+y) = f(y) + x^2.$$

Lemma 1: $f$ is surjective. 
Proof: $P(x,0): f(xf(x))=f(0)+x^2$. 

$P(x,-xf(x)): f(0)=f(-xf(x))+x^2$, so $f(-xf(x))=f(0)-x^2$. 

Thus, by induction, $f(0)+kx^2$ for any integer $k$ is in the image of $f$. 

But note that $\frac{p}{q}=pq\left(\frac{1}{q}\right)^2$, so $f(0)+\frac{p}{q}$ is in the image of $f$, for any integers $p,q$, where $q\ne 0$. 

Thus, any rational number is in the image of $f$. $\blacksquare$

Lemma 2: $f(0)=0$. 
Suppose $f(k)=0$ (a such $k$ must exist as $f$ is surjective). 

$P(k,x): f(x)=f(x)+k^2\implies k=0$. 


Lemma 3: $f(1)=\{-1,1\}$. 
$P(1,0): f(f(1))=1$. 

$P(f(1),0): f(f(1))=f(1)^2$. 

This implies $f(1)^2=1$, which proves our claim. 


Case 1: $f(1)=1$. 
Then $P(1,x): f(x+1)=f(x)+1\implies f(x)=x\forall x\in\mathbb{Z}$. 

We claim that $f(kxf(x))=kx^2$ for all positive integers $k$. 
Proof: We proceed by induction. Setting $y=0$ gives $f(xf(x))=x^2$. Now suppose for all positive integers $l$ less than $k$, $f(lxf(x))=lx^2$. 

$P(x,(k-1)xf(x)): f(kxf(x))=(k-1)x^2+x^2=kx^2$, which completes the induction. 


For any rational $x$, we take a positive integer $k$ so that $kxf(x)$ is an integer (this is obviously always possible). 

So $kxf(x)=kx^2\implies xf(x)=x^2\implies \boxed{f(x)=x\forall x\in\mathbb{Q}}$. 


Case 2: $f(1)=-1$. 
$P(1,x): f(x-1)=f(x)+1$. 

So for all integers $n$, $f(n)=-n$. 

We claim that $kxf(x)=kx^2$ for all positive integers $k$. 
Proof: Same as above case. 


For any given $x$, take a positive integer $k$ so that $kxf(x)$ is an integer. 

Then $-kxf(x)=kx^2\implies -xf(x)=x^2\implies \boxed{f(x)=-x\forall x\in\mathbb{Q}}$

Bratin. 

Comments

Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong