Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 6.4 National olympiad Prove it Ukraine

For which of the sets A=RA = \mathbb{R} or A=QA = \mathbb{Q} is there a function f:A(0,+)f : A \to (0, +\infty) such that x1,x2A, x1x2\forall x_1, x_2 \in A,\ x_1 \neq x_2 the condition min{f(x1),f(x2)}x1x2\min\{f(x_1), f(x_2)\} \leq |x_1 - x_2| is satisfied?
(Andrii Anikushin)

Solution

Suppose that the set AA is more than countable set.
Divide half-plane R×(0,+)\mathbb{R} \times (0, +\infty) to the counted number of rectangles:
Dn,m=[n,n+1)×[1m+1,1m), nZ, mN, Dn,0=[n,n+1)×[1,+). D_{n,m} = [n, n+1) \times \left[\frac{1}{m+1}, \frac{1}{m}\right), \ n \in \mathbb{Z},\ m \in \mathbb{N},\ D_{n,0} = [n, n+1) \times [1, +\infty).
By construction, nZmZ+Dn,m=R×(0,+)\bigcup_{n \in \mathbb{Z}} \bigcup_{m \in \mathbb{Z}^+} D_{n,m} = \mathbb{R} \times (0, +\infty), in addition, any two of determined earlier rectangles do not intersect. Consider the graph G={(x,f(x))xA}G = \{(x, f(x)) \mid x \in A\} of the function ff.
Because AA is more than countable, the set GG is also more than countable (AGA \sim G).
Suppose that nZ,mZ+\forall n \in \mathbb{Z}, m \in \mathbb{Z}^+ (i.e. the set GDn,mG \cap D_{n,m}) is finite, but then the whole set GG is at most countable, that contradicts its construction. Therefore, n0Z,m0Z+:GDn0,m0\exists n_0 \in \mathbb{Z}, m_0 \in \mathbb{Z}^+ : G \cap D_{n_0,m_0} is infinite set. This means that there is an infinite set X[n0,n0+1)AX \subset [n_0, n_0+1) \cap A such that xX\forall x \in X f(x)>1m0+1f(x) > \frac{1}{m_0+1}. Then due to Bolzano-Weierstrass theorem there is a sequence of different elements that converges to some number. As a result, this sequence is fundamental and kN\forall k \in \mathbb{N} f(xk)>1m0+1f(x_k) > \frac{1}{m_0+1}. But then we have the following relationship: 0=limkxk+1xk0 = \lim_{k \to \infty} |x_{k+1} - x_k| and min{f(xk),f(xk+1)}1m0+1\min\{f(x_k), f(x_{k+1})\} \geq \frac{1}{m_0+1}, which contradicts the problem's condition.

Thereby, AA should be no more than countable. Now determine the required function. Let A={x1,x2,...}A = \{x_1, x_2, ...\}. Define the function by induction: f(x1)=1f(x_1) = 1. Now let us know f(x1),...,f(xn)f(x_1), ..., f(x_n). Let us make the following notation: r=mink=1,nxn+1xk>0r = \min_{k=1,n} |x_{n+1} - x_k| > 0. Let's set f(xn+1)=r2f(x_{n+1}) = \frac{r}{2}.
We should verify that the function which is defined for AA satisfies the conditions of the problem.

Example: for A=QA = \mathbb{Q}: if x=pqx = \frac{p}{q}, where (p,q)=1(p, q) = 1, pZp \in \mathbb{Z}, qNq \in \mathbb{N} (0=010 = \frac{0}{1}), we will set f(pq)=1q2f\left(\frac{p}{q}\right) = \frac{1}{q^2}. Then if p1q1p2q2\frac{p_1}{q_1} \neq \frac{p_2}{q_2} we have:
x1x2=p1q2q1p2q1q21q1q21max{q12,q22}=min{f(x1),f(x2)}. |x_1 - x_2| = \frac{|p_1 q_2 - q_1 p_2|}{q_1 q_2} \geq \frac{1}{q_1 q_2} \geq \frac{1}{\max\{q_1^2, q_2^2\}} = \min\{f(x_1), f(x_2)\}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.