Math Challenge - April 2020

[Infrared]

I still don't understand. What if $x$ is not in such an interval $J$?

And can you address my question about why $f(f(x))>f(x)$?

 

[Adesh]

And can you address my question about why f(f(x))>f(x)f(f(x))>f(x)f(f(x))>f(x)?

Okay, you mean that $f$ may not be defined on $f(x)$ because we assumed only that $f$ on the sub-interval $J$?

 

[Infrared]

Because you're only assuming that $f$ is increasing on the interval $J$. If $f(x)$ is outside of the interval $J$, then $x<f(x)$ does not imply $f(x)<f(f(x))$.

It's not hard to fix this though; $f$. You should say why $f$ must be strictly monotonic on the whole interval, not just on some sub-interval.

 

[julian]

So $f$ is monotonically increasing because of injectivity. Say $f(x)$ intersects the function $x$ at a finite number of points which you use to define sub-intervals. Then $f(x)$ will alternate between convex down and convex up as you pass from one interval to the next. In a convex down interval, $[a,b]$, you arrive at the contradiction that: $c \equiv f(f(f(c))) < c$ for any $c$ such that $a < c < b$. And in an convex up interval, $[p,q]$, you arrive at the contradiction that $r \equiv f(f(f(r))) > r$ such that $p < r < q$.

 

[Infrared]

So $f$ is monotonically increasing because of injectivity.

Or decreasing

Say $f(x)$ intersects the function xx at a finite number of points which you use to define sub-intervals.

There don't have to be only finitely many intersections.

Then $f(x)$ will alternate between convex down and convex up as you pass from one interval to the next.##

Why can't there be mixed concavity on each interval? The points where $f(x)$ changes concavity won't be the same points where $f(x)=x$ in general.

In a convex down interval, $[a,b]$, you arrive at the contradiction that: $c=f(f(f(c)))<c$ for any $c$ such that $a<c<b$ . And in an convex up interval,

I don't see how you are using concavity for this.

@archaic has an almost complete solution.

 

[Adesh]

It's not hard to fix this though; fff. You should say why fff must be strictly monotonic on the whole interval, not just on some sub-interval.

If I prove the monotonicity then how would I ensure that $f$ will be monotone on $f(x)$? I’m thinking of it, I hope shortly I will come up with something.

 

[Infrared]

I'm not sure what you mean by "monotone on $f(x)$", but @Lament gave an argument for why $f$ is (strictly) monotonic on all of $[0,1]$, with some confusion about concavity. See posts 86 and 88.

You can assume that the range of $f$ lies inside of $[0,1]$ since this must be the case for $f(f(f(x)))$ to be defined.

 

[Adesh]

I'm not sure what you mean by "monotone on $f(x)$", but @Lament gave an argument for why $f$ is (strictly) monotonic on all of $[0,1]$, with some confusion about concavity. See posts 86 and 88.

Even if $f$ is monotone, how would I go for proving that $f \circ f$ is also monotone?

 

[Infrared]

If $f$ is increasing, then $f\circ f$ is increasing. If $f$ is decreasing, then $f\circ f$ is increasing.

 

[Adesh]

If $f$ is increasing, then $f\circ f$ is increasing. If $f$ is decreasing, then $f\circ f$ is increasing.

