Solving a Short but Nontrivial Introductory Olympiad Problem from China

Introduction

Apparently, my new neighbor in Shanghai is a genius fifth grader who is enrolled in a high school curriculum right now. It should not be too surprising to say that he is preparing for the China Mathematical Olympiad (CMO). Today, he showed me one of his homework problems from his olympiad training class, and I was stumped.

The topic was “Set Theory.” I thought that, surely as a college student, a fifth grader’s set theory problem cannot be difficult?

He pointed at problem 3 on his homework, telling me that this is the first problem he could not solve. He also reminded me that problems 4 through 6 are from the CMO and the IMO, so he also did not solve them (since when are 5th graders solving IMO problems now?).

After staring at the problem for ten minutes, I could not solve the second part of the problem. As a redemption after the embarrassment, I will write up my solution here. Because this problem has so many edge cases and places for mistakes, I will write a fully-rigorous solution.

Oh yeah, this problem reminds me of exactly why I did not do olympiad math in China. If you do enough Gaolian problems, you’ll see some sort of pattern among them… Note that I am not sure about the source of this problem — it looks like the style of a past Gaolian round 2 (China’s equivalent of AIME) exam. Please let me know if you find the source of this problem.

1% Set Theory, 99% Algebra.

Problem

For a given $𝑎\in ℝ$, define $𝑓\left(𝑥\right)=𝑎{𝑥}^2-1$. Define sets $𝐴=\left\{𝑥\in ℝ|𝑓\left(𝑥\right)=𝑥\right\}$ and $𝐵=\left\{𝑥\in ℝ|𝑓\left(𝑓\left(𝑥\right)\right)=𝑥\right\}$.

(a) Prove that $𝐴\subseteq 𝐵$.

(b) Determine, with proof, all possible values of $𝑎$ for which $𝐴=𝐵\ne \varnothing$.

Remark

Part (a) is trivial — it simply tests whether the contestant knows what a subset is.

Part (b)… no idea why this is on the set theory homework. My only bottleneck was the algebra observations.

My Solution

(a) Proof. Let $𝑥\in 𝐴$. Then, $𝑓\left(𝑥\right)=𝑥$, so $𝑓\left(𝑓\left(𝑥\right)\right)=𝑓\left(𝑥\right)=𝑥$, which means $𝑥\in 𝐵$. Therefore, $𝐴\subseteq 𝐵$. $∎$

(b) I claim that the set of all possible values of $𝑎$ is $\left[-\frac{1}{4},\frac{3}{4}\right]$.

Proof. We break the proof down into two claims.

Claim 1: $𝐴\ne \varnothing$ if and only if $𝑎\ge -\frac{1}{4}$.

Proof of claim 1.

$(\Rightarrow )$ First note that if $𝑎=0$, the claim trivially holds because $0\ge -\frac{1}{4}$.

For the case where $𝑎\ne 0$, if $𝐴\ne \varnothing$, then $𝑓\left(𝑥\right)-𝑥=𝑎{𝑥}^2-𝑥-1$ has a root. Therefore, $\mathrm{\Delta }={\left(-1\right)}^2-4\left(𝑎\right)\left(-1\right)\ge 0$, so $𝑎\ge -\frac{1}{4}$.

$(\Leftarrow )$ First note that if $𝑎=0$, then $𝑓\left(𝑥\right)=-1$, so $𝑓\left(-1\right)=-1$ is a fixed point, hence $-1\in 𝐴$, so $𝐴\ne \varnothing$.

For the case where $𝑎\ne 0$, if $𝑎\ge -\frac{1}{4}$, then $\mathrm{\Delta }\ge 0$, so $𝑓\left(𝑥\right)-𝑥$ has at least one real root, which means there exists some $𝑥\in ℝ$ for which $𝑥\in 𝐴$. $∎$

Claim 2: $𝐴=𝐵$ if and only if $𝑎\le \frac{3}{4}$.

Proof of claim 2. We have that $-1=𝑓\left(𝑥\right)-𝑎{𝑥}^2$. Therefore,

holds for all $𝑥\in ℝ$.

For convenience, denote $𝑔\left(𝑥\right)={𝑎}^2{𝑥}^2+𝑎𝑥+\left(1-𝑎\right)$. Then $𝑓\left(𝑓\left(𝑥\right)\right)-𝑥=𝑔\left(𝑥\right)\left(𝑓\left(𝑥\right)-𝑥\right)$.

