uniolympiads English

IMC 2003, Ημέρα 2, Θέμα 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}.

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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).

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;