Luận văn Một số lớp phương trình hàm trong số học

g tỏ không tồn tại hàm f thỏa mãn bài ra. 30 Bài toán 2.14 (France Selection Test 2007). Tìm tất cả các hàm số f : N→ Z thỏa mãn điều kiện f(x− y + f(y)) = f(x) + f(y),∀x, y ∈ N. (2.15) Lời giải. Kí hiệu P (u, v) chỉ phép thay x bởi u và y bởi v vào (2.15). Đặt f(0) = a. Khi đó ta có P (0, 0)⇒ f(a) = 2a⇒ f(a)− a = a, P (0, a)⇒ f(a) = a+ f(a)⇒ a = 0⇒ f(0) = 0, và P (0, x)⇒ f(f(x)− x) = f(x),∀x ∈ N. (2.16) Thực hiện P (x, f(y)− y) ta được f(x− f(y) + y + f(f(y)− y)) = f(x) + f(f(y)− y),∀x, y ∈ N. (2.17) Thay (2.16) vào (2.17) ta được f(x+ y) = f(x) + f(y),∀x, y ∈ N. Từ đây áp dụng kết quả bài toán 2.1, ta suy ra f(x) = ax,∀x ∈ N (a = f(1) là hằng số nguyên ). Thay vào (2.15) ta được a(x− y + ay) = ax + ay,∀x, y ∈ N ⇔ (a2 − 2a)y = 0,∀y ∈ N. Vậy a ∈ {0, 2}, do đó có hai hàm số thỏa mãn các yêu cầu đề bài là f(x) = 0, và f(x) = 2x,∀x ∈ N. Bài toán 2.15 (Hong Kong Team Selection Tests 2008). Giả sử hàm số f : N→ Z thỏa mãn f(1) = 1, f(2) = 20, f(−4) = −4 và f(x+ y) = f(x) + f(y) + axy(x+ y) + bxy + c(x+ y) + 4,∀x, y ∈ N. (2.18) trong đó a, b, c là các hằng số nguyên. 31 a) Tìm hàm số f. b) Giả sử f(x) ≥ mx2 + (5m+ 1)x+ 4m,∀x ∈ N. Hãy tìm giá trị nhỏ nhất củam. Lời giải. Kí hiệu P (u, v) chỉ việc thay x bởi u và thay y bởi v vào (2.18) a) Ta có P (0, 0)⇒ f(0) = −4 P (0, y)⇒ cy = 0,∀y ∈ N⇒ c = 0 P (1,−1)⇒ −4 = 1 + f(−1)− b− 4⇒ f(−1) = b− 9 P (−1,−1)⇒ f(−2) = 2f(−1)− 2a+ b+ 4 = −2a+ 3b− 14 P (−2,−2)⇒ f(−4) = 2f(−2)− 16a+ 4b+ 4 = −20a+ 10b− 24 Do đó − 4 = −20a+ 10b− 24⇔ 20a− 10b = −20⇔ 2a− b = −2. (2.19) Và P (1, 1)⇒ f(2) = 2f(1) + 2a+ b+ 4⇒ 2a+ b = 14. (2.20) Từ (2.19) và (2.20) suy ra a = 3, b = 8. Vậy f(x+ y) = f(x) + f(y) + 3xy(x+ y) + 8xy + 4,∀x, y ∈ N. (2.21) Xét hàm số g : N→ Z như sau g(x) = f(x)− (x3 + 4x2 − 4)⇔ f(x) = g(x) + (x3 + 4x2 − 4). Thay vào (2.21), suy ra, với mọi x, y ∈ N, ta có g(x+ y) + x3 + y3 + 3xy(x+ y) + 4(x+ y)2 − 4 = = g(x) + g(y) + (x3 + 4x2 − 4) + (y3 + 4y2 − 4) + 3xy(x+ y) + 8xy + 4 = g(x) + g(y) + x3 + y3 + 3xy(x+ y) + 4(x+ y)2 − 4. Như vậy g(x + y) = g(x) + g(y),∀x, y ∈ N. Từ đây áp dụng kết quả bài toán 2.1, suy ra g(x) = ax,∀x ∈ Z (a = g(1) là hằng số nguyên ). 32 Mà g(1) = f(1)− 1 = 0 nên a = 0. Do đó g(x) = 0,∀x ∈ N hay f(x) = x3 + 4x2 − 4,∀x ∈ N. Thử lại thấy hàm số trên thỏa mãn yêu cầu bài ra. b)f(x) ≥ mx2 + (5m+ 1)x+ 4m,∀x ∈ N. Khi đó x3 + 4x2 − 4 ≥ mx2 + (5m+ 1)x+ 4m,∀x ∈ N ⇔ x3 + 4x2 − x− 4 ≥ m(x2 + 5x+ 4),∀x ∈ N ⇔ (x+ 1)(x− 1)(x+ 4) ≥ m(x + 1)(x+ 4),∀x ∈ N ⇔ x− 1 ≥ m,∀x ∈ N Vậy giá trị nhỏ nhất củam là −1, đạt được khi x = 0. 33 Chương 3 Các dạng toán liên quan Trong chương này sẽ trình bày các dạng toán từ các đề thi Olympic các nước và quốc tế liên quan đến tính toán, ước lượng và các tính chất số học (nguyên tố, chính phương, tính đơn điệu, tính tuần hoàn. . . ) của các hàm số trên các tập số tự nhiên, tập số nguyên và tập số hữu tỷ. 3.1 Phương trình hàm trên N và trên Z 3.1.1 Lớp các bài toán áp dụng nguyên lý quy nạp toán học Nguyên lý quy nạp toán học là một trong những nguyên lý quen thuộc và rất quan trọng trong chương trình toán phổ thông. Nguyên lý này đôi khi là một trong những công cụ rất hữu hiệu để giải quyết một lớp bài toán khó liên quan đến tập số tự nhiên. Vì vậy nó cũng là một công cụ hữu hiệu dùng để công phá các bài phương trình hàm trên các tập rời rạc. Trước tiên ta xét bài toán sau. Bài toán 3.1 (Puerto Rico Team Selection Test 2012). Tìm tất cả các hàm số f : N∗ → N∗ sao cho 1) f(2) = 2; 2) f(mn) = f(m)f(n);∀m,n ∈ N∗; 3) f(m) < f(n),∀m < n. Lời giải. Giả sử tồn tại hàm số f thỏa mãn các yêu cầu bài toán. Khi đó, cho n = 1, 34 ta có f(1) = f(1.1) = f(1).f(1) suy ra f(1) = 1. Ta thấy rằng 2 = f(2) < f(3) < f(4) = f(2.2) = f(2).f(2) = 4. Từ tính chất sắp thứ tự tốt của tập số tự nhiên ta suy ra f(3) = 3. Tương tự ta có 4 = f(4) < f(5) < f(6) = f(2.3) = f(2).f(3) = 6. Từ đây ta cũng suy ra f(5) = 5. . . Ta sẽ chứng minh f(n) = n,∀n ∈ N∗. Thật vậy, ta chứng minh bằng phương pháp quy nạp. Ta có f(1) = 1, f(2) = 2. Giả sử khẳng định f(n) = n đã đúng tới n = k, (k ≥ 2). Lúc này f(k) = k, ta cần chứng minh f(k + 1) = k + 1. Nếu k là số lẻ thì k + 1 là số chẵn và f(k + 1) = f ( 2. k + 1 2 ) = f(2)f ( k + 1 2 ) = 2. k + 1 2 = k + 1. Nếu k là số chẵn thì k + 2 là số chẵn và do k + 2 2 ≤ k nên theo giả thiết quy nạp ta có f ( k + 2 2 ) = k + 2 2 . Vậy f (k + 2)) = f ( 2. k + 2 2 ) = f(2).f ( k + 2 2 ) = 2. k + 2 2 = k + 2. Do k = f(k) < f(k + 1) < f(k + 2) = k + 2 suy ra f(k + 1) = k + 1. Vậy khẳng định vẫn còn đúng với n = k + 1. Theo nguyên lý quy nạp, ta có f(n) = n,∀n ∈ N∗. Thử lại, ta thấy hàm này thỏa mãn yêu cầu bài ra. Nhận xét Trong lời giải bài toán trên, ta đã sử dụng tính chất quan trọng là thứ tự trên N∗ và phương pháp quy nạp toán học. Tính chất k < f(k + 1) < k + 2 ⇒ f(k + 1) = k + 1,∀k ∈ N là một tính chất rất quan trọng đã được sử dụng. Ngoài ra trong lời giải trên ta đã sử dụng hiệu quả cả ba điều kiện. Điều gì sẽ xảy ra nếu ta làm yếu đi một điều kiện ? Câu trả lời sẽ được biết khi ta xét tiếp bài toán sau. 35 Bài toán 3.2. Tìm tất cả các hàm số f : N∗ → N∗ sao cho a) f(2) = 2; b) f(mn) = f(m)f(n);∀m,n ∈ N∗,ƯSCLN(m,n) = 1; c) f(m) < f(n),∀m < n. Lời giải. Giả sử tồn tại hàm số f thỏa mãn các yêu cầu bài toán. Khi đó, cho n = 1, ta có f(1) = f(1.1) = f(1).f(1) suy ra f(1) = 1. Ta thấy rằng f(3).f(5) = f(15) < f(2).f(9) < f(2)f(10) = f(2).f(2).f(5). Suy ra f(3) < f(2)f(2) = 4.Mà 2 = f(2) < f(3) < 4 nên f(3) = 3. Từ đó ta tính được f(4) = 4, f(5) = 5, f(6) = 6, f(7) = 7, f(8) = 8, f(9) = 9, f(10) = 10. Do đó f(n) = n,∀n ∈ N∗, n ≤ 10. Ta chứng minh f(n) = n,∀n ∈ N∗. Giả sử f(k) = k (k ∈ N∗, 10 ≤ k ≤ n) . Ta cần chứng minh điều khẳng định vẫn còn đúng với n = k + 1. - Nếu k là số chẵn, ta xét hai trường hợp sau + Trường hợp k = 2α (2l + 1) , α, l ∈ N∗. Khi đó ta có f(k) = f(2α(2l + 1)) = f(2α)f(2l + 1) = 2α (2l + 1) = k. + Trường hợp k = 2α, α ∈ N∗. Ta có f(k+2) = f (2α + 2) = f ( 2 ( 2α−1 + 1 )) = f(2).f ( 2α−1 + 1 ) = 2 ( 2α−1 + 1 ) = 2α+2 = k+2. Mặt khác k − 1 = f(k − 1) < f(k) < f(k + 1) < f(k + 2) = k + 2. Do đó f(k) = k, f(k + 1) = k + 1. - Nếu k là số lẻ, ta xét hau trường hợp sau + Trường hợp k + 1 = 2α (2l + 1) , α, l ∈ N∗. Khi đó 0 < 2α ≤ n, 0 < 2l + 1 ≤ n. 36 Theo giả thiết quy nạp ta có f(k + 1) = f (2α (2l + 1)) = f (2α) f (2l + 1) = 2α (2l + 1) = k + 1. Mà k − 1 = f(k − 1) < f(k) < f(k + 1) = k + 1 nên f(k) = k. + Trường hợp k + 1 = 2α, α ∈ N. Ta có f((k+1)+2) = f (2α + 2) = f ( 2 ( 2α−1 + 1 )) = f(2).f ( 2α−1 + 1 ) = 2 ( 2α−1 + 1 ) = 2α+2 = k Mà k − 1 = f(k − 1) < f(k) < f(k + 1) < f(k + 2) < f(k + 3) = k + 3 nên f(k) = k, f(k + 1) = k + 1, f(k + 2) = k + 2. Theo nguyên lý quy nạp ta có f(n) = n,∀n ∈ N∗. Thử lại, thấy hàm số này thỏa mãn bài ra. Nhận xét Khi điều kiện b) được làm yếu đi so với điều kiện 2) của bài toán 3.1 thì điểm mấu chốt ở đây là chứng minh được f(3) = 3. Nếu thay đổi điều kiện 1) của bài toán 3.1 thì có thể xảy ra trường hợp bài toán không có nghiệm. Ta đi xét bài toán sau. Bài toán 3.3. Tìm tất cả các hàm số f : N∗ → N∗ sao cho 1) f(2) = 3; 2) f(mn) = f(m)f(n);∀m,n ∈ N∗; 3) f(m) < f(n),∀m < n. Lời giải. Giả sử tồn tại hàm f thỏa mãn điều kiện đề bài. Đặt f(3) = a, ta được 27 = 33 = f 3(2) = f ( 23 ) < f ( 32 ) = f 2(3) = a2 suy ra a > 5. Ta lại có a3 = f 3(3) = f ( 33 ) < f ( 25 ) = 35 < 343 = 73. Suy ra a 243 và f(256) = f ( 28 ) = (f(2)) 8 = 6561; f(243) = f ( 35 ) = (f(3)) 5 = 7776. 37 Suy ra f(256) < f(243) (mâu thuẫn với điều kiện 3)). Vậy không tồn tại hàm số f thỏa mãn yêu cầu bài toán. Nhận xét Việc tìm ra mâu thuẫn phục vụ cho việc giải bài toán, đôi khi không phải dễ dàng. Việc tính toán từng giá trị để phát hiện điều mâu thuẫn cũng là một phương pháp thường gặp. Đối với bài toán này, để có sự so sánh suy ra mâu thuẫn, trước hết ta tính bảng giá trị sau f(2) f(3) f(4) f(6) f(8) f(9) f(12) f(16) f(18) f(24) f(27) f(32) 3 a 9 3a 27 a2 9a 81 3a2 27a a3 243 Dựa vào bảng trên ta thấy rằng 27 ≤ a2 ⇒ a > 5 và a3 ≤ 243 ⇒ a < 7, do đó a = 6. Từ f(2) = 3, f(3) = 6, ta tìm kiếm sự mâu thuẫn sao cho 2k > 3l nhưng f ( 2k ) < f ( 3l ) . Sau khi thử các giá trị, ta tìm thấy sự mâu thuẫn khi k = 8 và l = 5. Bài toán 3.4 (IMO 1982). Tìm tất cả các hàm số f(n) xác định với mọi giá trị nguyên dương n và nhận giá trị nguyên không âm. Ngoài ra, biết rằng f(2) = 0, f(3) > 0, f(9999) = 3333 và f(m+ n)− f(m)− f(n) = 0 hoặc 1. Hãy tìm f(1982). Lời giải. Giả sử f(n) là hàm số thỏa mãn các yêu cầu bài toán. Ta có f(m+ n) = f(m) + f(n) + a, với a ∈ {0; 1} . Cho m = n = 1, ta được f(2) = 2f(1) + a suy ra 2f(1) ≤ f(2) = 0 suy ra f(1) = 0. Ta lại có f(3) = f(2) + f(1) + a = a suy ra f(3) = 1. Ta sẽ chứng minh bằng quy nạp rằng với mọi n ∈ N∗ thì f(3n) ≥ n. (3.1) Thật vậy + Với n = 1 ta có f(3.1) = 1 ≥ 1. Vậy (3.1) đúng với n = 1. 38 + Giả sử (3.1) đúng với n = k, (k ≥ 1). Ta chứng minh (3.1) cũng đúng với n = k + 1. Ta có f(3(k + 1)) = f(3k + 3) = f(3k) + f(3) + a ≥ f(3k) + f(3) ≥ k + 1. Vậy (3.1) đúng với n = k + 1. Do đó f(3n) ≥ n,∀n ∈ N∗. Vì f(9999) = 3333 nên suy ra f(3.3332) = 3332. Thật vậy + Nếu f(3.3332) > 3332 thì f(3.3332) ≥ 3333 = f(3.3333)⇒ f(9999) ≤ f(9996). + Mặt khác f(9999) = f(9996) + f(3) + a > f(9996) + a ≥ f(9996), đến đây ta gặp mâu thuẫn, vậy f(3.3332) = 3332. Tương tự ta suy ra rằng f(3n) = n,∀n ≤ 3333. Ta lại có f(3n) = f(2n) + f(n) + a = f(n) + f(n) + f(n) + a+ a = 3f(n) + 2a. Suy ra 3f(n) ≤ f(3n) ≤ 3f(n) + 2⇒ f(n) ≤ f(3n) 3 ≤ f(n) + 2 3 . (Do min tại a = 0 và max tại a = 1). Do đó f(n) = [ f(3n) 3 ] = [n 3 ] ,∀n ≤ 3333. Khi đó ta tính được f(1982) = [ 1982 3 ] = 660. Bài toán 3.5 (Romania District Olympiad 2010). Tìm tất cả các hàm số f : N∗ → N∗ thỏa mãn f(n) + f(n+ 1) + f(f(n)) = 3n+ 1,∀n ∈ N∗. (3.2) Lời giải. Từ (3.2) cho n = 1 ta được f(1) + f(2) + f(f(1)) = 4. Do f : N∗ → N∗ nên chỉ có hai trường hợp sau có thể xảy ra. 39 - Trường hợp 1: f(1) = 1 khi đó f(2) = 2. Giả sử f(k) = k, (k ∈ N∗), khi đó theo (3.2) ta có f(k) + f(k + 1) + f(f(k)) = 3k + 1 suy ra f(k + 1) = 3k + 1− 2k = k + 1 Theo nguyên lí quy nạp suy ra f(n) = n,∀n ∈ N∗. Thử lại thấy hàm số này thỏa mãn các yêu cầu đề bài. - Trường hợp 2: f(1) = 2. Khi đó f(2) = 1, f(3) = 4 . . . Ta sẽ chứng minh bằng quy nạp f(n) = n + (−1)n+1, (∀n ∈ N∗). Ta có (3.2) đúng khi n = 1, n = 2. Giả sử (3.2) đúng khi n = k, k ∈ N∗, k ≥ 2. Khi đó f(k) = k + (−1)k+1, f(k − 1) = k − 1 + (−1)k. Theo (3.2) ta có f(k) + f(k + 1) + f(f(k)) = 3k + 1 suy ra k + (−1)k+1 + f(k + 1) + f(k + (−1)k+1) = 3k + 1. (3.3) + Nếu k chẵn (k = 2p, p ∈ N∗) thì f(k + (−1)k+1) = f(k − 1) = k − 1 + (−1)k = k. Thay vào (3.3), ta được k + (−1)k+1 + f(k + 1) + k = 3k + 1 suy ra f(k + 1) = k + 1 + (−1)k+2 + Nếu k lẻ (k = 2p+ 1, p ∈ N∗) thì f(k + (−1)k+1) = f(k + 1). Thay vào (3.3), ta được k + 1 + f(k + 1) + f(k + 1) = 3k + 1 suy ra f(k + 1) = k = k + 1 + (−1)k+2 Vậy f(k+1) = k+1+(−1)k+2. Theo nguyên lí quy nạp suy ra (3.2) đúng. Thử lại thấy hàm này thỏa mãn yêu cầu đề bài. Kết luận Các hàm số cần tìm là f(n) = n; f(n) = n+ (−1)n+1,∀n ∈ N∗. 40 Nhận xét Đối với những phương trình hàm trên tập rời rạc ta phải đặc biệt quan tâm đến tập xác định và tập giá trị của hàm số. Chẳng hạn ở bài toán 3.5, từ f(1) + f(2) + f(f(1)) = 4 và f : N∗ → N∗ ta suy ra f(1) = 1 hoặc f(1) = 2. Bài toán 3.6 (IMO 1998). Xét hàm số f : N∗ → N∗ thỏa mãn điều kiện f ( m2f(n) ) = n (f(m)) 2 ,∀m,n ∈ N∗. (3.4) Tìm giá trị nhỏ nhất của f(1998). Lời giải. Gọi S là tập tất cả các hàm thỏa mãn điều kiện của bài toán. Giả sử f(n) ∈ S. Đặt f(1) = a. Chom = 1,từ (3.4) ta được f(f(n)) = nf 2(1) = na2. (3.5) Và f ( n2f(1) ) = 1.f 2(n)⇔ f (a.n2)) = f 2(n). (3.6) Với mọim,n ∈ N ta có [f(m)f(n)]2 = [f(m)]2[f(n)]2 (3.6) = f ( an2 ) [f(m)]2 (3.4) = f ( m2f ( f ( an2 ))) (3.5) = f ( m2a3n2 ) = f ( a(amn)2 ) (3.6) = f 2 (amn) . Suy ra f(amn) = f(m).f(n), (vìf(amn), f(m), f(n) ∈ N∗) . (3.7) Từ (3.7), cho n = 1, ta được f(am) = af(m). Khi đó af(mn) = f(amn) (3.7) = f(m)f(n). (3.8) Từ (3.8), cho m = n ta được f 2(n) = a1f ( n2 ) . Ta nhận thấy rằng với mọi k ∈ N∗ thì fk(n) = ak−1f ( nk ) . (3.9) Thật vậy, ta chứng minh bằng quy nạp như sau 41 + Với k = 1 ta có f 1(n) = a0f ( n1 ) . Do đó (3.9) đúng với k = 1. + Giả sử (3.9) đúng với k = l, (l ≥ 1) . Ta có f l+1(n) = f l(n)f(n) = al−1.f ( nl ) f(n) = al.f ( nl+1 ) (do (3.8)) . Do đó (3.9) đúng với k = l+1. Theo nguyên lý quy nạp (3.9) đúng với mọi k ∈ N∗. Ta chứng minh f(n) ... a,∀n ∈ N∗. Thật vậy, với p là số nguyên tố bất kì, gọi α là số mũ lớn nhất mà a ... pα và β là số mũ lớn nhất mà f(n) ... pβ. Từ (3.9) ta thấy: Vế trái chia hết cho pkβ, vế phải chia hết cho p(k−1)α (ngoài ra f ( nk ) còn có thể có ước là pl. Suy ra với mọi k ∈ N∗ ta có kβ ≥ (k − 1)α⇒ k(β − α) + α ≥ 0⇒ β ≥ α. Do đó f(n) ... a,∀n ∈ N∗. Xét hàm số g : N∗ → N∗ xác định bởi g(n) = 1 a f(n), a ≥ 1 vì f(1) ∈ N∗. Khi đó g(a) = f(a) a = af(1) a = a. Do đó  g(mn) = 1 a f(mn) = 1 a2 f(m)f(n) = g(m)g(n); g(1) = 1 g (g(m)) = g(a)g(g(m)) a = g(ag(m)) a = g(f(m)) a = f(f(m)) a2 = m (3.10) Và g ( m2g(n) ) = g ( m2 ) g(g(n)) = ng ( m2 ) = ng2(m) ⇒ g ∈ S. Ta lại có f(n) ≥ g(n) (vì a ≥ 1). Do đó để tìm giá trị nhỏ nhất, ta chỉ cần xét hàm g(n) thỏa mãn (3.10). Giả sử p là số nguyên tố và g(p) = u.v với u, v ∈ N∗. Ta có p = g(g(p)) = g(u.v) = g(u)g(v). Suy ra g(u) = 1 hoặc g(v) = 1. + Giả sử g(u) = 1. Ta được u = g(g(u)) = g(1) = 1. Khi đó g(p) = v. + Giả sử g(v) = 1. Ta được v = g(g(v)) = g(1) = 1. Khi đó g(p) = u. Vậy g(n) là hàm số chuyển số nguyên tố thành số nguyên tố. Ta lại có g(m) = g(n)⇒ g(g(m)) = g(g(n))⇒ m = n. Do đó g là đơn ánh. Vậy g(n) chuyển các số nguyên tố khác nhau thành các số nguyên tố khác nhau. Ta có 1998 = 2.33.37 và g(1998) = g(2.33.37) = g(2).g3(3).g(37) 42 Do đó để g(1998) nhận được giá trị nhỏ nhất ta phải chọn g(n) sao cho g(2), g(3), g(37) là các số nguyên tố khác nhau nhỏ nhất. Hiển nhiên, nếu ta chọn được hàm số g(n) sao cho g(3) = 2, g(2) = 3, g(5) = 37, g(37) = 5 thì g(n) ≥ g(2).g3(3).g(37) = 120. Ta xây dựng hàm g : N∗ → N∗ sao cho g(1) = 1, g(2) = 3, g(3) = 2, g(5) = 37, g(37) = 5, g(p) = p,∀p ∈ P\ {2; 3; 5; 37} và với n = pk11 pk22 . . . pkmm thì g(n) = gk1(p1).gk2(p2) . . . gkm(pm). Khi đó g(n) thỏa mãn (3.10) với a = 1. Vậy g(n) ∈ S. Do đó minf(1998) = 120 với f(n) ∈ S. 3.1.2 Lớp các bài toán áp dụng nguyên lí cực hạn Nguyên lí cực hạn là một trong những nguyên lí quan trọng được áp dụng hiệu quả trong việc giải các phương trình hàm trên tập N và Z. Nguyên lí này được phát biểu như sau: i) Một tập hợp hữu hạn khác rỗng các số tự nhiên bao giờ cũng có phần tử lớn nhất và nhỏ nhất. ii) Một tập khác rỗng bất kì các số tự nhiên bao giờ cũng có phần tử bé nhất. Bài toán 3.7 (IMO 1997). Cho hàm số f : N∗ → N∗ thỏa mãn điều kiện f(n+ 1) > f(f(n)),∀n ∈ N∗. Chứng minh rằng f(n) = n với mọi n ∈ N∗. Lời giải. Do Rf ⊆ N∗;Rf 6= ∅ nên tồn tại phần tử nhỏ nhất của Rf . Từ giả thiết ta có f(2) > f(f(1)) > 0; f(3) > f(f(2)); · · · Vậy phần tử nhỏ nhất của Rf không thể là f(2);f(3), · · · . Nói cách khác, f(1) là phần tử nhỏ nhất duy nhất của Rf . Do f(1) ≥ 1 suy ra f(n) > 1,∀n > 1. Vậy có thể hạn chế xét hàm số f : N∗\{1} → N∗\{1}. Cũng lập luận như trên ta cũng có f(2) là phần tử nhỏ nhất duy nhất của f(N∗\{1}) và f(n) > 2,∀n > 2. Lặp lại quá trình trên ( xét f : N∗\{1, 2} → N∗\{1, 2}, v.v · · · ) ta được f(1) < f(2) < f(3) < · · · suy ra f(n) ≥ n,∀n ∈ N∗. Ngoài ra, ta còn có f(n) là hàm đồng biến. Giả sử ∃n ∈ N∗, f(n) > n suy ra f(n) ≥ n + 1 hay là f(f(n)) ≥ f(n + 1) (Do f(n) là hàm đồng biến). Điều này mâu thuẫn với giả thiết f(f(n)) < f(n + 43 1),∀n ∈ N∗. Suy ra f(n) = n. Thử lại thấy hàm này thỏa mãn yêu cầu đề bài. Vậy f(n) = n,∀n ∈ N∗. Bài toán 3.8. Hãy xây dựng một hàm số f : N∗ → N∗ thỏa mãn điều kiện f(f(n)) = 1993.n1945,∀n ∈ N∗. Lời giải. Gọi A là tập các số có dạng 1993.n1945, n ∈ N∗;A0 là tập các số nguyên dương không có dạng trên. Khi đó A ∪ A0 = N∗;A ∩ A0 = ∅. Các số thuộc A0 được kí hiệu là n(0; k) với n(0; 1) = 1, n(0; k) < n(0; k + 1),∀k ∈ N∗. Chẳng hạn n(0; 2) = 2, n(0; 3) = 3, · · · , n(0; 1992) = 1992, n(0; 1993) = 1994, các số thuộc A được kí hiệu là n(s; k) và được xác định như sau n(s; k) = 1993(n(s− 1; k))1945. Chẳng hạn khi s = 1 thì n(1; k) = 1993(n(0; k))1945 (với n(0; k) ∈ A0). Ta sẽ chứng minh ∀n ∈ N∗, tồn tại duy nhất (s; k), với s ∈ N, k ∈ N∗ sao cho n(s; k) = n. Thật vậy, nếu n ∈ A0, chọn s = 0, dễ thấy tồn tại duy nhất k ∈ N∗ để n(0; k) = n. Nếu n ∈ A suy ra n = 1993.n19451 với n1 < n. Xét n1. Nếu n1 ∈ A thì tồn tại n2 sao cho n1 = 1993.n19452 với n2 < n1; · · · . Quá trình này là hữu hạn vì dãy n1;n2; · · · gồm các số nguyên dương giảm dần. Bởi vậy tồn tại s để ns ∈ A0, hay là tồn tại k, ns = n(0; k) ∈ A0, suy ra ns−1 = n(1; k);ns−2 = n(2; k); · · · ;n1 = n(s− 1; k);n = n(s; k). Vậy sự tồn tại của s; k đã được chứng minh. Giả sử tồn tại s; r ∈ N, (s ≥ r) sao cho n = n(s; k) = n(r;h), (k;h ∈ N∗). Khi đó 1993(n(s− 1); k))1945, suy ra n(s− 1; k) = n(r − 1;h)⇒ n(s− 2; k) = n(r − 2;h)⇒ · · · 44 Làm tương tự tiếp tục ta được n(s− r; k) = n(0;h). Từ đó có s = r vì nếu s− r > 0 thì ta được n(s− r; k) ∈ A còn n(0;h) ∈ A0. Đó là điều vô lí vì A∪A0 = ∅. Vậy ta cũng có k = h vì mỗi số n ∈ A0 được ứng với duy nhất một chỉ số k ∈ N∗ trong cách viết n = n(0; k). Như vậy tính duy nhất của bộ số (s; k) cũng được chứng minh. Bây giờ ta sẽ xây dựng hàm f(n) như sau. Với mỗi n ∈ N∗, tồn tại duy nhất (s; k), s ∈ N, k ∈ N∗ sao cho n(s; k) = n, ta đặt f(n) = f(n(s; k)) =   n(s; k + 1), nếu k lẻn(s+ 1; k − 1), nếu k chẵn . Khi đó nếu k lẻ thì f(f(n)) = f(f(n(s; k))) = f(n(s; k + 1)) (do k lẻ) = n(s+ 1; k) (do k chẵn) = 1993(n(s; k))1945 (do n = n(s; k)). Tương tự, nếu k chẵn thì f(f(n)) = f(f(n(s+ 1; k − 1))) = f(n(s; k + 1)) (do k chẵn) = n(s+ 1; k) (do k-1 lẻ) = 1993(n(s; k))1945 (do n = n(s; k)). Vậy ta được f(f(n)) = 1993n1945,∀n ∈ N∗. Bài toán 3.9. Tìm tất cả các hàm số f : N∗ → N∗ thỏa mãn điều kiện f(1) = 1 và f(f(n))f(n+ 2) + 1 = f(n+ 1)f(f(n+ 1)),∀n ∈ N∗. Lời giải. Giả sử tồn tại hàm số f thỏa mãn yêu cầu bài toán. Ta chứng minh bằng quy nạp rằng với mọi n ∈ N∗ thì f(n+ 1) > f(f(n)). - Với n = 1. Hiển nhiên khẳng định đúng. - Giả sử khẳng định đúng với n = k(k ≥ 1). Ta chứng minh khẳng định trên đúng với n = k + 1. Thật vậy, ta có f(f(k))f(k + 2) = f(k + 1)f(f(k + 1))− 1. Do đó f(k + 2) = f(k + 1)f(f(k + 1))− 1 f(f(k)) ≥ [f(f(k)) + 1][f(f(k + 1))]− 1 f(f(k)) > [f(f(k))]f(f(k + 1)) f(f(k)) = f(f(k + 1)). 45 Từ đó ta suy ra f(n+ 1) > f(f(n)),∀n ∈ N∗. Vậy theo bài toán 3.7 ta có f(n) = n,∀n ∈ N∗. Thử lại ta thấy hàm số này thỏa mãn yêu cầu bài toán. Kết luận. Vậy f(n) = n,∀n ∈ N∗. Bài toán 3.10. Tìm tất cả các hàm số f : N∗ → N∗ thỏa mãn điều kiện f(1) = 1 và 2f((m2 + n2))3 = f 2(m)f(n) + f(m)f 2(n),∀m,n ∈ N∗. Lời giải. Giả sử tồn tại hàm số f thỏa mãn các yêu cầu đề bài. Nếu f(n) ≡ c, với c là hằng số thì hiển nhiên thỏa mãn điều kiện bài toán. Nếu tồn tại m,n ∈ N∗ sao cho f(m) 6= f(n) thì ta gọi a, b là hai số thỏa mãn |f(a)− f(b)| = min|f(m)− f(n)|,∀m,n ∈ N∗. Giả sử f(a) > f(b). Ta có 2f 3(b) < f 2(a)f(b) + f(a)f 2(b) < 2f 3(a). Suy ra f(b) < f(a2 + b2) < f(a)⇒ f(a2 + b2)− f(b) < f(a)− f(b). Từ đó |f(a)− f(b)| = f(a)− f(b) > f(a2 + b2)− f(b) = |f(a2 + b2)− f(b)|. Đến đây ta gặp mâu thuẫn với cách gọi trên. Vậy f(n) ≡ c (với c là hằng số) là hàm số cần tìm. Bài toán 3.11 (Canada Nationnal Olympiad 2002). Tìm tất cả các hàm số f : N∗ → N∗ thỏa mãn điều kiện xf(y) + yf(x) = (x+ y)f(x2 + y2),∀x, y ∈ N∗. 46 Lời giải. Giả sử f không phải là hàm hằng. Khi đó ∅ 6= A = {f(y)− f(x)|x, y ∈ N∗, f(y)− f(x) > 0} ⊂ N∗. Do tập A có phần tử nhỏ nhất nên có thể chọn x, y ∈ N∗ sao cho f(y) > f(x) và f(y)− f(x) là nhỏ nhất. Ta có f(x) = xf(x) + yf(x) x+ y < xf(y) + yf(x) x+ y < xf(y) + yf(y) x+ y = f(y). Kết hợp với đề bài ta suy ra f(x) < f(x2+ y2) < f(y), điều này mâu thuẫn với cách chọn x và y. Vậy f(x) ≡ c,∀x ∈ N∗, với c là hằng số nguyên dương. Thử lại thấy hàm này thỏa mãn bài ra. 3.1.3 Lớp các bài toán áp dụng hệ đếm cơ số Hệ đếm cơ số có thể dùng để xây dựng nhiều phương trình hàm có tính chất rất thú vị. Nhìn trên phương diện của một cơ số khác, có thể rất khó nhận ra quy luật, nhưng nếu chọn đúng cơ số thì bài toán trở nên vô cùng đơn giản. Xin nhắc lại là với b là một số nguyên dương lớn hơn 2 thì mọi số nguyên dươngN đều có thể biểu diễn một cách duy nhất dưới dạng N = (a1a2...ak)b = a1b k−1 + a2b k−2 + · · ·+ akb0, với 1 ≤ a1 ≤ b− 1, 0 ≤ a2, · · · , ak ≤ b− 1. Đó là định nghĩa hệ đếm cơ số b của số N dạng cơ bản nhất. Hệ đếm thường sử dụng nhất là hệ đếm cơ số 2 và cơ số 3. Sau đây ta xét một vài bài toán thể hiện tư tưởng trên. Bài toán 3.12 (IMO 1988). Xét hàm số f : N→ N thỏa mãn điều kiện f(1) = 1, f(3) = 3 và với mọi số nguyên dương n thì f(2n) = f(n); f(4n+ 1) = 2f(2n+ 1)− f(n); f(4n+ 3) = 3f(2n+ 1)− 2f(n). 47 Tìm số các giá trị của n ≤ 1988 mà f(n) = n. Lời giải. Giả sử tồn tại hàm số f thỏa mãn yêu cầu bài toán. Một số k ∈ N bất kì chỉ có thể có một trong bốn dạng k = 4n = 2.2n; k = 4n+ 1; k = 4n+ 2; k = 4n+ 3. Do đó từ giả thiết có thể thấy rằng hàm số đã cho được xác định một cách duy nhất. Ta sẽ sử dụng cơ số 2 để tìm biểu diễn của hàm số f . Ta có f (12) = f(1) = 1 = 12; f (102) = f(2) = f(1) = 1 = 012; f (112) = f(3) = 3 = 112; f(1002) = f(4) = 1 = 0012; f (1012) = f(5) = 5 = 1012; f (1102) = f(6) = 0112 · · · Quy luật. Biểu diễn của f(n) trong cơ số 2 chính là biểu diễn của n bằng cách viết ngược lại, tức là f ((akak−1 · · · a1a0)2) = (a0a1 · · · ak−1ak)2 . Chứng minh. Giả sử tính chất đúng cho k < n. Ta sẽ chứng minh nó đúng cho n. + Nếu n chẵn (n = 2m) thì theo giả thiết f(n) = f(2m) = f(m). Vì n = 2m nên m được biểu diễn trong hệ cơ số 2 dưới dạng m = (akak−1 · · · a1a0)2 thì n = (akak−1 · · · a1a00)2 . Theo giả thiết quy nạp ta có f(m) = f ((akak−1 · · · a1a0)2) = (a0a1 · · · ak−1ak)2 = f(n) = = f ((akak−1 · · · a1a00)2) = (0a0a1 · · · ak−1ak)2 . + Nếu n = 4m+1 vớim = (akak−1 · · · a1a0)2 thì 4m+1 = (akak−1 · · · a1a001)2 và 2m+ 1 = (akak−1 · · · a1a01)2 . Theo đầu bài và giả thiết quy nạp ta có f(akak−1 . . . a1a001)2 = f(4m+ 1) = 2f(2m+ 1)− f(m) = 2.(1a0a1 . . . ak−1ak)2 − f(m) = (1a0a1 . . . ak−1ak)2 − f(m) = (10 . . . 0)2︸ ︷︷ ︸ k+3 +(a0a1 . . . ak−1ak0)2 − (a0a1 . . . ak−1ak)2 = (10 . . . 0)2︸ ︷︷ ︸ k+3 +(a0a1 . . . ak−1ak0)2 = (10a0a1 . . . ak−1ak)2. 48 + Nếu n = 4m+3 vớim = (akak−1 · · · a1a0)2 thì 4m+1 = (akak−1 · · · a1a011)2 và 2m+ 1 = (akak−1 · · · a1a01)2 . Theo đầu bài và giả thiết quy nạp ta có f(akak−1 . . . a1a011)2 = f(4m+ 3) = 3f(2m+ 1)− 2f(m) = f(2m+ 1) + 2f(2m+ 1)− 2f(m) = (1a0a1 . . . ak−1ak)2 + (1a0a1 . . . ak−1ak0)2 − (a0a1 . . . ak−1ak0)2 = (1a0a1 . . . ak−1ak)2 + (10 . . . 0)2︸ ︷︷ ︸ k+3 = (11a0a1 . . . ak−1ak)2. Vậy quy luật được chứng minh. Một số trong cơ số 2 được gọi là palindromic nếu nó không đổi khi ta đổi chỗ các chữ số theo thứ tự ngược lại. Với mỗi k, có tất cả 2  k − 1 2   số palindromic có độ dài k (số palindromic bậc k). Thật vậy, một số palindromic hoàn toàn được xác định nếu biết tất cả [ k + 1 2 ] chữ số đầu tiên bên phải, các chữ số còn lại được xác định bằng cách lấy đối xứng qua số đứng giữa. Vì chữ số đầu tiên bên phải bắt buộc phải là 1, nên chỉ còn lại [ k + 1 2 ] − 1 = [ k − 1 2 ] vị trí này tùy chọn là chữ số 0 hoặc chữ số 1. Có 2× 2× · · · × 2︸ ︷︷ ︸ k − 1 2   = 2  k − 1 2   khả năng chọn, nghĩa là có tất cả 2  k − 1 2   số palindromic bậc k. Từ quy luật trên ta suy ra nghiệm phương trình f(n) = n với n ≤ 1988 = 111110011102 Chính là các số palindromic tối đa 10 chữ số và những số có 11 chữ số nhưng nhỏ hơn n ≤ 1988. Vì có một số với 1 chữ số (số 1 = 12) và một số với 2 chữ số trong cơ số 2 (số 3 = 112) thỏa mãn phương trình f(n) = n nên tất cả có 1+1+2 [ 3− 1 2 ] +2 [ 4− 1 2 ] +· · ·+2 [ 9− 1 2 ] +2 [ 10− 1 2 ] = 2(1+2+· · ·+16) = 62. Số có tối đa 10 chữ số trong cơ số 2, tức là có tất cả 62 chữ số trong khoảng 0 ≤ n ≤ 1023 thỏa mãn phương trình f(n) = n. Có tất cả 2 [ 11− 1 2 ] = 32 số trong 49 khoảng 1024 ≤ n ≤ 2047 (có 11 chữ số) là palindromic. Trong số đó có hai số 111111111112 = 2047 và 111110111112 = 2015 vượt quá 1988. Vậy có tất cả 32 − 2 = 30 số trong khoảng 1024 ≤ n ≤ 1988 thỏa mãn phương trình f(n) = n. Cuối cùng, phương trình f(n) = n có tất cả 62 + 30 = 92 nghiệm thỏa mãn. Bài toán 3.13 (IMO shortlist 2000). Xét hàm số F