First note that if $𝑎=0$, then we get $𝑓\left(𝑓\left(𝑥\right)\right)-𝑥=\left(0+1\right)\left(𝑓\left(𝑥\right)-𝑥\right)=𝑓\left(𝑥\right)-𝑥$ for all $𝑥\in ℝ$, so $𝐴=𝐵$.

Then, we will prove claim 2 for the case where $𝑎\ne 0$.

$(\Rightarrow )$ Since $𝐴=𝐵$, it must be that $𝐵\subseteq 𝐴$. Hence any root of $𝑓\left(𝑓\left(𝑥\right)\right)-𝑥$ is also a root of $𝑓\left(𝑥\right)-𝑥$. Therefore, either $𝑔\left(𝑥\right)$ has no real roots, or the roots of $𝑔\left(𝑥\right)$ is a subset of the roots of $𝑓\left(𝑥\right)-𝑥$.

Case 1: $𝑔\left(𝑥\right)$ has no real roots. Then, $\mathrm{\Delta }={𝑎}^2-4{𝑎}^2\left(1-𝑎\right)<0$, so ${𝑎}^2\left(4𝑎-3\right)<0$, and since $𝑎\ne 0$, this gives $𝑎<\frac{3}{4}$.

Case 2: $𝑔\left(𝑥\right)$ has at least one real root, and all roots of $𝑔\left(𝑥\right)$ is also a root of $𝑓\left(𝑥\right)-𝑥$.

In this case, $\forall 𝑟\in ℝ$, $𝑔\left(𝑟\right)=0⟹𝑓\left(𝑟\right)-𝑟=0$.

Let $𝑟$ be a root of $𝑔\left(𝑥\right)$. Then, both ${𝑎}^2{𝑟}^2+𝑎𝑟+\left(1-𝑎\right)=0$ and $𝑎{𝑟}^2-𝑟-1=0$. Substitution gives $𝑎\left(𝑟+1\right)+𝑎𝑟+\left(1-𝑎\right)=0$, so $2𝑎𝑟+1=0$, and since $𝑎\ne 0$, this gives $𝑟=-\frac{1}{2𝑎}$. Therefore, $𝑔\left(𝑥\right)$ must have exactly one real root, and it must be $-\frac{1}{2𝑎}$. In this case, $\mathrm{\Delta }=0$, so ${𝑎}^2\left(4𝑎-3\right)=0$, and since $𝑎\ne 0$, we have $𝑎=\frac{3}{4}$.

That concludes all cases. In all cases, $𝑎\le \frac{3}{4}$.

$(\Leftarrow )$ As above, if $𝑎<\frac{3}{4}$, then $𝑔\left(𝑥\right)$ has no real roots, so $𝑓\left(𝑓\left(𝑥\right)\right)-𝑥=0⟹𝑓\left(𝑥\right)-𝑥=0$, so $𝐵\subseteq 𝐴$.

If $𝑎=\frac{3}{4}$, then $𝑔\left(𝑥\right)$ has exactly one root $-\frac{1}{2𝑎}=-\frac{2}{3}$, and in this case, $𝑓\left(-\frac{2}{3}\right)-\left(-\frac{2}{3}\right)=\left(\frac{3}{4}\right){\left(-\frac{2}{3}\right)}^2-1+\frac{2}{3}=0$, so $𝑓\left(𝑓\left(𝑥\right)\right)-𝑥=0⟹𝑓\left(𝑥\right)-𝑥=0$, which means $𝐵\subseteq 𝐴$.

Hence if $𝑎\le \frac{3}{4}$ and $𝑎\ne 0$, then $𝐵\subseteq 𝐴$. Furthermore, in part (a), we deduced that $𝐴\subseteq 𝐵$. Therefore, we have $𝑎\le \frac{3}{4}\wedge 𝑎\ne 0⟹𝐴=𝐵$.

Therefore, both directions are proven, and in the case where $𝑎\ne 0$, we have $𝑎\le \frac{3}{4}$ if and only if $𝐴=𝐵$.

Combining this with the $𝑎=0$ case, we have proven claim 2. $∎$

By claim 1 and claim 2, $𝐴=𝐵$ and $𝐴\ne \varnothing$ if and only if $𝑎\ge -\frac{1}{4}$ and $𝑎\le \frac{3}{4}$, so the set of all possible values of $𝑎$ is $\left[-\frac{1}{4},\frac{3}{4}\right]$. $∎$