I will prove that part (the implication that $x \lt f(x) \implies f(x) \lt f(f(x))$.

 

[julian]

Or decreasing
There don't have to be only finitely many intersections.Why can't there be mixed concavity on each interval? The points where $f(x)$ changes concavity won't be the same points where $f(x)=x$ in general.I don't see how you are using concavity for this.

@archaic has an almost complete solution.

Increasing because of claim 3 above.

Convex up implies $r \equiv f(f(f(r))) > r$ for $p< r < q$ from attached figure. Seems the only way to not have a contradiction is if $f(x) = x$.

 

[archaic]

9. Let $f:[0,1]\to[0,1]$ be a continuous function such that $f(f(f(x)))=x$ for all $x\in[0,1]$. Show that $f$ must be the identity function $f(x)=x$. (IR)

Saying $f(f(f(x)))=x$ is like saying $f(u\in[0,1])=x$. As such, $f:[0,1]\to[0,1]$ is bijective, and $f(f(x))=f^{-1}(x)$. Repeating this step twice more, we get that:$$f^{-1}(f^{-1}(f^{-1}(x)))=x\Leftrightarrow f(f(f(x)))=f^{-1}(f^{-1}(f^{-1}(x)))$$
Since $f$ is a continuous bijection on $[0,1]$, then it is either strictly decreasing or strictly increasing, the same for its inverse (which has the same direction of variation as $f$).

Suppose that $f$ is not the identity function, then there exists $a\in[0,1]$ such that $f(a)\neq f^{-1}(a)$. Let $f(a)=b$ and $f^{-1}(a)=c$, then:$$f(f(f(a)))=f^{-1}(f^{-1}(f^{-1}(a)))\Leftrightarrow f(f(b))=f^{-1}(f^{-1}(c))$$
Since $f(x)$ and its inverse are bijections, then $f(b)=d\neq f(a)=b$ and $f^{-1}(c)=e\neq f^{-1}(a)=c$.
We get:$$f(f(b))=f^{-1}(f^{-1}(c))\Leftrightarrow f(d)=f^{-1}(e)$$
Let us go back to our original equation and chose $x=a$.
$$f(f(f(a)))=f(f(b))=f(d)=f^{-1}(e)\neq a=f^{-1}(c)$$
That $f^{-1}(e)\neq a$ is because the inverse of $f$ is a continuous bijection and $a=f^{-1}(c)$.
Therefore, $f(x)$ must be the identity function.

 

[Infrared]

Increasing because of claim 3 above.

Convex up implies $r \equiv f(f(f(r))) > r$ for $p< r < q$ from attached figure. Seems the only way to not have a contradiction is if $f(x) = x$.

What is "claim 3"?

I'm still not sure how you're using convexity. Just $f$ being increasing is enough to say that $x<f(x)$ implies $f(x)<f(f(x))$ etc.

 

[Infrared]

@archaic I didn't read your new argument carefully, but it doesn't look like it uses the continuity of $f$, and so it cannot be right. A discontinuous counterexample is: Let $f(x)=x$ except when $x=0,1/2,1$, for which we set $f(0)=1/2, f(1/2)=1,$ and $f(1)=0$. Let me know if you still want me to read through it.

You had everything you needed in your old argument, just needed to clean some things up.

 

[julian]

What is "claim 3"?

I'm still not sure how you're using convexity. Just $f$ being increasing is enough to say that $x<f(x)$ implies $f(x)<f(f(x))$ etc.

@Lament's post #86, claim 3.

I think a combination of convex up in $[p,q]$ + no local maximum anywhere in the interior of $[0,1]$ is enough to say $x<f(x)$ implies $f(x)<f(f(x))$ etc.

 

[Infrared]

Okay, but it still has nothing to do with concavity- only monotonicity. If $f$ is strictly increasing, and $x<f(x)$ for some $x$, then $f(x)<f(f(x))$ and $f(f(x))<f(f(f(x)))=x$, which gives a contradiction. Similarly for the other cases.

 

[archaic]

@archaic I didn't read your new argument carefully, but it doesn't look like it uses the continuity of $f$, and so it cannot be right. A discontinuous counterexample is: Let $f(x)=x$ except when $x=0,1/2,1$, for which we set $f(0)=1/2, f(1/2)=1,$ and $f(1)=0$. Let me know if you still want me to read through it.

You had everything you needed in your old argument, just needed to clean some things up.

I added that it is a continuous bijection. This way you can't chose values as you did; you either chose them to be strictly increasing or strictly decreasing.

 

[Infrared]

Okay, you state that $f$ is strictly monotonic, but where do you use this fact in your proof? It still doesn't seem like your argument relies on it.

 

[archaic]

Okay, you state that $f$ is strictly monotonic, but where do you use this fact in your proof? It still doesn't seem like your argument relies on it.

It maintains the order of the values so that you cannot chose discontinuities like you did.

 

[Infrared]

I understand that, but where in your argument do you use the fact that $f$ is monotonic?

 

[Lament]

You have the right idea here, but the wording is a little off. Your argument that having a maxmum or a minimum contradicts the injectivity of $f$ is good, but concavity doesn't have much to do with it. Being "concave down" does not mean that a maximum is achieved on the interior (e.g. the square root function is concave down, but still strictly increasing on its domain). The last detail that you should check for this argument to be airtight is that a continuous function defined on an interval is either monotonic or has (interior) local extrema.

Yes, I think there is no reason to use concavity here. Here, I modified the Claim 2 according to your suggestion.

Claim 2: Since $f(x)$ is continuous bijection in the domain $[0,1]$, so $f(x)$ is either strictly increasing or strictly decreasing within the interval.
Proof: WLOG, let us consider a small neighbourhood $[a,b]$ around a local extrema $f(c)$ such that $a \lt c \lt b$ (We ensure that each such interval contains only one such extrema). Obviously, $f'(c)=0$. But, then by mean value theorem, $\exists x_1, x_2$ such that $a \lt x_1 \lt c$ and $c \lt x_2 \lt b$, i.e. $x_2 \gt x_1$ but $f(x_2)=f(x_1)$. This is a contradiction, since $f(x)$ is injective. So, a local extrema cannot lie in the interval (a,b). Hence, the local extrema must be at the end-points of the interval,i.e. either $f(b) \gt f(a)$ (strictly monotonically increasing) or $f(b) \lt f(a)$ (strictly monotonically decreasing). The monotonicity is strict because otherwise for some interval $f(x)$ is constant which contradicts the injectiveness of $f(x)$. This result can be extended other adjacent intervals repeatedly.

It is evident that if $f(x)$ is monotonically increasing(or decreasing) in $[a,b]$, then in the next interval $[b,d]$ (say), it cannot become monotonically decreasing(or increasing) because that would imply $f'(x)$ changed signs while we moved from one interval to the next. But that implies that $f'(b)=0$. But our choice of intervals was such that each interval contains only such peak or valley, so a extrema cannot occur at $x=b$ or else we can again squeeze $f(b)$ within some interval and apply the same reasoning as above to conclude $f'(b) \ne 0$.

So, $f(x)$ is either strictly monotonically increasing or strictly monotonically decreasing.

Why are the only three possible cases that f(x)=x,f(x)>xf(x)=x,f(x)>x, and f(x)<xf(x)<x (for all xx)? Why can't it be mixed?

Yes, of course, it can be mixed. My argument can be restated by just dividing the entire intervals into sub-intervals where either $f(x)>x$ or $f(x)<x$, and applying the same argument over the various sub intervals over the entire interval.

I think that solves all the problems. Do I need to post the complete solution again?

 

[fresh_42]

Do I need to post the complete solution again?

This would be very kind of you. It is meanwhile almost impossible to figure out in which post which argument contributes to a possible solution. It is generally best to quote the question and provide a consistent answer. Especially as there are quite a few members involved. E.g. someone used claim 3 of your attempt to argue about his, whereas claim 2 had a flaw. and it is impossible to figure out whether this affected claim 3 etc.
It's a mess.

 

[Adesh]

This would be very kind of you. It is meanwhile almost impossible to figure out in which post which argument contributes to a possible solution. It is generally best to quote the question and provide a consistent answer. Especially as there are quite a few members involved. E.g. someone used claim 3 of your attempt to argue about his, whereas claim 2 had a flaw. and it is impossible to figure out whether this affected claim 3 etc.
It's a mess.

Just a general query, do you people have to search every time who has has answered your question? Because whenever we post a solution we don’t ping (we don’t put @ before anybody’s name) you, QQ or IR. I think it’s a very hard job to come here and search for who has solved your question.

 

[Adesh]

Question 9:

Regarding the monotonicity of $f$, we are given that $$f \left (
f \left (
f(x) \right ) \right) =x $$ for all $x \in [0,1]$. Now, either $f$ is an identity function or $f$ undo the effect of $f \left ( f(x) \right)$, the latter condition implies that $f \left ( f(x) \right)$ is inverse of $f$. Hence, $f$ is inevrtible.

Any function which is invertible (in an interval) is also monotonic in that interval.

 

[Lament]

9. Let $f:[0,1]\to [0,1]$ be a continuous function such that $f(f(f(x)))=x$ for all $x\in [0,1]$. Show that $f$ must be the identity function $f(x)=x.$ (IR)

The question confines itself to $f:[0,1]\to [0,1]$ such that $f(f(f(x)))=x$ for all $x\in [0,1] \Rightarrow f(x)=x$.

However, it can be proved for the general case,i.e. when $f :\mathfrak {R}\rightarrow \mathfrak {R}$ such that $f(f(f(x)))=x$ for all $x\in \mathfrak {R}$, $f(x)=x.$

I prove the general case below :

Spoiler: Question 9 :

Claim 1: $f(x)$ is a bijective mapping.
Proof: To prove $f$ is one-one, assume $$f(x)=f(y)$$
$$\Rightarrow f(f(x))=f(f(y))$$
$$\Rightarrow f(f(f(x)))=f(f(f(y)))$$
$$\Rightarrow x=y$$
So, $f(x)$ is injective.

Now, to prove $f$ is onto, $\forall y \in \mathfrak {R},$ $\exists x \in \mathfrak {R}$ such that $y=f(x)$.
Evidently, if $y\in \mathfrak {R} \text { then } y=f(f(f(y))) \Rightarrow x=f(f(y))\in \mathfrak {R}$
Thus, we can find $s$ such that $$y=f(x)$$
So, $f(x)$ is surjective.

Thus, $f(x)$ is a continuous bijection as the mapping $f :\mathfrak {R}\rightarrow \mathfrak {R}$ is continuous.

Claim 2: Since $f(x)$ is continuous bijection in the domain $[0,1]$, so $f(x)$ is either strictly increasing or strictly decreasing within the interval.

Proof: WLOG, let us consider a small neighbourhood $[a,b]$ around a local extrema $f(c)$ such that $a \lt c \lt b$ (We ensure that each such interval contains only one such extrema). Obviously, $f'(c)=0$. But, then by mean value theorem, $\exists x_1, x_2$ such that $a \lt x_1 \lt c$ and $c \lt x_2 \lt b$, i.e. $x_2 \gt x_1$ but $f(x_2)=f(x_1)$. This is a contradiction, since $f(x)$ is injective. So, a local extrema cannot lie in the interval (a,b). Hence, the local extrema must be at the end-points of the interval,i.e. either $f(b) \gt f(a)$ (strictly monotonically increasing) or $f(b) \lt f(a)$ (strictly monotonically decreasing). The monotonicity is strict because otherwise for some interval $f(x)$ is constant which contradicts the injectiveness of $f(x)$. This result can be extended other adjacent intervals repeatedly.

It is evident that if $f(x)$ is monotonically increasing(or decreasing) in $[a,b]$, then in the next interval $[b,d]$ (say), it cannot become monotonically decreasing(or increasing) because that would imply $f'(x)$ changed signs while we moved from one interval to the next. But that implies that $f'(b)=0$. But our choice of intervals was such that each interval contains only such peak or valley, so a extrema cannot occur at $x=b$ or else we can again squeeze $f(b)$ within some interval and apply the same reasoning as above to conclude $f'(b) \ne 0$.Claim 3: $f(x)$ is strictly increasing.
Proof: Assume on the contrary that f(x) is strictly decreasing, then for
$$y>x \Rightarrow f(y)<f(x)$$
$$\Rightarrow f(f(y))>f(f(x))$$
$$\Rightarrow f(f(f(y)))<f(f(f(x)))⇒y<x$$
a contradiction.
So, $f(x)$ is strictly increasing.

Claim 4: $f(x)$ satisfies the identity relation, i.e., $f(x)=x$
Proof: Suppose $f(x)≠x$, then either $f(x)>x$ or $f(x)<x$ for a certain interval.
As such, the entire interval can be subdivided on the basis of $f(x)>x$ or $f(x)<x$, and for each such interval, we prove that it leads to a contradiction.

Therefore, if in a certain interval,
\begin{equation}f(x)>x\end{equation}
\begin{equation}\Rightarrow f(f(x))>f(x)\end{equation}
\begin{equation}\Rightarrow f(f(f(x)))>f(f(x))\end{equation}
\begin{equation}\Rightarrow x>f(f(x))\end{equation}
From (1), (2) and (4)
$$x>f(f(x))>f(x)>x$$
which is impossible.

Similarly, in another interval if
\begin{equation}f(x)<x\end{equation}
\begin{equation}\Rightarrow f(f(x))<f(x)\end{equation}
\begin{equation}\Rightarrow f(f(f(x)))<f(f(x))\end{equation}
\begin{equation}\Rightarrow x<f(f(x))\end{equation}
From (5), (6) and (8)
$$x<f(f(x))<f(x)<x$$
which is impossible.
Hence,
$$f(x)=x$$ Q.E.D.

 

[fresh_42]

Just a general query, do you people have to search every time who has has answered your question?

If a new post is entered, the alert box says there is. And then we know who posted which question, and at least you guys normally quote the number of the question. The harder part is to edited the "solved by" part, because I link to the solution. Unless someone comes up with a full solution, this will be impossible for revolution no. 9. I need the id number of the post, and I only get it by pressing "reply". But that fills my edit box and if I'm waiting too long, it will be stored automatically, which is annoying for future posts. Unfortunately, the "give credit to" messages from my colleagues don't provide that url or id either. I normally look for a like that might indicate which post is meant to be the solution. So the edit might take some time, especially as I have to wait until the browser interpreted the MathJax code, for otherwise I risk that it will be destroyed.

 

[Lament]

5. For coprime natural numbers $n,m$ show that
$$
m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \operatorname{mod} nm
$$

Edited after comments from @fresh_42

Spoiler: Question 5

Fermat-Euler Theorem states that for every pair of co-prime integers $a$ and $m$, it holds
$$a^{\varphi(m)} \equiv 1 (\operatorname{mod} m)$$ where ${\varphi(m)}$ is the Euler totient function.

Thus, since $n,m$ are co-prime, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1+0 \equiv 1(\operatorname{mod} n)$$
& $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1+0 \equiv 1 (\operatorname{mod} m)$$
This suggests $$n|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$ and $$m|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
Hence, (since if $a|c$ and $b|c$ then $lcm(a,b)|c$. Now, $gcd(a,b)=1 \Rightarrow lcm(a,b)=ab$. Hence, $ab|c$ ) $$mn|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
or equivalently, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \operatorname{mod} nm$$.

 

[fresh_42]

Fermat-Euler Theorem states that for every pair of co-prime integers $a$ and $m$, it holds
$$a^{\varphi(m)} \equiv 1 (\operatorname{mod} m)$$ where ${\varphi(m)}$ is the Euler totient function.

Thus, since $n,m$ are co-prime, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 (\operatorname{mod} n)$$

Easier to read: $m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 + 0 \equiv 1 (\operatorname{mod} n)$

& $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 (\operatorname{mod} m)$$
This suggests $$n|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$ and $$m|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
Hence, (since if $a|c$ and $b|c$ such that $gcd(a,b)=1$, then $ab|c$ ) $$

Here we use $a|c$ and $b|c \Longrightarrow lcm(a,b)|c$ and $lcm=ab$ for $gcd(a,b)=1$.

mn|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
or equivalently, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \operatorname{mod} nm$$.

 

[Infrared]

The question confines itself to $f:[0,1]\to [0,1]$ such that $f(f(f(x)))=x$ for all $x\in [0,1] \Rightarrow f(x)=x$.

However, it can be proved for the general case,i.e. when $f :\mathfrak {R}\rightarrow \mathfrak {R}$ such that $f(f(f(x)))=x$ for all $x\in \mathfrak {R}$, $f(x)=x.$

I prove the general case below :

Thus, $f(x)$ is a continuous bijection as the mapping $f :\mathfrak {R}\rightarrow \mathfrak {R}$ is continuous.

Claim 2: Since $f(x)$ is continuous bijection in the domain $[0,1]$, so $f(x)$ is either strictly increasing or strictly decreasing within the interval.

Proof: WLOG, let us consider a small neighbourhood $[a,b]$ around a local extrema $f(c)$ such that $a \lt c \lt b$ (We ensure that each such interval contains only one such extrema). Obviously, $f'(c)=0$. But, then by mean value theorem, $\exists x_1, x_2$ such that $a \lt x_1 \lt c$ and $c \lt x_2 \lt b$, i.e. $x_2 \gt x_1$ but $f(x_2)=f(x_1)$ This is a contradiction, since $f(x)$ is injective.

It is not given that $f$ is differentiable. The function $f(x)=|x|$ is minimized $0$, but is not differentiable there. Even for differentiable functions, I think your MVT argument is flawed- I can't tell how you're applying MVT, but it looks like you're claiming that any function whose derivative has a zero cannot be injective. The function $f(x)=x^3$ is a counterexample to that. It is also not clear how you can make each interval contain only one such extremum, since in general functions can change monotonicity infinitely often in a finite interval, like $f(x)=x\sin(1/x), f(0)=0$ near $x=0$. Your original argument using the IVT was sound, aside from the concavity language.

Claim 4: $f(x)$ satisfies the identity relation, i.e., $f(x)=x$
Proof: Suppose $f(x)≠x$, then either $f(x)>x$ or $f(x)<x$ for a certain interval.
As such, the entire interval can be subdivided on the basis of $f(x)>x$ or $f(x)<x$, and for each such interval, we prove that it leads to a contradiction.
...

As before, dividing into intervals adds some confusion. Here the problem is less severe because the set where $x\neq f(x)$ is open, so it must contain an interval if it's nonempty, but it's still easier to avoid it: suppose for contradiction that $f(x)\neq x$ for some $x$. Then either $x<f(x)$ or $x>f(x)$, and apply your argument to the point $x$, not to an entire interval.

Any function which is invertible (in an interval) is also monotonic in that interval.

Any continuous invertible function, yes. This is the content of @Lament's claim 2.

 

[Adesh]

Just a general query, do you people have to search every time who has has answered your question? Because whenever we post a solution we don’t ping (we don’t put @ before anybody’s name) you, QQ or IR. I think it’s a very hard job to come here and search for who has solved your question.

Any continuous invertible function, yes. This is the content of @Lament's claim 2.

I can give an informal proof of why an invertible function would be monotonic.
PROOF: Function is invertible implies it is injective, that is it passes horizontal line test for all horizontal lines. That is our function passes every horizontal line just once and this is possible only if it keeps on increasing/decreasing, if it were to change it’s nature, that is from increasing to decreasing (or decreasing to increasing) it would surely intersect at least one horizontal line at least twice and hence will not be injective

Was my proof of “$f$ is invertible” right?