My mathematics blog

Month: April, 2013

An exercise in transfinite magic

In my hometown there is a university called SUSU. And in this university regular math contests (link in Russian) are held, organized by A. Yu. Evnin. The following problem appeared in one of these contests:

Problem 1. A function $f: \mathbb {R} \to \mathbb {R}$ has the following property: every straight line on the plane $\mathbb {R}^2$ intersects the graph of $f$ and the parabola $y = x^2$ at the same number of points. Prove that $f(x) = x^2$ for every $x \in \mathbb {R}$.

The solution is quite straightforward, I am not going to write it down. It is probably enough to say that it heavily exploits the convexity of $y = x^2$.

This post is not about problem 1. It is about the next thing that comes to mind:

Problem 2. Two functions $f, g: \mathbb {R} \to \mathbb {R}$ have graphs $F$ and $G$ such that for every straight line $l \subset \mathbb {R}^2$: $|l \cap F| = |l \cap G| < \infty$. Does it follow that $f$ and $g$ are the same function?

If you think about this one for a minute, I’m sure you’ll find it much more challenging than problem 1. This whole post is about solving problem 2. If you want to give it a try yourself, this is the last point in the text where you can still do this without knowing the answer.

Problem 1. A function $f: \mathbb {Z} \times \mathbb {Z} \to \mathbb {Z}$ is polynomial of each argument, i.e. for every $x_0 \in \mathbb {Z}$ the function $y \to f(x_0, y)$ can be represented by a polynomial with integer coefficients, and the same goes for $x \to f(x, y_0)$ for every $y_0$. Is it true then that $f$ must be polynomial of both arguments simultaneously, i.e. representable by an element of $\mathbb {Z}[x,y]$?
If you’ve ever been a freshman in an analysis course, you are bound to be aware of a common trap with the notion of differentiability. The trap is like this: you are asked to prove that a function $g: \mathbb {R} \times \mathbb {R} \to \mathbb {R}$ is differentiable everywhere. You have several months of single-variable analysis behind your back. So your first instinct may be to prove that $\partial g / \partial x$ and $\partial g / \partial y$ exist at every point and be done with it. But this is not enough, as demonstrated by
$\displaystyle g(x,y) = \left\{ \begin{array}{ll}0 & \quad \mathrm{at}\, \mathrm{point}\, (0,0) \\ \frac{xy}{\sqrt {x^2+y^2}} & \quad \mathrm{everywhere}\, \mathrm{else.}\end{array}\right.$