Solving a Functional Equation using Verbal reasoning. International Math Olympiad 2022, Problem 2.

Context
Problem
Solution
- Notation
- Lemma 1
- Lemma 2
- Lemma 3
- Lemma 4
- Lemma 5
- Lemma 6
- Finally
Final thoughts
Postscript
- Modified proof of Lemma 5

Context

Suppose you are constrained to solving a math problem purely in your head (no pen/paper). Is it possible to solve a medium hard problem, like say a International Math Olympiad problem? In this post, I’ll show that some times, it is possible to solve problems purely using verbal reasoning. That is, instead of full fledged formal manipulations in your head, you can use simpler, verbal reasoning that still captures the essence which can then be turned into a formal proof later on.

Why is this interesting? Right now, LLMs (Large Language Models) are topical and their ‘reasoning’ appears verbal than formal. I don’t know if there’s any real connection, but I thought it was interesting nonetheless. It is also much easier to reason in this domain than otherwise.

Problem

This is problem #2 from IMO 2022

Let \(\mathbb{R}^+\) denote the set of positive real numbers. Find all functions \(f : \mathbb{R}^+ \to \mathbb{R}^+\) such that for each \(x \in \mathbb{R}^+\), there is exactly one \(y \in \mathbb{R}^+\) satisfying \(xf (y) + yf (x) \le 2\).

Solution

The solution will proceed as a series of observations all done without pen/paper. Some of them will require a deeper understanding of continuous functions to allow for verbal reasoning.

Notation

Some notation/terminology

All variables like \(u, v, x, y\) are assumed to be in \(\mathbb{R}^+\).
Let’s call \((x, y)\) a matching pair if they satisfy the given functional equation, i.e. \(xf(y) + yf(x) \le 2\).
We say \(y\) is \(x\)’s match if \((x, y)\) is a matching pair.

Lemma 1

If \((x, y)\) is a matching pair, so is \((y, x)\)

Obvious since the functional equation is symmetric in \(x\) and \(y\). The implication is that if we find a match for \(x\), say \(X\), then we’ve found the match for \(X\) as well (it is \(x\)).

Lemma 2

If \((x,y)\) is a matching pair, \(\forall Y \neq y\), \((x, Y)\) is not a matching pair

Follows from the uniqueness requirement in the problem statement.

Lemma 3

\(f\) is a decreasing function

