PUMaC 2016 · 个人决赛（A 组） · 第 2 题

PUMaC 2016 — Individual Finals (Division A) — Problem 2

Let m , k , and c be positive integers with k > c , and let λ be a positive, non-integer real m +1 m + root of the equation λ − kλ − c = 0. Let f : Z → Z be defined by f ( n ) = b λn c

m +1 + + for all n ∈ Z . Show that f ( n ) ≡ cn − 1 (mod k ) for all n ∈ Z . (Here, Z denotes the set of positive integers, b x c denotes the greatest integer less than or equal to x , and m +1 f ( n ) = f ( f ( . . . f ( n ) . . . )) where f appears m + 1 times.)

解析

From the defining equation we obtain λ = k + ⇒ b λn c = kn + for all n ∈ Z , m m λ λ ⌊ ⌋ ⌊ ⌋ m cf ( n ) cn m +1 so f ( n ) ≡ (mod k ). Thus f ( n ) ≡ (mod k ) so it suffices to show that m m λ λ a m m m ( cn − 1) λ ≤ cf ( n ) < cnλ . We note that if λ = is rational with gcd( a, b ) = 1 then b m m +1 b λ is an integer, so b = ± 1 and λ is an integer. Therefore λ must be irrational, so m m m m f ( n ) < λn ⇒ f ( n ) < λ n ⇒ cf ( n ) < cnλ . On the other hand, f ( n ) > λn − 1 so m m λ − 1 λ − 1 m m m m f ( n ) > λ ( λ ( . . . λ ( λn − 1) − 1 . . . ) − 1) − 1 = λ n − ⇒ cf ( n ) > cnλ − c λ − 1 λ − 1 m m λ − 1 λ − 1 m m where c ≤ ( k − 1) < λ . The second inequality holds because ( k − 1)( λ − 1) < λ − 1 λ − 1 m m m +1 m λ ( λ − 1) ⇔ kλ − k + 1 < λ = kλ + c which is true since k + c > 1. This completes the proof. Problem written by Mel Shu. (See next page for solution to Problem 3.) 1 1