Maths Olympiad Prep

Library / Ukrainian Mathematical Competitions /6 of 6

Ukrainian Mathematical Competitions

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,x2∈A, x1≠x2\forall x_1, x_2 \in A,\ x_1 \neq x_2 the condition min⁡{f(x1),f(x2)}≤∣x1−x2∣\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), n∈Z, m∈N, 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, ⋃n∈Z⋃m∈Z+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))∣x∈A}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 (A∼GA \sim G).
Suppose that ∀n∈Z,m∈Z+\forall n \in \mathbb{Z}, m \in \mathbb{Z}^+ (i.e. the set G∩Dn,mG \cap D_{n,m}) is finite, but then the whole set GG is at most countable, that contradicts its construction. Therefore, ∃n0∈Z,m0∈Z+:G∩Dn0,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 ∀x∈X\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 ∀k∈N\forall k \in \mathbb{N} f(xk)>1m0+1f(x_k) > \frac{1}{m_0+1}. But then we have the following relationship: 0=lim⁡k→∞∣xk+1−xk∣0 = \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=min⁡k=1,n∣xn+1−xk∣>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, p∈Zp \in \mathbb{Z}, q∈Nq \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 p1q1≠p2q2\frac{p_1}{q_1} \neq \frac{p_2}{q_2} we have:
∣x1−x2∣=∣p1q2−q1p2∣q1q2≥1q1q2≥1max⁡{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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.