Verbal Reasoning: Suppose \((V,v)\) is a matching pair. So, \(Vf(v) + f(V)v \le 2\). If both \(f(v)\) and \(v\) simultaneously become smaller, the LHS becomes smaller and stays \(\le 2\) providing another match for \(V\) which is a contradiction. In other words, we can’t have \(f(v') \le f(v) \text{ and } v' \lt v\).

Ideally, for the argument to work correctly, I should have said one is smaller (\(v\)) and the other (\(f(v)\)) is not larger but, when reasoning purely in the head, it is helpful to make statements like both simultaneously become smaller over one is smaller and the other is not larger. At least, my brain processes the former easier than the latter. Perhaps because it compresses better.

Lemma 4

\(f\) is a continuous function

This is where the verbal-reasoning cracks open the problem. When I was originally reasoning about this (on my train commute), I had this hypothesis that \(f\) is continuous but without access to pen/paper, it was difficult to prove or reason about. The \(\epsilon, \delta\) definition of continuity is hard to apply purely in the head.

So, I turned to a different sort of reasoning about continuity that CAN be done in the head.

Definition: A function \(f\) is continuous at \(a\) iff for every \(\epsilon \gt 0, \exists \delta \gt 0\) such that \(|x-a| \lt \delta \implies |f(x)-f(a)| \lt \epsilon\).

The way I read this is: If \(f\) is discontinous at \(a\), there’s some fixed threshold such that there are arbitrary small input changes still produce changes larger than the threshold. This interpretation is accurate and more easy to reason in the head but a further simplification is required to more readily reason.

Introduce notion of Vanishing(ly small)Jump, StepJump & Fixed.

VanishingJump is an arbitrarily small positive jump picked from an infinite set with \(0\) as a limit point.

Fixed is any positive constant

StepJump is a minimal positive jump. That is, it is some minimal distance away from \(0\). It is not Fixed since it can change based on our choice

Admittedly, these are fuzzy concepts, but they are still quite accurate for our purposes.

It becomes easier to reason if we can do some algebra in our heads:

\[StepJump * Fixed = StepJump\]

\[VanishingJump * Fixed = VanishingJump\]

\[Fixed + Positive StepJump \gt Fixed\]

\[VanishingJump + Fixed \sim Fixed\]

Note the similarity of the algebra with big-oh algebra: \(O(n^2) + O(n) = O(n^2)\)

Finally, it all boils down to this:

\(\text{If } f \text{ is discontinuous at a, then } f(a \pm VanishingJump) = f(a) \pm StepJump\)

\(\text{If } f \text{ is continuous at a, then } f(a \pm VanishingJump) = f(a) \pm VanishingJump\)

Obviously, not all VanishingJumps produce StepJumps even at a discontinuity, but we can read it as: the user can choose VanishingJumps & StepJumps to make the above identities come true.

Armed with this simplification, we can now reason. Assume \(f\) is discontinuous at \(a\) and \((a, b)\) is a matching pair. We’ll need to produce a contradiction by utilizing the fact that \(f\) is discontinuous at \(a\).

Let’s use \(A = a + VanishingJump\) ! Then, \(f(A) = f(a + VanishingJump) = f(a) - StepJump\) (the \(-\)ve sign is because \(f\) is decreasing as noted in Lemma 3), so that

\[\begin{align*} bf(A) + f(b)A & = b(f(a) - StepJump) + f(b)(a + VanishingJump) \\ & = bf(a) + f(b)a - b.StepJump + f(b).VanishingJump \\ & = bf(a) + f(b)a - Fixed.StepJump + Fixed.VanishingJump \\ & = bf(a) + af(b) - StepJump + VanishingJump \\ & \lt bf(a) + f(b)a \\ & \le 2 \\ & \implies \text{(b, A) is a matching pair} \\ & \implies \text{contradiction since (b, a) is already a matching pair!} \end{align*}\]

Verbal Reasoning: If \(f\) is discontinuous at \(a\), small increase in \(a\) leads to large decreases in \(f(a)\) and we can exploit this fact to find another match for \(b\).

Lemma 5

\[\forall x, xf(x) \ge 1\]

Assume contrary, that is, \(\exists a, af(a) \lt 1\).

Then, \(af(a) \lt 1 \implies af(a) + f(a)a \lt 2 \implies \text{(a, a) is a matching pair}\).

We show that \(a\) has another matching pair \(A\), a contradiction. To do this, we set \(A = a + VanishingJump\).

\[\begin{align*} af(A) + f(a)A & = a(f(a) - VanishingJump) + f(a)(a + VanishingJump) \\ & = af(a) + f(a)a - a.VanishingJump + f(a).VanishingJump \\ & = af(a) + f(a)a - fixed.VanishingJump + fixed.VanishingJump \\ & = af(a) + af(a) - VanishingJump + VanishingJump \\ & \lt af(a) + f(a)a \pm VanishingJump \\ & \lt 2 \pm VanishingJump \\ & \le 2 \\ & \implies \text{(a, A) is a matching pair} \\ & \implies \text{contradiction since (a, a) is already a matching pair!} \end{align*}\]

Verbal Reasoning: In other words, since \(f\) is continuous at \(a\), small increases in \(a\) lead to small decreases in \(f(a)\) and we exploit this fact to find a second match for \(a\).

Lemma 6

\[\forall x, xf(x) \le 1\]

Assume otherwise, i.e. \(\exists a, af(a) \gt 1\). Let \((a, b)\) be a matching pair.

\[\begin{align*} af(b) + bf(a) & \ge af(a) + bf(b) \text{ [Rearrangement inequality & f decreasing]} \\ & \gt 1 + 1 \text{ [}bf(b) \ge 1 \text{ from Lemma 5]} \\ & \implies \text{(a, b) is NOT a matching pair, a contradiction!} \end{align*}\]

Verbal Reasoning: If \(af(a) \gt 1\), we exploit that \(f\) is decreasing to invoke Rearrangement inequality.

Finally

Putting Lemma 5 and Lemma 6 together, we have the final solution:

\(\forall x, f(x) = 1/x\) is the only solution

Final thoughts

Proving continuity of \(f\) required a deep understanding of continuity and how small changes at a discontinuity can still lead to large changes in the function’s value. Once we created a verbal calculus (VanishingJump & StepJump) around it, it became easier to reason purely in the verbal domain, like let me perturb the input by a small change and see what happens to the output. This allowed us to show that for a matching pair \((x, y)\), tightness in the form of \(xf(y) = 1\) is required; otherwise nearby perturbations like \((x, y+\epsilon)\) also become matching pairs.

This technique of verbal reasoning is not always feasible, of course. But, I’ve found that the ability to reason verbally is invaluable and broadly applicable, especially in software engineering; it appears to be a potent form of intuition.

Postscript

After publishing this post & staring at it, it has occurred to me that continuity is not even required to solve the problem. I suppose it speaks to the power of using all our senses (vision included). The modified proof differs from the proof above like so:

Don’t prove Lemma 4
Prove Lemma 5 (i.e. \(\forall x, xf(x) \ge 1\)) without resorting to continuity, just using that \(f\) is decreasing
Everything else remains the same

Modified proof of Lemma 5