uniolympiads Ελληνικά

IMC 2024, Day 2, Problem 6

Prove that for any function f ⁣:Q→Zf\colon \mathbb{Q} \to \mathbb{Z}, there exist a,b,c∈Qa, b, c \in \mathbb{Q} such that a<b<ca < b < c, f(b)≥f(a)f(b) \ge f(a), and f(b)≥f(c)f(b) \ge f(c).

Original from the official PDFProve that for any function f : Q → Z, there exist a, b, c ∈ Q such that a < b < c, f (b) ≥ f (a), and f (b) ≥ f (c).

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

(proposed by Mehdi Golafshan & Markus A. Whiteland, University of Liège, Liège)

Solution 1. We can replace f(x)f(x) by the function g(x)=f(1−x)g(x) = f(1-x), so without loss of generality we can assume f(0)≤f(1)f(0) \le f(1).

If f(1)≥f(2)f(1) \ge f(2) then we can choose (a,b,c)=(0,1,2)(a, b, c) = (0, 1, 2). Otherwise we have f(0)≤f(1)<f(2)f(0) \le f(1) < f(2).

If there is some x∈(1,2)x \in (1, 2) such that f(x)≥f(2)f(x) \ge f(2) then we can chose (a,b,c)=(1,x,2)(a, b, c) = (1, x, 2); similarly, if there is some x∈(1,2)x \in (1, 2) with f(x)≤f(1)f(x) \le f(1) then choose (a,b,c)=(0,1,x)(a, b, c) = (0, 1, x). Hence, in the remaining cases we have f(1)≤f(x)≤f(2)f(1) \le f(x) \le f(2) for all x∈(1,2)x \in (1, 2).

Now ff is bonded on the interval [1,2][1, 2], so it has only finitely many values on this interval. Since there are infintely many rational numbers in [0,1][0, 1], there is a value yy that is attained infinitely many times. The we can choose 1≤a<b<c≤21 \le a < b < c \le 2 such that f(a)=f(b)=f(c)=yf(a) = f(b) = f(c) = y.

Solution 2. Assume towards a contradiction that there is a function ff which does not satisfy the claim: for all rationals a,b,ca, b, c with a<b<ca < b < c we have f(b)<f(a)f(b) < f(a) or f(b)<f(c)f(b) < f(c).

Let xx and yy be arbitrary rationals with x<yx < y. Let I(x,y)=[x,y]∩QI(x, y) = [x, y] \cap \mathbb{Q}. We first observe that inf⁡f(I(x,y))=−∞\inf f(I(x, y)) = -\infty. Indeed, if the infimum was finite, then, as the set f(I(x,y))f(I(x, y)) is bounded (sup⁡f(I(x,y))=max⁡{f(x),f(y)}\sup f(I(x, y)) = \max\{f(x), f(y)\}) and thus finite, there are three points having the same value under ff, which leads to a contradiction regarding our assumption on ff.

So, going back to the question at hand, let xx, bb, yy be arbitrary rationals with x<b<yx < b < y. Applying the above observation to the set I(x,b)I(x, b), there exists a point a∈I(x,b)a \in I(x, b) such that f(a)<f(b)f(a) < f(b). Similarly, there exists a point c∈I(b,y)c \in I(b, y) such that f(c)<f(b)f(c) < f(b). Hence we have the points aa, bb, cc with a<b<ca < b < c and f(b)>max⁡{f(a),f(c)}f(b) > \max\{f(a), f(c)\}, which contradicts our assumption on ff.

Transcribed from the official solutions, pages 1–2. 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?