Unofficial archive — problems, solutions & results © IMC, reproduced with permission.

IMC / 2002 / Problems / Day 1, P4

IMC 2002 · Day 1 · P4

hard

Let f:[a,b][a,b]f : [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 xTpx \notin T_p then there is a δ>0\delta > 0 such that for all xTpx' \in T_p we have xxδ|x' - x| \ge \delta. Show that TpT_p has finitely many elements.

Solution (official)

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 p0,p1,p_0, p_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{pmpn:m,n0}d = \sup \{ |p_m - p_n| : m, n \ge 0 \}. Let δn\delta_n be positive numbers such that n=0δn<d2\sum\limits_{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 pkj=0nIjp_k \notin \bigcup\limits_{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 pkj=0nmIjp_k \notin \bigcup\limits_{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 TpT_p is closed then this contradicts the Baire Category Theorem.

How the field did

contestants scored
182
average (of 20)
6.98
solved (≥ 80%)
24.7%
near-0 (≤ 10%)
38.5%
discrimination
0.50

Score distribution (field cohort)

Computed on contestants with a meaningful total (field cohort); discrimination is the corrected item–total correlation.

Similar problems

IMC 2007 · Day 2 · P9easyavg 5.4/10 · solved 51% · near-0 40% · disc 0.44
IMC 2005 · Day 2 · P10hardavg 4.3/10 · solved 25% · near-0 44% · disc 0.49
IMC 2023 · Day 2 · P7hardavg 3.8/10 · solved 26% · near-0 45% · disc 0.49
IMC 2017 · Day 1 · P2hardavg 3.2/10 · solved 26% · near-0 56% · disc 0.63