uniolympiads Ελληνικά

IMC 2002, Day 1, Problem 4

Let f ⁣:[a,b]→[a,b]f\colon [a, b] \to [a, b] be a continuous function and let p∈[a,b]p \in [a, b]. Define p0=pp_0 = p and pn+1=f(pn)p_{n+1} = f(p_n) for n=0,1,2,…n = 0, 1, 2, \dots Suppose that the set Tp={pn:n=0,1,2,… }T_p = \{p_n : n = 0, 1, 2, \dots\} is closed, i.e., if x∉Tpx \notin T_p then there is a δ>0\delta > 0 such that for all x′∈Tpx' \in T_p we have ∣x′−x∣≥δ|x' - x| \ge \delta. Show that TpT_p has finitely many elements.

Original from the official PDFLet f : [a, b] → [a, b] be a continuous function and let p ∈ [a, b]. Define p 0 = p and p n+1 = f (p n ) for n = 0, 1, 2, . . . Suppose that the set T p = {p n : n = 0, 1, 2, . . . } is closed, i.e., if x ∈ / T p then there is a δ > 0 such that for all x 0 ∈ T p we have |x 0 − x| ≥ δ. Show that T p has finitely many elements.

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. If for some n>mn>m the equality pm=pnp_m=p_n holds then TpT_p is a finite set. Thus we can assume that all points p0p_0, p1p_1, …\dots are distinct. There is a convergent subsequence pnkp_{n_k} and its limit qq is in TpT_p. Since ff is continuous pnk+1=f(pnk)→f(q)p_{n_k+1}=f(p_{n_k})\to f(q), so all, except for finitely many, points pnp_n are accumulation points of TpT_p. Hence we may assume that all of them are accumulation points of TpT_p. Let d=sup⁡{∣pm−pn∣:  m,n≥0}d=\sup\{|p_m-p_n|:\ \ m,n\ge0\}. Let δn\delta_n be positive numbers such that ∑n=0∞δn<d2\sum_{n=0}^\infty\delta_n<\frac{d}{2}. Let InI_n be an interval of length less than δn\delta_n centered at pnp_n such that there are there are infinitely many kk's such that pk∉⋃j=0nIjp_k\notin\displaystyle\bigcup_{j=0}^{n}I_j, this can be done by induction. Let n0=0n_0=0 and nm+1n_{m+1} be the smallest integer k>nmk>n_m such that pk∉⋃j=0nmIjp_k\notin\displaystyle\bigcup_{j=0}^{n_m}I_j. Since TpT_p is closed the limit of the subsequence (pnm)(p_{n_m}) must be in TpT_p but it is impossible because of the definition of InI_n's, of course if the sequence (pnm)(p_{n_m}) is not convergent we may replace it with its convergent subsequence. The proof is finished.

Remark. If Tp={p1,p2,… }T_p=\{p_1,p_2,\dots\} and each pnp_n is an accumulation point of TpT_p, then TpT_p is the countable union of nowhere dense sets (i.e. the single-element sets {pn}\{p_n\}). If TT is closed then this contradicts the Baire Category Theorem.

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