TA BA TRUNG JOY15/3 Phương trình hàm tập số nguyên D em o Ve rs io n Phan Sỹ Quang Lớp A1 K35, Trường THPT Chuyên Phan Bội Châu, Nghệ An Mục lục Sử dụng nguyên lý quy nạp. Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Bài tập áp dụng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 n 1.1 Ứng dụng toán dãy số vào giải phương trình hàm. 11 Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Bài tập áp dụng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Sử dụng đánh giá bất đẳng thức. rs io 2.1 11 15 Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Bài tập áp dụng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ve 3.1 Sử dụng nguyên lý cực hạn. 19 21 Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Bài tập áp dụng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 D em o 4.1 Hàm số sử dụng tính chất số học. 25 5.1 Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 Bài tập áp dụng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Hàm số hệ đếm số. 39 6.1 Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.3 Bài tập áp dụng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Ý tưởng liên kết hàm số toán rời rạc. 46 7.1 Lý thuyết. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7.2 Một vài ví dụ minh họa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 48 D em o Ve rs io n Một số toán chưa có lời giải. Sử dụng nguyên lý quy nạp. 1.1 Lý thuyết. 1.2 io n Phương pháp quy nạp không xa lạ môn toán, công cụ thực hiệu để giải toán xác định tập số nguyên. ( Tất nhiên có quy nạp tập số thực, quy nạp hình học, ta xét đến dạng quen thuộc phương pháp quy nạp mà ). Điều quan trọng việc thiết lập giá trị hàm số điểm lớn điểm biết giá trị hàm số ( theo giả thiết quy nạp ), cụ thể ta cần để ý đến đẳng thức truy hồi biết. Một vài ví dụ minh họa. rs Ví dụ 1. ( Việt Nam TST 2005 ). Tìm tất hàm số f : Z −→ Z thỏa mãn: f (x3 + y + z ) = f (x)3 + f (y)3 + f (z)3 P (0, 0, 0) ⇒ f (0) = Ve Giải: Kí hiệu P (x, y, z) cách cho (x, y, z) ∈ Z3 vào phương trình. P (x, −x, 0) ⇒ f (x) = −f (−x) D em o P (1, 1, 0) ⇒ f (2) = 2f (1) P (1, 1, 1) ⇒ f (3) = 3f (1) Ta chứng minh quy nạp mệnh đề sau f (n) = nf (1), ∀n ∈ Z. Với n = hiển nhiên . Giả sử với n = k ≥ đúng, ta chứng minh với n = k + đúng. Với k = 2t, sử dụng đẳng thức: (2t + 1)3 + 53 + 13 = (2t − 1)3 + (t + 4)3 + (4 − t)3 k = 2t − (2t)3 = (2j )3 .(2i + 1)3 , 2i + < 2t, j ∈ N Ta có: f (2t + 1)3 + f (5)3 + f (1)3 = f ((2t + 1)3 + 53 + 13 ) = f (2t − 1)3 + (t + 4)3 + (4 − t)3 ) = f (2t − 1)3 + f (t + 4)3 + f (4 − t)3 ( Do f lẻ nên f (4 − t) = −f (t − 4) = −(t − 4)f (1) ). Hay : f (2t + 1) = (2t + 1)f (1). Tương tự cho f (2t) = 2tf (1). Vì ta có với n ∈ Z f (n) = nf (1). Thay vào phương trình ta nhận nghiệm: f (x) = 0, f (x) = x, f (x) = −x. n Sau ví dụ tương tự cho biến: ∇ rs 1, f (m2 + n2 ) = f (m) + f (n) với m, n ∈ N. io Ví dụ 2. Tìm tất hàm f : N −→ N thoả mãn điều kiện: 2, f (1) > 0. Ve Giải: Cho m = n = vào phương trình hàm, ta f (0) = 2f (0). Nếu f (0) = từ suy f (0) = , điều mâu thuẫn f nhận giá trị N. Vậy f (0) = điều dẫn đến f (m2 ) = f (m). Ta viết a) dạng f (m2 + n2 ) = f (m) + f (n) = f (m2 ) + f (n2 ) D em o Ta ý f (1) = f (12 ) = f (1). Vì f (1) > nên f (1) = 1. Từ suy ra: f (2) = f (12 + 12 ) = f (1) + f (1) = f (4) = f (22 ) = f (2) = f (5) = f (22 + 12 ) = f (2) + f (1) = f (8) = f (22 + 22 ) = f (2) + f (2) = Hơn nữa, ta thấy 25 = f (5) = f (52 ) = f (32 + 42 ) = f (3) + f (4) = f (3) + 16 Từ suy f (3) = 3. Từ ta lại có: f (9) = f (32 ) = f (3) = f (10) = f (32 + 12 ) = f (3) + f (1) = 10 Sử dụng đẳng thức 72 + 12 = 52 + 52 , biết f (5) = 5, f (1) = 1, ta tính f (7) = 7. Cuối cùng, ta sử dụng đẳng thức 102 = 62 + 82 để thu f (6) = 6. Như ta có f (n) = n với n ≤ 10. Ta sử dụng đẳng thức sau: (5k + 1)2 + 22 = (4k + 2)2 + (3k − 1)2 (5k + 2)2 + 12 = (4k + 1)2 + (3k + 2)2 (5k + 3)2 + 12 = (4k + 3)2 + (3k + 1)2 Và : io (5k + 5)2 = (4k + 4)2 + (3k + 3)2 . n (5k + 4)2 + 22 = (4k + 2)2 + (3k + 4)2 Sử dụng quy nạp ví dụ ta có f (n) = n, ∀n ∈ N. rs Ngay sau toán với ý tưởng khác. ∇ 1, f (1) = 1, f (2) = 2. Ve Ví dụ 3. Cho f (n) ∈ N , ∀x ∈ N và: 2,f (n + 2) = f (n + − f (n + 1)) + f (n + − f (n)) , ∀x ∈ N. a, Chứng minh ≤ f (n + − f (n) ≤ n lẻ f (n + 1) = f (n) + 1. D em o b,Tìm n cho f (n) = 210 + 1. Giải: Ta có với ∀k = 2, 3, . . . , i = 1, . . . , k , j = 1, . . . , 2k−1 − k ta có f (2k − i) = 2k−1 f (2k − k − j) = 2k−1 − f (j). Chứng minh: Quy nạp theo n. Với k = 2, ,n ≤ kiểm tra trực tiếp ta thấy thỏa mãn. Xét với n > 7, k > , đó: f (2k − i) = f (2k − i − f (2k − i − 1)) + f (2k − i − − f (2k − i − 2)) Trường hợp 1: Khi i ≤ k − Theo giả thiết quy nạp : f (2k −i) = f (2k −i−2k−1 )+f (2k −i−1−2k−1 ) = f (2k−1 −i)+f (2k−1 −i−1) = 2k−2 +2k−2 = 2k−1 Trường hợp 2: Khi i = k − 1, ta có : f (2k − i) = f (2k − k + − 2k−1 ) + f (2k − k − 2k−1 + 1) = 2k−1 Trường hợp 3: Khi i = k, ta xác định f (2k − i) = f (2k − k − 2k−1 + 1)) + f (2k − k − − 2k−1 + 2) = 2k−1 Tương tự cho trường hợp tính f (2k − i − j). Ta kết thúc lời giải cho câu 1,. n Mặt khác với k ≥ 2: f (2k ) = f (2k+1 − (k + 1) − (2k − (k + 1))) = 2k − f (2k − k − 1) io = 2k − (2k−1 − f (1)) = 2k−1 + Từ f (2k −1) = 2k−1 nghiệm phương trình f (n) = 210 +1 ta phải có n ≥ 211 theo a,. rs Và với k ≥ ta tính: f (2k + 1) = f (2k+1 − (k + 1) − (2k − (k + 2))) = 2k − f (2k − (k + 2) Ve = 2k − (2k−1 − f (2)) = 2k−1 + Do n = 211 giá trị thỏa mãn. ∇ Ví dụ 4. ( IMO 1982, ).Cho f : N −→ N thoả mãn với m, n ∈ N : D em o f (m + n) − f (m) − f (n) = 1, f (2) = 0, f (3) > 0, f (9999) = 3333. Tính f (1982). Giải: Ta chứng minh quy nạp rằng: f (n) = n với n ≤ 9999 Trước tiên dễ dàng chứng minh f (3) = 1. Quy nạp lên, ta có f (3n) ≥ n. Với f (3n + 3) = f (3) + f (3n) + a (trong a ∈ {0, 1}) = f (3n) + b (trong b ∈ {1, 2}). Mặt khác f (3n) > n ta có f (3m) > m, ∀m > n. Nhưng f (3.3333) = 3333, f (3n) = n với n ≤ 3333. Bây ta có f (3n + 1) = f (3n) + f (1) + a = n + a Nhưng 3n + = f (9n + 3)f (6n + 2) + f (3n + 1)3f (3n + 1) suy f (3n + 1) < n + 1. Hay f (3n + 1) = n. Tương tự, f (3n + 2) = n. Do f (1982) = 660. ∇ Ví dụ 5. ( Iran 1995 ).Tìm tất hàm số f : Z \ {0} → Q thoả mãn với x, y ∈ Z \ {0}: f x+y = f (x) + f (y) , x, y ∈ Z \ {0} n Giải:Ta chứng minh f (x) = c với x ∈ N. Đặt f (1) = c. Cho x = 1, y = ta có f (2) = f (1) = c. io Cho x = y = 3,khi f (3) = f (2) = c. Bây ta chứng minh quy nạp với x > f (x) = c. Vì t ≤ n n+1+t f (n + 1) + f (t) )= Ve f( rs Ta có f (1) = f (2) = f (3) = c. Giả sử với ≤ x ≤ n (ở n ≥ 3) ta có f (x) = c. Gọi t số tự nhiên thuộc đoạn [1; n] cho (n + 1) + t bội 3. Khi n+1+t ≤ n ta có f (n + 1) = c có nghĩa là: f (x) = c D em o với x ≥ 1. Xét k số âm. Khi tồn l > cho l + k > l + k bội 3. Cho x = l, y = k vào phương trình ban đầu, ta f (k) = c. Vậy ta có f (x) = c với số c ∈ Q. Để kết thúc ta xét ví dụ kinh điển sau, phép quy nạp chứng minh trực tiếp giá trị hàm số điểm. ∇ Ví dụ 6. Tìm tất hàm f : N∗ −→ N∗ thoả mãn điều kiện: f (f (n)) + f (n + 1) = n + 2, ∀n ∈ N Giải. Cho n = vào (1) ta có: f (f (1)) + f (2) = Từ f (2) ≤ f (f (1)) ≤ 2. Ta xét trường hợp: (1) Trường hợp 1: f (2) = f (f (1)) = 2. Đặt f (1) = k, ta có f (k) = 2. Cho n = vào (1), ta được: f (f (2)) + f (3) = Suy f (3) = − f (1) = − k. Từ f (3) ≥ nên k ≤ 3. Nếu k = ta có : = f (f (1)) = f (k) = f (1) = k = Mâu thuẫn. Cuối xét k = 3. Hay : io = f (f (1)) = f (k) = f (2) = n Mâu thuẫn. Nếu k = 2, ta có: = f (f (1)) = f (k) = f (3) = − k = rs Cũng điều mâu thuẫn. Ta loại trường hợp này. Trường hợp 2: f (2) = f (f (1)) = 1. Cho n = vào (1), ta nhận được: Ve f (f (2)) + f (3) = Từ dễ thấy f (3) = 2. Ta tính toán rằng: f (4) = − f (f (3)) = − f (2) = D em o f (5) = − f (f (4)) = − f (3) = f (6) = − f (f (5)) = − f (4) = Dự đoán rằng: f (n) = nα − n + √ Ở α = 1+ . Để chứng minh ta cần tới bổ đề sau: Bổ đề 1. Với số n ∈ N∗ : α( nα − n + 1) = n n + Chứng minh: Ta có : α( nα − n + 1) < α(nα − n + 1) n+α α(nα − − n + 1) − = n − Bổ đề chứng minh xong. Bổ đề 2. Với số n ∈ N∗ : nα + 2, α( nα − n + 1) = n nα + 1, trường hợp lại (n + 1)α = io > α((n + 1)α − − n) − = n n Chứng minh: Hiển nhiên (n+1)α = nα +1 nα +2. Giả sử (n+1)α = (n)α +1. Từ ta có: α( nα − n + 1) = α( (n + 1)α − n) Suy ra: α( nα − n + 1) ( Theo Bổ đề 1) rs Mặt khác (n + 1)α = (n)α + thì: α( nα − n + 1) = α( (n + 1)α − n − 1) < α((n + 1)α − n − 1) = n + Ve Từ đó, quan sát Bổ đề ta nhận : α( nα − n + 1) = n. Bây ta chứng minh theo quy nạp kết dự đoán trên. Với n = 1: f (1) = = α = α − + D em o Với n = 2: f (2) = = − + = 2α − + Giả sử kết với ≤ j ≤ n. Sử dụng (1) ta có : f (n + 1) = n + − f (f (n)) = n + − h( nα − n + 1) = n + − α( nα − n + 1) + nα − n + − Từ nα − n + < 2n − n + = n + 1, dẫn đến: f (n + 1) = nα + − α( nα − n + 1) Giả sử n thỏa mãn α( nα − n + 1) = n. Từ ta có (n + 1)α = nα + đó: f (n + 1) = (n + 1)α − n Nếu n không thỏa mãn α( nα − n + 1) = n α( nα − n + 1) = n + (n + 1)α = nα + 1, từ ta có: f (n + 1) = (n + 1)α + − (n + 1) (n + 1)α − n Ta kết thúc chứng minh. 10 6) Cho a = bc vào phương trình cho , ta có f (b2 c) + f (b2 (c2 + 1)) = f (bc) + f (b). Nhưng f (b) ≥ f (b2 (c2 + 1)) f (bc) ≥ f (b2 c). Do f (b2 c) = f (bc). Chọn c = 1, f (b2 ) = f (b). Tiếp theo chọn c = b), f (b3 ) = f (b2 ). Bằng quy nạp ta có: f (bk ) = f (b) ∀k ≥ pni i ) = f (pi ) pi số nguyên tố. n 7) Sử dụng (5) (6) ta có f ( Xét hàm số f (x) xác định : io f (1) = rs f (2) = f (p) = với số nguyên tố p cho p = (mod 4) p = 2. Ve f (p) = ap ≤ với số nguyên tố p lại ( ap số nguyên không dương.) f ( pni i ) = f (pi ) pi số nguyên tố. Ta chứng minh f (x) thỏa mãn điều kiện : Hiển nhiên a|b f (a) ≥ f (b) f (1 × 1) + f (12 + 12 ) = f (1) + f (1) = D em o f (a × 1) + f (a2 + 1) = f (a) + f (1), ta có ước nguyên tố p a2 + thỏa mãn p = (mod 4). Với số nguyên a, b > bất kì, gọi : - pi ước nguyên tố a không chia hết b. - qi ước nguyên tố b không chia hết a. - ri ước nguyên tố a b. f (a) = f (pi ) + f (ri ). f (b) = f (qi ) + f (ri ). f (ab) = f (pi ) + f (a2 + b2 ) = f (qi ) + f (ri ) + f (ri ). f (si ). a b )2 + ( )2 . Nhưng tương tự (5) ta có gcd(a, b) gcd(a, b) ước nguyên tố A số nguyên tố thỏa si = (mod 4)và f (A) = 0. Suy f (a2 + b2 ) = f (ri ). Ở si ước nguyên tố A = ( 35 Hay f (ab) + f (a2 + b2 ) = f (a) + f (b). Và ta có nghiệm phương trình hàm : Cho M số nguyên, hàm f xác định sau: f (2) = M . io f (p) = M với số nguyên tố p thỏa mãn p = (mod 4). n f (1) = M . f (p) = M + ap với số nguyên tố p lại (ở ap số nguyên không dương ). 5.3 pni i ) = M + (f (pi ) − M ) pi số nguyên tố. rs f( Bài tập áp dụng. 1, f (m.n) = f (m).f (n) 2, f (m)|f (n) ⇔ m|n. Ve 21. Cho f : N∗ −→ N∗ song ánh. Chứng minh điều kiện sau tương đương: D em o 22. ( Một chút mở rộng cho Ví dụ ) Tìm tất hàm số f : Z → Z thỏa mãn: a, f (x + 22) = f (x) b, f (x2 y) = f (x)2 f (y) với x, y ∈ Z2 . 23. ( China 1996 ) Cho A = {1; 2; .; 17} hàm số f : A → A. Xác định f [1] (x) = f (x) f [k+1] (x) = f (f [k] (x)) với k ∈ N. Tìm số tự nhiên lớn M cho tồn đơn ánh f : A → A thỏa mãn điều kiện sau : 1, Nếu m < M ≤ i ≤ 16 thì: f [m] (i + 1) − f [m] (i) ≡ ±1 mod 17 2, Với ≤ i ≤ 16 : f [M ] (i + 1) − f [M ] (i) ≡ ±1 mod 17 36 24. Với số nguyên dương k tồn hay không hàm số f : N −→ Z thỏa mãn : 1, f (1995) = 1996 2, f (xy) = f (x) + f (y) + kf (gcd(x, y)) với x; y ∈ N ? 25. Tìm tất hàm số f : N −→ N thỏa mãn : f (m)f (n) . d 3, Với m ∈ N, ta có f 2000 (m) = m. rs 26. Cho hàm số f : N ∪ {0} −→ N thỏa mãn điều kiện. io 2, Nếu d = gcd(m, n), f (mn) = n 1, f (m) = m = 1. 1, f (0) = 0, f (1) = Ve 2, f (n + 2) = 23 · f (n + 1) + f (n), n = 0, 1, . . Chứng minh với m ∈ N,tồn số d ∈ N cho m|f (f (n)) ⇐⇒ d|n. 27. Cho hàm số f : N∗ −→ N∗ thỏa mãn: D em o 1, f (1) = a 2, f (n2 f (m)) = mf (n)2 Chứng minh rằng: a, f (m).f (n) = af (mn) b, a | f (n), ∀n ∈ N∗ . 28. Tìm tất hàm f : Z −→ Z thỏa mãn: f (x + y + f (y)) = f (x) + 2y, ∀x, y ∈ Z 29. Tìm tất hàm f : N −→ N thỏa mãn: gcd(f (m), f (n)) = ⇐⇒ gcd(m, n) = 30. Tìm tất hàm f : Z −→ Z thỏa mãn: f (f (n)) + f (n + 1) = 2n + f (n) ≥ n − 1. 37 31. Cho f : Z −→ Z: 1, f (p) = 1∀ với số nguyên tố p 2, f (ab) = af (b) + bf (a) Chứng minh : n a, Tồn hàm số f . io b, Tìm n cho f (n) = n. rs 32. Cho f hàm số f : N ∪ {0} −→ N, thỏa mãn điều kiện: 1, f (0) = 0, f (1) = 1, Ve 2, f (n + 2) = 23 · f (n + 1) + f (n), n = 0, 1, . . . . Chứng minh với m ∈ N, tồn số d ∈ N cho m|f (f (n)) ⇔ d|n. 33. Cho g(n) hàm số xác định : D em o g(1) = 0, g(2) = g(n + 2) = g(n) + g(n + 1) + 1, n ≥ 1. Chứng minh n > số nguyên tố n chia hết g(n) · (g(n) + 1). 34. Cho đa thức P (x) ∈ Z[x], P (x) = a0 + · · · + ap−1 xp−1 số nguyên tố p > thỏa mãn : Nếu p không chia hết a − b p không chia hết P (a) − P (b).Chứng minh p|ap−1 . 35. Cho hàm số f : Z −→ Z f không đa thức. Giả sử ∀a, b, m ∈ Z , a ≡ b mod m ta có f (a) ≡ f (b) mod m. Chứng minh với số nguyên dương k ta có : |f (n)| = +∞ n→∞ nk lim 36. ( Việt Nam 1997 ) Cho hàm số f : N → Z xác định f (0) = 2; f (1) = 503; f (n + 2) = 503f (n + 1) − 1996f (n). Với k ∈ N chọn số nguyên s1 , s2 , ., sk không bé k cho pi ước nguyên tố f (2si ). Chứng minh : pi | 2t k | 2t . 38 37. ( Balkan MO 2006, Bài số ) Cho số nguyên m dãy số (an )∞ n=0 xác định a0 = a ∈ N, an an ≡ (mod 2), an+1 = an + m trường hợp lại . Tìm giá trị a cho an dãy tuần hoàn. f (k) số nguyên với k = 1, 2, ., p − 1. p io 1, n 38. Cho p số nguyên tố lẻ q số nguyên không chia hết cho p. Giả sử f : {1, 2, 3, .} → R hàm thỏa mãn đồng thời hai điều kiện sau: Khi p−1 f (k) · k=1 rs 2, f (k) + f (p − k) số nguyên chia hết cho p với k = 1, 2, ., p − 1. q q = p p p−1 f (k) − k=1 p−1 Ve Bài toán dùng để chứng minh toán. Bài 1. Cho p, q số nguyên dương nguyên tố nhau. Chứng minh p−1 D em o k=1 kq (p − 1)(q − 1) = p Bài 2. Cho p số nguyên tố lẻ. Chứng minh p−1 k=1 (p − 2)(p − 1)(p + 1) k3 = p Bài 3. Cho p nguyên tố lẻ q số nguyên không chia hết cho p. Chứng minh p−1 (−1)k k=1 (p − 1)(q − 1) k2 q = p Bài 3. Cho p số nguyên tố lẻ. Chứng minh p−1 k=1 kp − k p+1 ≡ p 39 (mod p) Hàm số hệ đếm số. 6.1 Lý thuyết. io n Hệ đếm số phần quan trọng liên quan đến thuật toán tin học. Trong phân môn toán, hệ đếm số dùng để xây dựng nhiều dãy số có tính chất thú vị. Nhìn phương diện số khác, khó nhận quy luật, chọn số toán trở nên vô đơn giản. Xin nhắc lại với b số nguyên dương lớn hay số nguyên dương N biểu diễn cách dạng N = a1 a2 .ak |(b) = a1 bk−1 + a2 bk−2 . + ak với ≤ a1 ≤ b − 1, ≤ a2 , ., ak ≤ b − 1. 6.2 Ve rs Đó định nghĩa hệ đếm số dạng nhất. Tuy nhiên, lấy dãy số nguyên (có trị tuyệt đối tăng nghiêm ngặt) làm hệ đếm số ví dụ hệ đếm số (-2), hệ đếm số Fibonacci (3 = - + 1, 17 = 13 + + .). Các hệ đếm thường sử dụng hệ đếm số số 3. Một vài ví dụ minh họa. Ví dụ 1. Tìm tất hàm số f : N∗ −→ N∗ thoả mãn điều kiện: D em o 1, f (1) = 1, f (3) = 3. 2, f (2n) = f (n). 3, f (4n + 1) = 2f (2n + 1) − f (n). 4, f (4n + 3) = 3f (2n + 1) − 2f (n). Giải. Hiển nhiên tồn hàm số nhất. Ta chứng minh biểu diễn nhị phân n có dạng a1 a2 .am |2 f (n) = am am−1 .a1 |2 . Thật vậy: Với n = 1, kết luận hiển nhiên đúng. Giả sử với k < n kết luận đúng. Ta xét trường hợp sau: Trường hợp 1. Nếu n số chẵn, đặt n = 2k. Giả sử k = a1 a2 .am |2 n = a1 a2 .am |2 . Khi kết luận hiển nhiên đúng. Trường hợp 2. Nếu n số lẻ. Đến đây, ta tiếp tục khoanh vùng giá trị n. 40 n có dạng 4k + 1. Giả sử k = a1 a2 .am |2 n = a1 a2 .am 01 |2 . Mặt khác, ta có : uk = ak−2 .a2 a1 |2 u2k+1 = 1ak−2 .a2 a1 |2 Suy ra: n un = u2k+1 + (u2k+1 − uk ) = 10ak−2 .a2 a1 |2 Kết luận trường hợp này. io n có dạng 4k + 3. Tương tự. rs Vậy hàm số đầu hàm thỏa mãn ra. ∇ 1, f (1) = 1. 2, f (2n) = f (n). 3, f (2n + 1) = + f (2n). Ve Ví dụ 2. Tìm tất hàm số f : N∗ −→ N∗ thoả mãn điều kiện: D em o Giải. Cũng ví dụ trên, ta nhận thấy tồn hàm số nhất. Tiếp theo ta chứng minh quy nạp mệnh đề f (n) số số biểu diễn nhị phân n. Thật vậy: Với n = 1, hiển nhiên đúng. Giả sử với k < n đúng. Xét n = k + 1. Ta xét trường hợp sau: Trường hợp 1. Nếu k số chẵn, đặt k = 2m. Khi : f (k + 1) = f (2m + 1) = + f (2m) = + f (m) Nếu m = a1 a2 .an |2 2m + = a1 a2 .an |2 Suy số chữ số biểu diễn nhị phân 2m + m 1. Kết luận trường hợp này. Trường hợp 2. Nếu k số lẻ, đặt k = 2m + 1. Khi : f (k + 1) = f (2(m + 1)) = f (m + 1) 41 Tương tự số chữ số biểu diễn nhị phân 2m + số chữ số biểu diễn nhị phân m. Chứng minh kết thúc. ∇ n Ví dụ 3. Tìm tất hàm số f : N∗ −→ N∗ thoả mãn điều kiện: io 1, f (1) = 1. 2, f (2n + 1) = f (2n) + 1. rs 3, f (2n) = 3f (n). Giải. Theo tính hàm số, ta chứng minh quy nạp mệnh đề sau : Nếu viết n hệ nhị phân ak ak−1 .a0 |2 f (n) = ki=0 3i . Ve Với n = 1, hiển nhiên đúng. Giả sử 2n + = ak ak−1 .a1 |2 , suy 2n = ak ak−1 .a1 |2 n = ak ak−1 .a1 |2 . Kiểm tra giả thiết: k 3i + 30 .1 f (2n + 1) = D em o i=1 k = 3i + 30 .0 + 30 .1 = f (2n) + i=1 Và: k k−1 i f (2n) = 3i ) = 3f (n) = 3( i=1 i=1 Bài toán giải hoàn chỉnh. ∇ Ví dụ 4. ( Bài toán cổ Josephus [1] ) Giả sử Josephus có n − người bạn, n người đứng thành vong tròn đánh số từ đến n theo chiều kim đồng hồ tự sát theo nguyên tắc, người thứ cầm dao đếm tự sát, người thứ đếm tự sát. Quá trình dừng lại người. Gọi f (n) hàm số biểu thị vị trí người sống sót đó. Tìm f (n). Giải: 42 Nếu n = 2k. Sau vòng 1, người vị trí lẻ. Số người đánh lại thành 1, 2, ., k. Nếu lượt trước người có số 2i − sau mang số i. Người sống sót có số cũ f (2k), sau mang số f (k). Vậy ta có: f (2k) = 2f (k) − io f (2k + 1) = 2f (k) + n Nếu n = 2k + 1. Sau vòng ( ta ngầm hiểu có 2k + người cách tính trùng người thứ thành 2k + ), lại người số 3, 5, ., 2k + 1, đánh số lại 1, 2, ., k. Nếu lượt trước người có số 2i + sau mang số i. Người sống sót có số cũ f (2k + 1), sau mang số f (k) .Vậy ta có: rs Như f (1) = 1, f (2k) = 2f (k) − 1, f (2k + 1) = 2f (k) + 1. Ta chứng minh quy nạp biểu diễn số n ak ak−1 .a1 |2 ,ak = 1, với i = k ∈ {0, 1} f (n) = ak−1 .a1 ak |2 . Thật vậy. Với n = hiển nhiên đúng. Ve Giả sử với k < n mệnh đề đúng. Ta có trường hợp: Trường hợp 1. Nếu n số chẵn, đặt n = 2m. Khi m = bk bk−1 .b1 |2 2m = bk bk−1 .b1 |2 . Và D em o f (2m) = 2f (m) − = 2. bk−1 2k + . + b1 .2 + − = bk−1 .b1 01 |2 Đúng. Trường hợp 2. Nếu n số lẻ, đặt n = 2m + 1. Khi m = bk bk−1 .b1 |2 2m + = bk bk−1 .b1 |2 . Và f (2m + 1) = 2f (m) + = 2. bk−1 2k + . + b1 .2 + + = bk−1 .b1 11 |2 Đúng. Bài toán giải hoàn chỉnh. [1] Câu chuyện truyền thuyết. Vaspasien Hoàng đế La Mã kỉ thứ (từ năm 69 đến năm 79, theo Dương lịch). Thời có Josephus nhà viết sử bị Vaspasien truy lùng can tội chống lại triều đình. Tục truyền Vaspasien tìm chỗ ẩn náu 100 người chống đối kêu gọi họ hàng, không tàn sát tất cả. Đa số muốn tự sát có người nói với Josephus hoàn cảnh riêng nên muốn đầu hàng. Josephus hiểu hoàn cảnh người đặt quy tắc toán trên. Hỏi Josephus phải xếp để người sống ? 43 ∇ Ví dụ 5. Tồn hay không hàm số f : {1, 2, ., n} −→ N thỏa mãn: 1. f đơn ánh. n 2. f (ab) = f (a) + f (b) với a, b ∈ {1, 2, ., n} ab ≤ n. io Giải: Ta hàm số f sau: Kí hiệu số nguyên tố bé n theo thứ tự tăng dần p1 , p2 , ., pk . Khi đó, a = ki=1 pαi i , αi ∈ N, αi < n + f (pi ) = (n + 1)i , f (a) = ki=1 αi (n + 1). Ta chứng minh hàm số thỏa mãn điều kiện. rs Thật vậy, với a = ki=1 pαi i , b = ki=1 pβi i ( có giá trị αi βj khác ), k k f (a) = i=1 αi (n + 1) f (b) = i=1 βi (n + 1), hiển nhiên ta biểu diễn f (a), f (b) cách sang hệ số n + f (a) = f (b). Mặt khác: k (pi )αi +βi Ve f (ab) = f ( i=1 k = (αi + βi ).f (pi ) i=1 k D em o = k αi .f (pi ) + i=1 βi .f (pi ) i=1 = f (a) + f (b), Hay f (ab) = f (a) + f (b). 6.3 Bài tập áp dụng. 39. ( IMO 1988, số ) Hàm số f xác định tập hợp số nguyên dương sau 1, f (1) = 1, f (3) = 3, 2, f (2n) = f (n), f (4n + 1) = 2f (2n + 1) − f (n), f (4n + 3) = 3f (2n + 1) − 2f (n) Tìm số giá trị n cho f (n) = n, ≤ n ≤ 1988. 44 40. ( IMO shortlist 2000 ) Cho hàm số f : N∗ −→ N∗ thoả mãn điều kiện: 1, f (4n) = f (2n) + f (n). 2, f (4n + 2) = f (4n) + 3, f (2n + 1) = f (2n) + 1. n Chứng minh với số nguyên dương m, số số nguyên dương n cho ≤ n < 2m f (4n) = f (3n) f (2m+1 ). io 41. Hàm số f : N∗ −→ N xác định sau rs 1, f (1) = 2, f (2) = 2, f (3n) = 3f (n), f (3n + 1) = 3f (n) + 2, f (3n + 2) = 3f (n) + 1. Tìm số số n ≤ 2006 thỏa mãn f (n) = 2n. Ve 42. Hàm số f : N × N −→ N xác định sau x + y ≡ (mod 2), D em o 1, f (0, 0) = 0.  x y  f( , )   2 2, f (x, y) =   f ( x , y ) + 2 x, y ∈ N. Chứng minh: x , x b, f (x, y) = f ( , a, f (x, y) = f ( x + y ≡ (mod 2) y ) ⇐⇒ x y tính chẵn lẻ. y ) + ⇐⇒ x y khác tính chẵn lẻ. c, f (x, y) = ⇐⇒ x = y. 43. Hàm số f : N∗ −→ N∗ số số khai triển nhị phân n. Chứng minh rằng: a, f (n2 ) ≤ f (n)(1 + f (n)) đẳng thức xảy vô số điểm. b, Tồn dãy vô hạn (un )+∞ i=1 cho: f (u2k ) =0 k→∞ f (uk ) lim 45 44. ( China 1995 ) Hàm số f xác định tập hợp số nguyên dương sau: 1, f (1) = 1. 2, 3f (n)f (2n + 1) = f (2n) (1 + 3f (n)). Tìm số k, m cho f (m) + f (k) = 293. io 45. Hàm số f xác định tập hợp số nguyên dương sau: n 3, f (2n) < 6f (n). 1, f (3n) = 2f (n). rs 2, f (3n + 1) = f (3n) = 1. f (3n + 2) = f (3n) + 2. Ve Tìm tất giá trị n ∈ 0, 1, 2, ., 2003 cho f (2n) = 2f (n). 46. ( Balkan MO ) Hàm số f xác định tập hợp số nguyên dương sau: 1, f (2n + 1)2 − f (2n)2 = 6f (n) + 1. D em o 2, f (2n) ≥ f (n). Hỏi có giá trị n mà f (n) ≥ 2003. 46 7.1 Ý tưởng liên kết hàm số toán rời rạc. Lý thuyết. Một vài ví dụ minh họa. rs 7.2 io n Từ lâu ta biết việc sử dụng đẳng thức truy hồi ( dãy số ) hay tính chất ánh xạ việc giải toán rời rạc. Phương pháp tỏ rõ lợi ta phải làm việc với toán đòi hỏi tính xâu chuỗi trường hợp nhỏ lẻ toán tổng quát. Bằng liên tưởng đó, ta chuyển xử lý toán đại số thúy. Trong phần này, ta xét nhìn theo hướng ngược lại, nơi đó, toán hàm số chuyển toán rời rạc. Ý tưởng thực mẻ tác giả mong muốn có trao đổi với bạn thầy cô sâu mảng tập này. Ví dụ 1. Tồn hay không hàm số f : {1, 2, ., n} × {1, 2, ., n} −→ Z thỏa mãn với số x, y, a ∈ {1, 2, ., n}. Ve 1, f (x, y) = ⇐⇒ x2 + y ∈ P. Và f (x, y)2 = trường hợp lại. 2, n i=1 f (a, i), n i=1 f (i, a) ∈ {−1, 0, 1}. D em o Với P tập số nguyên tố . Giải: Điều kiện làm ta liên tưởng đến tính chất số học quen thuộc : Một số nguyên tố dạng 4k + viết dạng tổng số phương. Tuy nhiên ta thấy mệnh đề bẫy việc kết nối trở nên khó khăn. Hàm biến giúp ta liên tưởng đến hệ trục tọa độ. Và toán sau xuất hiện: Ta cụ thể hóa giá trị hàm số 0, -1, trạng thái điểm có hệ trục tọa độ không màu, màu trắng màu đỏ, tương ứng. Suy tập điểm đó, điều kiện đáp ứng, tức số điểm đỏ trắng không 1, để đơn giản chọn đường thẳng. Ta phát biểu lại toán: Cho số hữu hạn điểm mặt phẳng, với điểm nguyên có tô màu điểm với màu đỏ trắng cho đường thẳng L chứa điểm nói số điểm đỏ trắng L không điểm. 47 Đây IMO 1986. Câu trả lời có dĩ nhiên, hàm số toán tồn tại. Một phát biểu khác toán dạng sau : ∇ n Ví dụ 1’. Tồn hay không hàm số f : {1, 2, ., n} × {1, 2, ., n} −→ {−2, −1, 0, 1, 2} thỏa mãn với số x, y, a ∈ {1, 2, ., n}. n i=1 f (i, a) | ≤ 3, | n j=1 f (a, j) |≤ 3. D em o Ve rs 2, | io 1, f (x, y) ≡ x2 − y mod 3. 48 Một số toán chưa có lời giải. Kết thúc chuyên đề số toán chưa có lời giải ( theo nhiều nguồn sách website toán mathlinks.ro hay nhiều trang web toán nước khác ) . Đây thực toán hay đương nhiên khó. f (f (n) − n) + f (f (n) + n) = 8n io ∇ Bài số 2. Tìm tất hàm số f : N −→ N thỏa mãn: xm k ) f( k=1 f m (xk ) = k=1 D em o Ve Với m, n số tự nhiên. n rs n 49 n Bài số 1. Tìm tất hàm số f : N −→ N thỏa mãn: Tài liệu [1] Nguyễn Trọng Tuấn, Bài toán hàm số qua kì thi Olimpic . [2] Titu Andreescu - Contests Around the World 1996-1997, 1997-1998, 1999-2000 . [3] Valentine Boju, Luis Funar - The Math Problems Notebook . [4] Titu Andreescu , Razvan Gelca - Birkhauser Mathematical Olympiad Challenges . n [5] Edward Lozansky , Cecil Rousseau - Winning Solutions . [6] Marko Radovanovi’c ( The IMO Compedium Group ) - Functional Equations . io [7] Christopher G. Small - Functional Equations and How To Solve Them . [8] Trần Nam Dũng, Dương Bửu Lộc - Chuyên đề Phương trình hàm tập số nguyên . [10] http://www.mathsope.org . D em o Ve [11] http://www.diendantoanhoc.net . rs [9] http://www.mathlinks.ro . 50