uniolympiads Ελληνικά

IMC 2003, Day 2, Problem 5

(a) Show that for each function f ⁣:Q×Q→Rf\colon \mathbb{Q} \times \mathbb{Q} \to \mathbb{R} there exists a function g ⁣:Q→Rg\colon \mathbb{Q} \to \mathbb{R} such that f(x,y)≤g(x)+g(y)f(x, y) \le g(x) + g(y) for all x,y∈Qx, y \in \mathbb{Q}.

(b) Find a function f ⁣:R×R→Rf\colon \mathbb{R} \times \mathbb{R} \to \mathbb{R} for which there is no function g ⁣:R→Rg\colon \mathbb{R} \to \mathbb{R} such that f(x,y)≤g(x)+g(y)f(x, y) \le g(x) + g(y) for all x,y∈Rx, y \in \mathbb{R}.

Original from the official PDF5. (a) Show that for each function f : Q × Q → R there exists a function g : Q → R such that f (x, y) ≤ g(x) + g(y) for all x, y ∈ Q. (b) Find a function f : R × R → R for which there is no function g : R → R such that f (x, y) ≤ g(x) + g(y) for all x, y ∈ R.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. a) Let φ:Q→N\varphi : \mathbb{Q} \to \mathbb{N} be a bijection. Define g(x)=max⁡{∣f(s,t)∣:s,t∈Q,φ(s)≤φ(x),φ(t)≤φ(x)}g(x) = \max\{|f(s, t)| : s, t \in \mathbb{Q}, \varphi(s) \le \varphi(x), \varphi(t) \le \varphi(x)\}. We have f(x,y)≤max⁡{g(x),g(y)}≤g(x)+g(y)f(x, y) \le \max\{g(x), g(y)\} \le g(x) + g(y).

b) We shall show that the function defined by f(x,y)=1∣x−y∣f(x, y) = \frac{1}{|x-y|} for x≠yx \ne y and f(x,x)=0f(x, x) = 0 satisfies the problem. If, by contradiction there exists a function gg as above, it results, that g(y)≥1∣x−y∣−f(x)g(y) \ge \frac{1}{|x-y|} - f(x) for x,y∈R, x≠yx, y \in \mathbb{R}, \ x \ne y; one obtains that for each x∈R, lim⁡y→xg(y)=∞x \in \mathbb{R}, \ \lim\limits_{y\to x} g(y) = \infty. We show, that there exists no function gg having an infinite limit at each point of a bounded and closed interval [a,b][a, b].

For each k∈N+k \in \mathbb{N}^+ denote Ak={x∈[a,b]:∣g(x)∣≤k}A_k = \{x \in [a, b] : |g(x)| \le k\}.

We have obviously [a,b]=∪k=1∞Ak[a, b] = \cup_{k=1}^\infty A_k. The set [a,b][a, b] is uncountable, so at least one of the sets AkA_k is infinite (in fact uncountable). This set AkA_k being infinite, there exists a sequence in AkA_k having distinct terms. This sequence will contain a convergent subsequence (xn)n∈N(x_n)_{n\in\mathbb{N}} convergent to a point x∈[a,b]x \in [a, b]. But lim⁡y→xg(y)=∞\lim\limits_{y\to x} g(y) = \infty implies that g(xn)→∞g(x_n) \to \infty, a contradiction because ∣g(xn)∣≤k, ∀n∈N|g(x_n)| \le k, \ \forall n \in \mathbb{N}.

Second solution for part (b). Let SS be the set of all sequences of real numbers. The cardinality of SS is ∣S∣=∣R∣ℵ0=2ℵ02=2ℵ0=∣R∣|S| = |\mathbb{R}|^{\aleph_0} = 2^{\aleph_0^2} = 2^{\aleph_0} = |\mathbb{R}|. Thus, there exists a bijection h: R→Sh : \ \mathbb{R} \to S. Now define the function ff in the following way. For any real xx and positive integer nn, let f(x,n)f(x, n) be the nnth element of sequence h(x)h(x). If yy is not a positive integer then let f(x,y)=0f(x, y) = 0. We prove that this function has the required property.

Let gg be an arbitrary R→R\mathbb{R} \to \mathbb{R} function. We show that there exist real numbers x,yx, y such that f(x,y)>g(x)+g(y)f(x, y) > g(x) + g(y). Consider the sequence (n+g(n))n=1∞(n + g(n))_{n=1}^\infty. This sequence is an element of SS, thus (n+g(n))n=1∞=h(x)(n + g(n))_{n=1}^\infty = h(x) for a certain real xx. Then for an arbitrary positive integer nn, f(x,n)f(x, n) is the nnth element, f(x,n)=n+g(n)f(x, n) = n + g(n). Choosing nn such that n>g(x)n > g(x), we obtain f(x,n)=n+g(n)>g(x)+g(n)f(x, n) = n + g(n) > g(x) + g(n).

Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?