Luận văn Hệ đếm và ứng dụng trong toán phổ thông

8 là số chia hết cho 3, 9 vì 3 và 9 là ước của (8+1). Thí dụ 1.3.4 1. Số (23456780113)9 có tổng đan đấu các chữ số là S’=3-1+1-0+8-7+6-5+4- 3+2=8 là số chia hết cho 2 nhưng không chia hết cho 5, 10 nên số (23456780113)9 chia hết cho 2 nhưng không chia hết cho 5, 10. Kiểm tra qua phần mềm Maple có kết quả hoàn toàn đúng. > convert(23456780113,decimal,9); > ifactor(8335586568); 2. Số (356776130112)8 có tổng đan dấu các chữ số là S’=2-1+1-0+3-1+6-7+7- 6+5-3=6 là số chia hết cho 3 nhưng không chia hết cho 9 nên số (356776130112)8 chia hết cho 3 nhưng không chia hết cho 9. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 64 Kiểm tra qua phần mềm Maple có kết quả hoàn toàn đúng: >convert(356776130112,decimal,octal); >ifactor(32077557834); 3. Xét xem số (120124123432100123341)5 có chia hết cho 2, 7, 9 hay không? Ta có 2´7´9=126 =125+1. Nên ta chuyển số đã cho thành số viết trong hệ đếm cơ số 125, bằng cách tách số đó ra thành từng nhóm có 3 chữ số từ phải qua trái (nhóm cuối cùng có thể không đủ 3 chữ số) và mỗi nhóm chuyển thành số viết trong hệ đếm cơ số 125. Khi đó ta lấy tổng đan dấu các chữ số của số đó viết trong hệ đếm cơ số 125 kể từ phải qua trái. Nếu tổng đó chia hết cho 2, 7, 9 thì số đó chia hết cho 2, 7, 9. Ta có: 341 = 3 ´52 + 4 ´5 +1 = 96; 123 = 1 ´52 + 2 ´5 + 3 = 38; 100 = 1 ´52 + 0 ´5 + 0 = 25; 432 = 4 ´52 + 3 ´5 + 2 = 117; 123 = 1 ´52 + 2 ´5 + 3 = 38; 124 = 1 ´52 + 2 ´5 + 4 = 39; 120 = 1 ´52 + 2 ´5 + 0 = 35. Tổng đan dấu các chữ số của nó là S = 96 -38 + 25 – 117 + 38 -39 + 35 = 0 là số chia hết cho 2, 7, 9 nên số đã cho chia hết cho 2, 7, 9. Thực ra thì ta có thể lấy tổng đan dấu của các nhóm có 3 chữ số từ phải qua trái của số đã cho, nếu tổng ấy chia hết cho 2, 7, 9 thì số đó chia hết cho 2, 7, 9 chứ không cần thiết phải đổi từng nhóm sang hệ đếm cơ số 125 như trên. Kiểm tra qua phần mềm Maple có kết quả hoàn toàn đúng: > convert(120124123432100123341,decimal,5); > ifactor(134714096098596); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 65 Nhận xét 1.3.3 Sử dụng phần mềm Maple có ưu điểm rất lớn là tìm được các ước của một số a ở trong hệ đếm cơ số tùy ý một cách dễ dàng bằng cách chuyển đổi số đó qua hệ đếm cơ số 10, rồi phân tích nó ra thừa số nguyên tố hoặc chia trực tiếp tìm kết quả rồi kết luận. Cũng có thể kiểm tra tính chia hết dựa vào việc chia tìm dư. Tuy nhiên máy tính mặc dù đã được sử dụng nhiều hiện nay song không phải bất kỳ lúc nào cũng có sẵn sàng ở mọi nơi mọi lúc. Cho nên việc tìm hiểu về các dấu hiệu chia hết ở các hệ đếm với cơ số khác nhau vẫn luôn là một vấn đề cần thiết cho việc sử dụng cũng như phát triển tư duy toán học. §2. Sử dụng hệ đếm trong giải toán Trong phần này chúng ta đề cập tới một số bài toán được phát biểu bằng ngôn ngữ hệ đếm hoặc sử dụng các kiến thức về hệ đếm để giải. Các bài toán này thường hay gặp trong các kỳ thi quốc gia và quốc tế. Hệ đếm được sử dụng trong việc giải các bài toán này chủ yếu là hệ nhị phân (hệ đếm cơ số 2) và hệ tam phân (hệ đếm cơ số 3), tuy nhiên cũng có thể có những bài sử dụng cơ số khác hoặc những bài phát biểu cho hệ đếm cơ số bất kì. Những bài này thường khó và đa dạng, nói chung không có phương pháp tổng quát để giải. Các bài dạng này thường phải sử dụng phương pháp quy nạp toán học và một số tính chất của số viết trong hệ đếm cơ số 2 và hệ đếm cơ số 3. Thí dụ: 1) Nếu ( )1 1 0 2...n na a a a a-= thì: ( )1 1 0 22 ... 0n na a a a a-= , ( )1 1 0 24 ... 00n na a a a a-= , ( )1 1 0 22 1 ... 1n na a a a a-+ = và ( )1 1 0 2... .2 n n a a a a a-= , ( )1 2 1 0 2... .4 n n a a a a a a-= . Tương tự trong hệ đếm cơ số 3 ta có 2) Nếu ( )1 1 0 3...n na a a a a-= thì: ( )1 1 0 33 ... 0n na a a a a-= , ( )1 1 0 39 ... 00n na a a a a-= , ( )1 1 0 33 1 ... 1n na a a a a-+ = , ( )1 1 0 33 2 ... 2n na a a a a-+ = và ( )1 1 0 3... .3 n n a a a a a-= , ( )1 2 1 0 3... .9 n n a a a a a a-= . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 66 2.1 Các bài toán được phát biểu trên ngôn ngữ hệ đếm Bài toán 1 (Vô địch Canada, 1972) Chứng minh rằng 1) ( )10201 b là hợp số với mọi 2b > . 2) ( )10101 k là hợp số với mọi k . Giải 1) Vì ( ) 4 210201 2 1b b b= + + = ( ) 22 1b + nên ( )10201 b là hợp số với mọi 2b > . 2) Ta có: ( )10101 k = ( )4 2 4 2 21 2 1k k k k k+ + = + + - = ( ) 22 21k k+ - = ( )( )2 21 1k k k k+ + - + . Với mọi k >1 thì 2 1 1k k- + > nên ( )10101 k là hợp số với mọi k vì ( )10101 k là tích của hai nhân tử khác 1. Bài toán 2 (Vô địch Canada, 1987) Tìm tất cả các cách viết số 1987 trong hệ đếm cơ số k có ba chữ số để cho tổng 1 2 3 25a a a+ + = . Giải Số đó có dạng ( ) 21 2 3 1 2 3kA a a a a k a k a= = + + , 1 2 30 , , 1a a a k£ £ - , 10 a< . Do đó ( ) ( )2 2 3 31 1 1 1k A k k k k k k k£ £ - + - + - = - < . Vì 452 = 2025 >1987 nên với 45k ³ thì ( ) 21 2 3 45 1987kA a a a= ³ > Þ 44k £ . Mặt khác, 123 = 1728 <1987 nên với 12k £ nên ( ) 31 2 3 12 1987kA a a a= < < . Suy ra 13k ³ . Do vậy 13 44k£ £ . Vì 1 2 3 25a a a+ + = nên ta có: ( ) 21 2 3 1 2 1 225kA a a a a k a k a a= = + + - - Û ( ) ( )21 21987 1 1 25a k a k= - + - + Û ( ) ( )1 21962 1 1k a k a= - + +é ùë û Û ( ) ( )1 218.109 1 1k a k a= - + +é ùë û . Ta xét các trường hợp có thể xảy ra sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 67 · 1k - là ước của 109 Þk=2 hoặc k = 110 (đều không thỏa mãn). · 1k - là ước của 18: Nếu 1k - =1, 2, 3, 6, 9 thì k =2, 3, 4, 7, 10 (đều không thỏa mãn). Do vậy 1 18k - = Þ 19k = (thỏa mãn) Þ 1 2 35; 9; 11a a a= = = . Vậy có duy nhất một cách biểu diễn thỏa mãn yêu cầu là: ( ) 19 1987 5911= . Bài toán 3 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1965) Kí hiệu 25b là số có hai chữ số trong hệ đếm cơ số b . Nếu 52b gấp đôi 25b thì b bằng (chọn một trong năm đáp số): a) 7b = ; b) 8b = ; c) 9b = ; d) 11b = ; e) 12b = . Giải Vì 52 5 2b b= + và 25 2 5b b= + nên theo bài ra ta có: ( )5 2 2 2 5b b+ = + . Suy ra 8b = . Đáp án b) là đúng. Bài toán 4 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1967) Các số 12, 15, 16 được viết trong cơ số b có tích là 3146 trong cơ số b . Vậy trong cơ số b , tổng của chúng bằng (chọn một trong năm đáp số): a) 43; b) 44; c) 45; d) 46; e) 47. Giải Vì 12 2b b= + ; 15 5b b= + ; 16 6b b= + nên ( )( )( ) 3 212 15 16 2 5 6 13 52 60b b b b b b b b b´ ´ = + + + = + + + . Mặt khác, 3 23146 3 4 6b b b b= + + + . Theo bài ra ta có: 12 15 16 3146b b b b´ ´ = Û 3 2 3 213 52 60 3 4 6b b b b b b+ + + = + + + Û 3 26 24 27 0b b b- - - = Û 9b = . Vậy ( ) ( ) ( )9 9 9 9 12 15 16 12 15 16 9 2 9 5 9 6 3.9 13 3.9 9 4 4.9 4 44 . b b b+ + = + + = + + + + + = + = + + = + = Đáp án b) là đúng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 68 Bài toán 5 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1968) Số N có ba chữ số khi viết trong cơ số 7. Khi viết N trong cơ số 9, các chữ số đảo ngược lại. Thế thì số chính giữa là (chọn một trong năm đáp số): a) 0; b) 1; c) 3; d) 4; e) 5. Giải Giả sử ( ) 27 7 .7 .7N abc a b c= = + + , 0 , , 6a b c£ £ , 0a > . Khi ấy ( ) 29 9 .9 .9N cba c b a= = + + . Suy ra 49 7 81 9a b c c b a+ + = + + Û 24 40b a c= - Û ( )8 3 5b a c= - . Do 0 , , 6a b c£ £ , 0a > nên số nguyên 3 5 0n a c= - = . Chứng tỏ 0b = và 5a = , 3c = . Vậy số cần tìm là ( ) ( )7 9503 305= . Chọn a Bài toán 6 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1969) Nếu trong cơ số 2 số N là 11000. Thế thì số nguyên liền trước viết trong cơ số 2 là (chọn một trong năm đáp số): a) 10001; b) 10010; c) 10011; d) 10110; e) 10111. Giải Cách 1: Số liền trước số 211000 trong cơ số 2 sẽ là (làm phép trừ trong cơ số 2): 2 211000 1 10111- = . Chọn e Cách 2: Đổi qua cơ số 10: 4 3211000 2 2 24= + = . Số liền trước số 24 là 4 2 223 2 2 2 1 10111= + + + = . Bài toán 7 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1970) Số 10! (10 được viết trong cơ số 10), khi viết trong cơ số 12 có đúng k chữ số cuối cùng đều bằng 0. Giá trị của k là (chọn một trong năm đáp số): a) 1; b) 2; c) 3; d) 4; e) 5. Giải Trong cơ số 10 ta có: 8 4 2 4 210! 1.2.3.4.5.6.7.8.9.10 2 .3 .5 .7 12 .5 .7= = = . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 69 Vì ( )2 2 125 .7 25.7 175 12 2.12 7 127= = = + + = nên 4 2 12 12 1210! 12 .5 .7 10000 .127 1270000= = = . Chứng tỏ 10! có 4 chữ số 0 trong cơ số 12. Đáp án d) đúng. Bài toán 8 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1971) Một số khi viết trong cơ số a là 47, khi viết trong cơ số b là 74. Giả sử cả hai cơ số là số nguyên dương. Giá trị nhỏ nhẩt của a b+ được viết trong hệ thống số La Mã là (chọn một trong năm đáp số): a) XIII; b) XV; c) XXI; d) XXIV; e) XVI. Giải Ta có 47 4 7a a= + với 7a > ; 74 7 4b b= + với 7b > . Suy ra 47 74a b= Û 4 7 7 4a b+ = + Û 7 4 3b a- = . Đây là một phương trình vô định với a và b là những số nguyên dương. Tập tất cả các nghiệm nguyên dương của phương trình này là 1 7 ; 1 4a t b t= + = + với t là số không âm bất kì. Dễ thấy rằng với 2t = ta được nghiệm nhỏ nhất với 15 7; 9 7a b= > = > . Vậy giá trị nhỏ nhất của a b+ là 24=XXIV. Đáp án d) đúng. Bài toán 9 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1973) Số 544 trong hệ đếm cơ số b là bình phương của số 24 viết trong hệ cơ số b . Số đó viết trong hệ cơ số 10 sẽ là (chọn một trong năm đáp số): a) 6; b) 8; c) 12; d) 14; e) 16. Giải Ta có 5b > . Vì 24 2 4b b= + nên ( ) ( ) 2 2 224 2 4 4 16 16b b b b= + = + + . Mặt khác, 2554 5 5 4b b b= + + . Suy ra ( )224 554b b= Û 2 24 16 16 5 5 4b b b b+ + = + + Û 2 11 12 0b b- - = Û 12b = . Vậy đáp án c) là đúng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 70 Bài toán 10 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1978) Biết số nguyên 8n > là nghiệm của phương trình 2 0x ax b- + = và biểu diễn của a trong cơ số n là 18. Thế thì biểu diễn của b trong cơ số n là (chọn một trong năm đáp số): a) 18; b) 28; c) 80; d) 81; e) 280. Giải Vì 8n > là nghiệm của phương trình 2 0x ax b- + = nên ta có 2 0n an b- + = . Mặt khác, ( )18 8na n= = + . Suy ra ( ) ( ) 2 28 8 80 nb an n n n n n= - = + - = = . Vậy c) là đáp án đúng. Bài toán 11 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1981) Biểu diễn trong hệ đếm cơ số 3 của x là 12112211122211112222. Chữ số đầu tiên (tức là chữ số bên trái) của x khi viết trong hệ cơ số 9 là (chọn một trong năm đáp số): a) 1; b) 2; c) 3; d) 4; e) 5. Giải Cách 1: Ta có ( )312112211122211112222 = ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) 19 18 17 16 15 14 1 9 82 2 9 8 7 1.3 2.3 1.3 1.3 2.3 2.3 ... 2.3 2 1.3 2 . 3 1.3 1 3 ... 2.3 2 5.9 4.9 8.9 ... 8. + + + + + + + + = + + + + + + = + + + + Vậy chữ số đầu tiên trong biểu diễn cơ số 9 là 5. Đáp án e) là đúng. Cách 2: Chia thành từng cụm 2 chữ số từ phải qua trái rồi chuyển nhóm cuối sang hệ đếm cơ số 9. 2.2. Các bài toán được giải nhờ phương pháp hệ đếm Nhiều bài toán phát biểu rất đa dạng và phong phú (phương trình hàm, ngôn ngữ tập hợp,...), tuyệt nhiên không có một giả thiết nào về hệ đếm, nhưng nhờ phát Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 71 biểu lại dưới ngôn ngữ hệ đếm, ta có lời giải đẹp cho chúng. Có những bài lời giải có lẽ là duy nhất. Các bài toán dưới đây là những ví dụ minh họa. Bài toán 12 (Vô địch Trung quốc, 2005) Cho { }0,1,2,3,4,5,6T = và M = 1 2 3 42 3 4 ; , 1,47 7 7 7 i a a a a a T iì ü+ + + Î =í ý î þ . Sắp xếp các số của M theo thứ tự giảm dần thì số thứ 2005 của M sẽ là số nào trong các số sau: a) 2 3 4 5 5 6 3 7 7 7 7 + + + ; b) 2 3 4 5 5 6 2 7 7 7 7 + + + ; c) 2 3 4 1 1 0 4 7 7 7 7 + + + ; d) 2 3 4 1 1 0 3 7 7 7 7 + + + . Giải (sử dụng hệ đếm cơ số 7) Kí hiệu ( )1 2... k pa a a là số viết trong hệ đếm cơ số p với k chữ số. Lấy số bất kì trong tập M nhân với 74 ta được một số mới dạng 3 2 1 2 3 4.7 .7 .7a a a a+ + + . Kí hiệu tập các số mới là *M thì *M = { }3 21 2 3 4.7 .7 .7 ; , 1,4ia a a a a T i+ + + Î = = ( ){ }1 2 3 4 7a a a a . Như vậy, khi ia nhận giá trị trong tập { }0,1,2,3,4,5,6T = thì *M chính là tập tất cả các số có không quá 4 chữ số trong hệ đếm cơ số 7. Số lớn nhất trong tập *M là số ( )76666 =2400. Sắp xếp các số của tập *M theo thứ tự giảm dần thì số 2400 là số đứng thứ nhất. Số đứng thứ 2005 của tập *M là 2400 – 2004 = 396 = ( )71104 . Đem các số của tập *M chia cho 74 thì ta được các số của tập M , và tập M cũng được sắp thứ tự giảm dần giống như tập *M . Chính vì vậy số đứng thứ 2005 của tâp M được sinh ra do số thứ 2005 của tập *M chia cho 74. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 72 Vậy số cần tìm là ( ) 4 2 3 47 1 1 0 41104 : 7 7 7 7 7 = + + + . Đáp án c) là đáp án đúng. Bài toán 13 (Bài toán Josephus) Trong cuộc chiến tranh Do Thái-La Mã, Josephus ra nhập đội quân Do Thái. Trong một trận chiến đấu ác liệt, 41 người lính, trong đó có Josephus đã bị quân La Mã vây chặt trong một hang động. Với tinh thần thà tự sát còn hơn là bị bắt, họ quyết định đứng thành vòng tròn, rồi theo chiều kim đồng hồ, bắt đầu từ người thứ hai, cứ cách một người lại có một người tự sát, hết vòng này đến vòng khác, cho đến người cuối cùng thì dừng. Người này phải sống và tìm cách thoát ra khỏi hang động để kể lại cho mọi người tinh thần hy sinh anh dũng của những người lính. Hỏi người đó phải đứng ở vị trí nào trên vòng tròn trong số 41 người. Giải Xét bài toán Josephus tổng quát với n người. Kí hiệu ( )J n là vị trí người sống sót. Ta có (1) 1J = . Trường hợp 1 2n k= . Sau một vòng còn lại k người mang số cũ là 1,3,5,...,2 1k - và được đánh số mới là 1,2,...,k . Tiếp tục như thế, ta có (2 ) 2 ( ) 1J k J k= - . (1a) Trường hợp 2 2 1n k= + . Sau một vòng còn lại k người mang số cũ là 1,3,5,...,2k và được đánh số mới là 1,2,...,k . Tiếp tục như thế, ta có (2 1) 2 ( ) 1J k J k+ = + . (1b) Xét 12 2m mn +£ < , tức là 2mn r= + với 0 2mr£ < . Ta sẽ chứng minh bằng qui nạp rằng ( ) (2 ) 2 1mJ n J r r= + = + . (2) Với 1m = thì 0( ) (2 0) 2.0 1 1J n J= + = + = . Công thức (2) đúng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 73 Nếu n chẵn ( 2n k= ) thì 1 12 2 2 2 2 m m mn rk- -£ = = + < ; r cũng là một số chẵn và 2 r là một số nguyên. Theo công thức (1a) và giả thiết qui nạp ta có 1( ) (2 ) (2 ) 2 ( ) 1 2 (2 ) 1 2(2. 1) 1 2 1 2 2 m m r rJ n J r J k J k J r-= + = = - = + - = + - = + . Nếu n lẻ ( 2 1n k= + ) thì 1 11 12 2 2 2 2 m m mn rk- -- -£ = = + < ; r cũng là một số lẻ và 1 2 r - là một số nguyên. Theo công thức (1b) và giả thiết qui nạp ta có 1 1 1( ) (2 1) 2 ( ) 1 2 (2 ) 1 2(2. 1) 1 2 1 2 2 m r rJ n J k J k J r- - -= + = + = + + = + + = + . Vậy công thức (2) được chứng minh. Giả sử n được viết trong hệ đếm cơ số 2 là ( ) ( )1 0 1 02 21 ... 2 ... 2 m m m mn a a a a r- -= = + = + . Khi ấy theo công thức (2) ta có ( ) ( ) ( )1 0 1 0 1 02 2 2( ) 2 1 2 ... 1 ... 0 1 ... 1m m mJ n r a a a a a a- - -= + = + = + = hay ( ) ( )1 0 1 02 21 ... ... 1m mJ a a a a- -= . Vì ( )5 3 241 2 2 1 101001= + + = nên ( ) 4 2(41) 10011 2 2 1 19J = = + + = . Người sống sót là người đứng thứ 19 trên vòng tròn tính theo chiêu kim đồng hồ. Bài toán 14 Cho *N là tập các số nguyên dương, * *:f N N® là hàm tăng chặt thỏa mãn ( ( )) 3f f n n= . (1) Tính ( )2009f . Giải (sử dụng hệ tam phân) Nếu ( )1 1f = thì ( )( ) ( )1 1 1f f f= = . Vô lý vì theo giả thiết ta có ( (1)) 3f f = . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 74 Vậy ( )1 1f > . Vì * *:f N N® là hàm tăng chặt nên ( )( ) ( )1 1f f f> Þ ( )3 3.1 ( (1)) 1 1f f f= = > > Þ ( )1 2f = . Từ đó ta có ( ) ( )( ) ( ) ( )( ) ( ) ( )( )2 1 3; 3 2 6; 6 3 9f f f f f f f f f= = = = = = ; Þ ( ) ( )4 7; 5 8f f= = (vì f là hàm tăng chặt). Þ ( )(7) ( 4 ) 12f f f= = ; ( ) ( )( )8 5 15f f f= = ; ( ) ( )( )9 6 18f f f= = ; Þ ( ) ( )( )12 7 21f f f= = Þ ( ) ( )10 19; 11 20f f= = (vì f là hàm tăng chặt). Từ đây, do ( )1 2f = được xác định duy nhất nên tồn tại duy nhất hàm tăng chặt * *:f N N® thỏa mãn (1). Đến đây ta vẫn chưa thấy qui luật. Số 3 trong đầu bài gợi ý việc ta sử dụng hệ đếm cơ số 3. Vậy ta viết đối số và các giá trị của hàm số theo hệ đếm cơ số 3 để thử tìm quy luật. Ta có: f(1) =2 Û f(13) = 23; f(2) =3 Û f(23) = 103; f(3) =6 Û f(103) = 203; f(4) =7 Û f(113) = 213; f(5) = 8 Û f(123) = 223; f(6) =9 Û f(203) =1003; f(7) =12 Û f(213) = 1103; f(8) =15 Û f(223) = 1203; f(9)=18 Û f(1003) =2003; f(10)=19 Û f(1013)=2013; f(11)=20 Û f(1023)=2023; f(12)=21 Û f(1103)= 2103; Từ đây ta thấy quy luật: ( )1 1 0 3 1 1 0 3(1 ... ) (2 ... )n n n nf x x x x x x x x- -= và ( )1 1 0 3 1 1 0 3(2 ... ) (1 ... 0)n n n nf x x x x x x x x- -= . (2) Ta sẽ chứng minh qui luật (2) thỏa mãn (1). Trường hợp 1 3n m= . Nếu 1 1 0 3(1 ... )k km x x x x-= thì 3 1 1 0 3 1 1 0 310 (1 ... ) (1 ... 0)k k k kn x x x x x x x x- -= ´ = . Theo (2) thì ( )1 1 0 3 1 1 0 3( ) (3 ) (1 ... 0) (2 ... 0)k k k kf n f m f x x x x x x x x- -= = = ; ( )1 1 0 3 1 1 0 3 1 1 0 3( ( )) (2 ... 0) (1 ... 00) 3(1 ... 0) 3k k k k k kf f n f x x x x x x x x x x x x n- - -= = = = . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 75 Nếu 1 1 0 3(2 ... )k km x x x x-= thì 3 1 1 0 3 1 1 0 310 (2 ... ) (2 ... 0)k k k kn x x x x x x x x- -= ´ = . Theo (2) thì ( )1 1 0 3 1 1 0 3( ) (3 ) (2 ... 0) (1 ... 00)k k k kf n f m f x x x x x x x x- -= = = ; ( )1 1 0 3 1 1 0 3 1 1 0 3( ( )) (1 ... 00) (2 ... 00) 3(2 ... 0) 3k k k k k kf f n f x x x x x x x x x x x x n- - -= = = = . Trường hợp 2 3 1n m= + . Nếu 1 1 0 3(1 ... )k km x x x x-= thì 3 1 1 0 3 1 1 0 310 (1 ... ) 1 (1 ... 1)k k k kn x x x x x x x x- -= ´ + = . Theo (2) thì ( )1 1 0 3 1 1 0 3( ) (3 1) (1 ... 1) (2 ... 1)k k k kf n f m f x x x x x x x x- -= + = = ; ( )1 1 0 3 1 1 0 3 1 1 0 3( ( )) (2 ... 1) (1 ... 10) 3(1 ... 1) 3k k k k k kf f n f x x x x x x x x x x x x n- - -= = = = . Nếu 1 1 0 3(2 ... )k km x x x x-= thì 3 1 1 0 3 1 1 0 310 (2 ... ) 1 (2 ... 1)k k k kn x x x x x x x x- -= ´ + = . Theo (2) thì ( )1 1 0 3 1 1 0 3( ) (3 1) (2 ... 1) (1 ... 10)k k k kf n f m f x x x x x x x x- -= + = = ; ( )1 1 0 3 1 1 0 3 1 1 0 3( ( )) (1 ... 10) (2 ... 10) 3(2 ... 1) 3k k k k k kf f n f x x x x x x x x x x x x n- - -= = = = . Trường hợp 3 3 2n m= + . Nếu 1 1 0 3(1 ... )k km x x x x-= thì 3 1 1 0 3 1 1 0 310 (1 ... ) 2 (1 ... 2)k k k kn x x x x x x x x- -= ´ + = . Theo (2) thì ( )1 1 0 3 1 1 0 3( ) (3 2) (1 ... 2) (2 ... 2)k k k kf n f m f x x x x x x x x- -= + = = ; ( )1 1 0 3 1 1 0 3 1 1 0 3( ( )) (2 ... 2) (1 ... 20) 3(1 ... 2) 3k k k k k kf f n f x x x x x x x x x x x x n- - -= = = = . Nếu 1 1 0 3(2 ... )k km x x x x-= thì 3 1 1 0 3 1 1 0 310 (2 ... ) 2 (2 ... 2)k k k kn x x x x x x x x- -= ´ + = . Theo (2) thì ( )1 1 0 3 1 1 0 3( ) (3 2) (2 ... 2) (1 ... 20)k k k kf n f m f x x x x x x x x- -= + = = ; ( )1 1 0 3 1 1 0 3 1 1 0 3( ( )) (1 ... 20) (2 ... 20) 3(2 ... 2) 3k k k k k kf f n f x x x x x x x x x x x x n- - -= = = = . Vậy (2) thỏa mãn (1). Do tính duy nhất nên (1) và (2) tương đương. Quay lại bài toán ta có: 2009 = 22021023 Þ ( )2009f = ( )( )32202102f = 120210203 = 3840. Bài toán 15a Chứng minh rằng giữa các số 0, 1, 2,…, 3 1k - có thể tìm thấy 2k các số khác nhau sao cho không có số nào trong các số ấy là trung bình cộng của hai số khác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 76 Giải Vì 3 3 3 1 100....00 1 22....22k k k æ ö æ ö - = - =ç ÷ ç ÷ è ø è ø 14243 14243 nên mọi số { }k0, 1, 2,...,3 1mÎ - đều có thể biểu diễn được dưới dạng một số trong hệ đếm cơ số 3 có độ dài k : ( ) ( )1 23 3... km a a a= , trong đó ia nhận một trong các giá trị 0,1,2 . Thí dụ, {3 3 0 0....0 k æ ö = ç ÷ è ø ; { 33 3 1 1....1 2 k k æ ö- æ ö =ç ÷ ç ÷ è øè ø ; 3 3 1 22....22k k æ ö - = ç ÷ è ø 14243 . Trong tập các số 0, 1, 2,…, 3 1k - xét tập T tất các số mà biểu diễn của chúng chỉ gồm các chữ số 0 và chữ số 1. Mỗi vị trí trong tất cả k vị trí của các số đó có thể nhận chữ số 0 hoặc chữ số 1 nên có tất cả 2k số. Tổng a b+ của hai số (khác nhau) a và b trong các số này chắc chắn chứa chữ số 1 (tồn tại một vị trí 0k nào đó mà chữ số của a là 0, còn chữ số của b là 1 hoặc ngược lại). Nhưng số 2c , trong đó c cũng thuộc tập trên ( c chỉ có các chữ số 0 và 1) có biểu diễn chỉ gồm các chữ số 0 và 2. Vì vậy đẳng thức 2c a b= + là không xảy ra. Vậy T là tập gồm 2k số cần tìm. Bài 15b (Thi Olympic Quốc tế, 1983) Có thể tìm được hay không 2009 số nguyên dương khác nhau nhỏ hơn hoặc bằng 105 sao cho ba số bất kỳ trong các số đó không lập thành ba số hạng liên tiếp của một cấp số cộng. Giải (sử dụng hệ tam phân) Ta xây dựng một tập hợp T có thể nhiều hơn 2009 số nguyên dương nhỏ hơn 105, sao cho trong tập hợp đó không có ba số liên tiếp nào là ba số hạng của một cấp số cộng, tức là không xảy ra đẳng thức 2x y z+ = với mọi , ,x y z TÎ . Thật vậy, ta xét tập hợp T gồm tất cả các số nguyên dương mà trong cách biểu diễn theo hệ đếm cơ số 3 có nhiều nhất 11 chữ số và mỗi một trong chúng là 0 hoặc 1. Như vậy ta có 211 – 1 = 2047 > 2009 số mà số lớn nhất là: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 77 310 +39 +37+36 + 35+ 34 +33 +32 +31 +30 = 88573 < 105 Giả sử có 2x y z+ = với bộ ba , ,x y z TÎ nào đó. Số 2z với mọi z TÎ chỉ gồm các chữ số 0 và 2. Từ đó suy ra x và y phải bằng nhau từng chữ số một, do đó ta có x y z= = . Vô lý. Vậy T là tập không chứa ba số hạng liên tiếp của một cấp số cộng. Suy ra T thỏa mãn yêu cầu của đầu bài. Bài 16a (Vô địch Trung Mĩ, 1989) Cho hàm số * *:f ®¥ ¥ thỏa mãn ( ) ( ) ( ) ( ) ( ) 1 1 2 1 2 1 2 3 f f n f n f n f n =ì ï + = +í ï =î Tìm tất cả các số m sao cho tồn tại n để ( )m f n= Giải (sử dụng hệ nhị phân) Vì (2 ) 3 ( )f n f n= và (2 1) 1 (2 ) 1 3 ( )f n f n f n+ = + = + với mọi n , tức là (2 )f n và (2 1)f n + đều được tính theo theo ( )f n nên ta nghĩ tới viết các số trong hệ đếm cơ số 2. Ta có: 2 3(2) (10 ) 3 (1) 3 10f f f= = = = ; 2 3(3) (11 ) 1 3 (1) 4 11f f f= = + = = ; 2 3(4) (100 ) 3 (2) 9 100f f f= = = = ; 2 3(5) (101 ) 1 3 (2) 10 101f f f= = + = = ; 2 3(6) (110 ) 3 (3) 12 110f f f= = = = ; 2 3(7) (111 ) 1 3 (3) 13 111f f f= = + = = . Qui luật Giá trị của hàm số ( )f n viết trong cơ số 3 có các chữ số chính là các chữ số của n viết trong hệ đếm cơ số 2, tức là khi ( )1 1 0 2...p pn a a a a-= thì ( )( ) ( )1 1 0 1 1 02 3( ) ... ...p p p pf n f a a a a a a a a- -= = . (1) Chứng minh Giả sử công thức (1) đúng với mọi n k< . Ta chứng minh nó đúng với n k= . Nếu n k= lẻ, thì 2 1n m= + và m k< . Nếu ( )1 1 2...p pm a a a-= thì Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 78 ( ) ( ) ( )1 1 1 1 1 12 2 22 1 2 ... 1 ... 0 1 ... 1p p p p p pn m a a a a a a a a a- - -= + = + = + = . Theo qui nạp ta có ( )( ) ( )1 1 1 12 3( ) ... ...p p p pf m f a a a a a a- -= = . Vậy ( ) ( ) ( ) ( )1 1 1 1 1 13 3 3( ) 2 1 1 3 ( ) 1 3 ... 1 ... 0 ... 1p p p p p pf n f m f m a a a a a a a a a- - -= + = + = + = + = . Nếu n chẵn, thì ( ) ( )1 1 1 12 22 2 ... ... 0p p p pn m a a a a a a- -= = = . Ta có ( ) ( ) ( ) ( )1 1 1 1 33 3( ) 2 3 ( ) 3 ... ... 0p p p pf n f m f m a a a a a a n- -= = = = = . Vậy trong mọi trường hợp ta đều có ( )( ) ( )1 1 0 1 1 02 3... ...p p p pf a a a a a a a a- -= . Từ chứng minh trên ta có: Tất cả các số tự nhiên m cần tìm sao cho tồn tại n để ( )m f n= chính là tập các số tự nhiên được viết trong cơ số 3 mà không có chữ số 2. Bài toán 16b (Vô địch Trung Quốc, 1995) Giả sử :f N N® có (1) 1f = và hai điều kiện sau đây được thỏa mãn với mọi số nguyên dương n : 1) 3 ( ) (2 1) (2 )(1 3 ( ))f n f n f n f n+ = + ; 2) (2 ) 6 ( )f n f n< . Tìm tất cả các nghiệm của phương trình ( ) ( ) 293f k f m+ = . Giải Vì 3 ( )f n và 1 3 ( )f n+ là nguyên tố cùng nhau nên từ điều kiện 1) suy ra, (2 )f n chia hết cho 3 ( )f n , tức là (2 ) .3 ( )f n k f n= với k nguyên dương nào đó. Từ điều kiện 2) suy ra 1k = hay (2 ) 3 ( )f n f n= với mọi n . Lại từ điều kiện 1) suy ra (2 1) 1 3 ( )f n f n+ = + . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 79 Như vậy, ta trở về Bài 16a. Suy ra ( )f n viết trong cơ số 3 có các chữ số chính là các chữ số của n khi ( )1 1 0 2...p pn a a a a-= viết trong hệ đếm cơ số 2, tức là ( )( ) ( )1 1 0 1 1 02 3... ...p p p pf a a a a a a a a- -= . Bởi vì 3293 101212= nên số nghiệm của phương trình ( ) ( ) 293f k f m+ = cũng chính là số cách viết 3101212 dưới dạng tổng của hai số trong hệ đếm cơ số 3 mà các chữ số của nó chỉ có thể là 0 hoặc 1 (do chúng chính là các chữ số trong biểu diễn cơ số 2). Nhận xét rằng cộng hai số như vậy trong hệ đếm cơ số 2 sẽ không có nhớ, vì vậy cả hai phải cùng là 0 tại vị trí thứ 2 (từ bên trái) và cùng là 1 tại ví trí thứ tư và thứ sáu. Tại vị trí thứ nhất, thứ 3 và thứ 5 một số có chữ số là 0 và một số có chữ số là 1. Như vậy, ta có tất cả 4 khả năng sau: 1) 3 3 3101212 101111 000101= + ; 2) 3 3 3101212 100101 001111= + ; 3) 3 3 3101212 101101 000111= + ; 4) 3 3 3101212 100111 001101= + . Vậy phương trình ( ) ( ) 293f k f m+ = có 4 trường hợp: 1) ( ) ( )2 2 3 3 3101111 000101 101111 000101 101212f f+ = + = hay ( ) ( )47 5 283 10 293f f+ = + = ; 2) ( ) ( )2 2 3 3 3100101 001111 100101 001111 101212f f+ = + = hay ( ) ( )37 15 253 40 293f f+ = + = ; 3) ( ) ( )2 2 3 3 3101101 000111 101101 000111 101212f f+ = + = hay ( ) ( )45 7 280 13 293f f+ = + = ; 4) ( ) ( )2 2 3 3 3100111 001101 100111 001101 101212f f+ = + = hay ( ) ( )39 13 256 37 293f f+ = + = . Đáp số: 8 cặp nghiệm k 47 37 45 39 5 15 7 13 m 5 15 7 13 47 37 45 39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 80 Lời bình Đây là các bài toán giải phương trình hàm thường rất hay gặp ở các kì thi học sinh giỏi. Ta thấy trong phát biểu của bài toán không có liên quan tới hệ đếm nhưng khi giải chúng thì phải sử dụng tới các hệ đếm (cơ số 2, cơ số 3,...). Do vậy hệ đếm có thể được xem như một phương pháp để giải quyết một lớp các bài toán về phương trình hàm trên tập số tự nhiên. 2.3 Các bài toán được giải nhờ kết hợp hệ đếm với các dạng toán khác hoặc các phương pháp khác Phương pháp hệ đếm không chỉ liên quan đến các phương trình hàm, mà hệ đếm còn liên quan đến các loại bài toán khác như các bài toán giải phương trình và hệ phương trình, giải phương trình nghiệm nguyên, số thập phân vô hạn tuần hoàn, liên phân số, công thức truy hồi,... Các bài toán sau đây minh họa điều này. Bài toán 17 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1966) Trong cơ số 1R , phân số 1F khai triển thành 0.373737... và phân số 2F khai triển thành 0.737373...; Trong cơ số 2R , phân số 1F khai triển thành 0.252525..., còn phân số 2F khai triển thành 0.525252.... Tổng số 1 2R R+ viết trong cơ số 10 bằng (chọn một trong năm đáp số): a) 24; b) 22; c) 21; d) 20; e) 19. Giải Vì 0.373737... là số “thập phân” vô hạn tuần hoàn nên nó là số hữu tỉ (phân số). Trong hệ đếm cơ số 10, ta có 2 3 2 37 37 37 37 1 1 37 1 370.373737...= ... 1 ... 1100 100 100 100 100 100 100 991 100 æ ö ç ÷æ ö+ + + = + + + = =ç ÷ç ÷ è ø ç ÷- è ø . Tương tự, trong hệ cơ số 1R , ta có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 81 ( ) ( ) ( )1 1 1 2 2 1 1 1 1 1 37 37 3 70.373737... 1 1 1 1R RF R R R R R + = = = = - + - - - ; ( ) ( ) ( )1 1 2 2 2 1 1 1 1 1 73 73 7 30.737373... 1 1 1 1R RF R R R R R + = = = = - + - - - . Tương tự, trong hệ cơ số 2R , ta có ( ) ( ) ( )2 2 1 2 2 2 2 2 2 2 25 25 2 50.252525... 1 1 1 1R RF R R R R R + = = = = - + - - - ; ( ) ( ) ( )2 2 2 2 2 2 2 2 2 2 52 52 5 20.525252... 1 1 1 1R RF R R R R R + = = = = - + - - - . Suy ra: 1 1 11 2 2 2 2 1 1 1 1 3 7 7 3 10 10 10 1 1 1 1 R R RF F R R R R + + + + = + = = - - - - và 2 2 21 2 2 2 2 2 2 2 2 2 5 5 2 7 7 7 1 1 1 1 R R RF F R R R R + + + + = + = = - - - - . Vậy ta có: 1 21 1 10 7 R R- - = hay 1 27 10 3 0R R- + = . Mặt khác, 1 1 11 2 2 2 2 1 1 1 1 3 7 7 3 4 4 4 1 1 1 1 R R RF F R R R R + + - - - = - = - = - - - + và 2 2 21 2 2 2 2 2 2 2 2 2 5 5 2 3 3 3 1 1 1 1 R R RF F R R R R + + - - - = - = - = - - - + . Suy ra 1 21 1 4 3 R R- - = hay 1 23 4 1 0R R- - = . Giải hệ phương trình 1 2 1 27 10 3 0; 3 4 1 0R R R R- + = - + = ta được 1 11R = và 2 8R = . Vậy 1 2 19R R+ = . Đáp án e) là đáp án đúng. Bài toán 18 (Thi trắc nghiệm học sinh giỏi toán toàn nước Mỹ, 1981) Trong hệ đếm cơ số 8, cho một số chính phương 3ab c , trong đó 0a ¹ . Vậy c bằng (chọn một trong năm đáp số): a) 1; b) 2; c) 3; d) 4; e) Không xác định được một cách duy nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 82 Giải Cách 1 Đặt ( )2 83n ab c= với ( )8n de= . Khi ấy ( )22 2 2 28 8 8.2n d e d de e= + = + + . Chứng tỏ số 3 trong 3ab c là chữ số đầu tiên (trong hệ cơ số 8) của tổng các chữ số của hàng chục của 2e (trong hệ cơ số 8) và chữ số đơn vị của ( )82de . Chữ số đơn vị của ( )82de là chẵn nên chữ số hàng chục của 2e phải là lẻ. Ta có tất cả các khả năng sau đây của 2e trong cơ số 8: e 1 2 3 4 5 6 7 2e 1 4 11 20 31 44 61 Vậy chữ số hàng chục của 2e là lẻ khi e bằng 3 hoặc 5. Trong cả hai trường hợp, chữ số hàng đơn vị của 2e là 1. Thử các trường hợp, n là ( )833 ; ( )873 ; ( )845 . Bình phương các số này tương ứng là ( )81331 ; ( )86631 và ( )82531 . Cách 2 Ta có ( )2 3 283 .8 .8 3.8n ab c a b c= = + + + . Nếu n là số chẵn, thì 2 24n k= chia hết cho 4. Do đó số dư của 2n khi chia cho 8 chỉ có thể là 0 hay 4. Nếu n lẻ, tức là 2 1n k= + . Khi ấy ( ) ( )22 22 1 4 4 1 4 1 1n k k k k k= + = + + = + + . Vì ( )1k k + luôn là chẵn nên ( )2 4 1 1n k k= + + khi chia cho 8 luôn có số dư là 1. Như vậy, trong mọi trường hợp, số c chỉ có thể là 0, 1 hay 4. Nếu 0c = thì ( ) ( )2 3 2830 .8 .8 3.8 8 8 3n ab a b p= = + + = + vô lí vì 8 không phải là số chính phương. Nếu 4c = thì ( ) ( )2 3 2834 .8 .8 3.8 4 4 8 7n ab a b q= = + + + = + vô lí vì không có số chính phương lẻ nào có dạng 8 7q + . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 83 Vậy 1c = . Suy ra ( )2 831n ab= và n nhận một trong ba giá trị ( )833 ; ( )873 ; ( )845 . Bình phương các số này tương ứng là ( )81331 ; ( )86631 và ( )82531 . Bài toán 19 (Vô địch Anh, 1982) Một số tự nhiên n NÎ là bội của 17, có biểu diễn trong hệ đếm cơ số 2 chứa đúng 3 chữ số 1. Chứng minh rằng trong biểu diễn đó có không ít hơn 6 chữ số 0. Và nếu có đúng 7 chữ số 0, thì n là chẵn. Giải Vì trong biểu diễn cơ số 2 của n có đúng ba chữ số 1 (các chữ số còn lại bằng 0) nên n có dạng ( )210...010...010...0 2 2 2 k l mn = = + + , trong đó , ,k l m là những số tự nhiên, k l m< < . Giả sử n trong hệ cơ số 2 có ít hơn 6 chữ số 0. Vì n có đúng 3 chữ số 1 nên nó có nhiều nhất là 8 chữ số, do đó 7 6 511100000 2 2 2n £ = + + . Chứng tỏ 7m £ . Nhưng 2i với 0,1,2,...,7i = chỉ có thể đồng dư với 1, 2, 4, 8, -1, -2, -4, -8 theo mod 17. Xem xét tất cả các trường hợp (tổng bộ ba từ các số 1, 2, 4, 8, -1, -2, -4, -8 không thể bằng 0 hoặc bằng bội của 17), ta đi đến kết luận: Số 2 2 2k l mn = + + với 0 7k l m£ < < £ không thể chia hết cho 17. Vậy muốn n chia hết cho 17 thì số chữ số 0 trong biểu diễn cơ số 2 của n phải có ít nhất 6 chữ số 0. Nếu số chữ số 0 trong biểu diễn cơ số 2 của n đúng bằng 7 thì 9m = và 92 2(mod17)º . Khi ấy n không thể là số lẻ, bởi vì nếu n là số lẻ thì n có dạng ( )21...1 2 2 2 m l kn = = + + hay 0k = . Do đó ( ) ( )9 02 2 2 2 3(mod17)m k+ = + º , nghĩa là 2 3(mod17)l º - . Điều này không thể xảy ra với mọi 1,2,...,7,8l = . Vô lí. Vậy n phải là số chẵn. Chọn 9m = , 6l = , 1k = ta có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 84 ( ) 9 621000100010 2 2 2 512 64 2 578 17 34n = = + + = + + = = ´ chia hết cho 17. Bài toán 20 Tìm cơ số k của hệ đếm có cơ số nhỏ hơn 100 để số 2101k là một số chính phương. Giải Số 2101k là một số chính phương nghĩa là tồn tại số n sao cho 3 2 2 22101 2 1 (2 1)( 1)k k k k k k n= + + = - + + = . Do 2 2(2 1) ( 1) 2( 1)k k k k- + + + = + là một số chẵn nên 22 1k k- + và 1k + phải cùng chẵn hoặc cùng lẻ. Vì 22 1 ( 1)(2 3) 4k k k k- + = + - + hay ( )24 2 1 ( 1)(2 3)k k k k= - + - + - nên ước số chung lớn nhất của 22 1k k- + và 1k + phải là ước của 4. Nếu hai số 22 1k k- + và 1k + là lẻ thì ước số chung lớn nhất của chúng là 1, vì vậy 2 2(2 1)( 1)k k k n- + + = khi và chỉ khi 2 2 2 2(2 1)( 1)k k k n p q- + + = = và 2 22 1k k p- + = , còn 21k q+ = . Do 100k < nên cho q lần lượt các giá trị từ 2 đến 10 ta được q 2 3 4 5 6 7 8 9 10 2 1k q= - 3 8 15 24 35 48 63 80 99 22 1k k- + 16 121 436 1129 2416 4561 7876 12721 19504 22 1k k- + 4 11 20.8 33.6 49.1 67.5 88.7 112.7 139.5 Như vậy, chỉ có hai giá trị 3k = , 232101 64 8= = và 8k = , 2 82101 1089 33= = thỏa mãn điều kiện đầu bài. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 85 Nếu hai số 22 1 2k k p- + = và 1 2k q+ = là chẵn thì ước số chung lớn nhất của chúng là 2 hoặc 4. vì vậy 2 2(2 1)( 1)k k k n- + + = khi và chỉ khi 2 2 2 2 1(2 1)( 1) 4 4k k k n p q- + + = = và 2 22 1 2k k p- + = , còn 21 2k q+ = . Do đó 22 1k q= - . Do 100k < nên cho q lần lượt các giá trị từ 2 đến 7 ta không được thêm nghiệm nào. q 2 3 4 5 6 7 22 1k q= - 7 17 31 49 71 97 22 1 2 k k- + 46 281 946 2377 5006 9361 22 1 2 k kp - += 6,7 16,7 30,5 48,7 70,7 96,7 Nhận xét Bằng máy tính, ta có thể kiểm tra và khẳng định, trong khoảng 10000k < cũng chỉ có hai giá trị 3k = và 8k = thỏa mãn điều kiện đầu bài. Ta có thể đặt Câu hỏi Tìm tất cả cơ số k để số 2101k là một số chính phương? Bài toán 21 (Victor Thébault) Tìm mối quan hệ giữa ba số tự nhiên a , k , k¢ để cho số a trong các hệ đếm cơ số k và k¢ đều biểu diễn được dưới dạng một số có ba chữ số của cùng các chữ số. Sử dụng kết quả nhận được, hãy xét 10k = . Giải Phải tìm 1 2 3, ,a a a sao cho ( )1 2 3k ka a a a a= = và ( )1 2 3k ka a a a a¢ ¢¢ ¢ ¢ ¢= = , trong đó ia¢ , 1,2,3i = là hoán vị của 1 2 3, ,a a a , nghĩa là Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 86 2 21 2 3 1 2 3a k a k a a k a k a¢ ¢ ¢ ¢ ¢+ + = + + . (1) Với k , k¢ cố định thì biểu thức trên có thể được viết dưới dạng 1 2 3 0pa qa ra+ + = , (2) trong đó , ,p q r là các hàm nhận giá trị nguyên của các số tự nhiên k , k¢ . Thí dụ, khi 1 3 2 1 3 2, ,a a a a a a¢ ¢ ¢= = = thì (1) có dạng 2 2 1 2 3 3 1 2a k a k a a k a k a¢ ¢+ + = + + và (2) có các hệ số 2 2, 1, 1p k k q k r k¢ ¢= - = - = - . Phương trình (2) có vô số nghiệm dạng ( ) ( ) ( ) ( ) ( ) ( ) 3 2 1 3 2 1 1 2 3; ;, , , , , , n q n r n r n q n p n qa a a p q p r q r p q p r q r = - = - = - , (2’) trong đó ( ),a b là ước chung dương lớn nhất của hai số a và b , còn 1 2 3, ,n n n là các số nguyên bất kì. Ngoài ra, theo định nghĩa cơ số, ta còn có điều kiện 1 2 30 , , ,a a a k k¢£ < . (3) Có thể kiểm tra các số 1 2 3, ,a a a có thỏa mãn đồng thời cả hai điều kiện (2’) và (3) hay không bằng phương pháp thử trực tiếp. Với 10k = : Tất cả các nghiệm đã biết được cho trong bảng sau. Các số mà chữ số đầu tiên (hàng trăm) bằng 0 (biểu diễn trong hệ đếm cơ số bất kì nào đó) không được đưa vào bảng này. 10 7265 526= 10 11283 238= 10 16371 173= 10 19825 258= 10 26919 199= 10 7316 631= 10 11370 307= 10 16913 391= 10 21551 155= 10 26961 191= 10 9158 185= 10 13191 119= 10 18782 278= 10 21912 219= 10 21912 219= 10 9227 272= 10 13774 477= 10 19441 144= 10 22511 115= 10 26912 192= 10 9445 544= 10 14834 438= 10 19518 185= 10 26910 190= 10 16913 319= 10 11196 169= 10 15261 126= 10 19882 288= 10 26911 191= 10 26913 193= Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 87 Trong bảng trên, có hai số thú vị là 10 21 26912 219 192= = và 10 16 28913 391 193= = . Bài toán trên liên quan đến khá nhiều vấn đề khác của toán học. Thí dụ, nếu 1 1a a¢ không phải là số chính phương, thì tồn tại vô số cặp k , k¢ để (2) và (3) đồng thời được thỏa mãn. Thật vậy, giả sử ( ),p q là cặp nghiệm nghiệm nguyên của phương trình Pell 2 21 1 1x a a y¢- = thì, theo công thức nghiệm tổng quát của phương trình Pell, các cơ số 1nk + , 1nk +¢ của hệ đếm được tính theo công thức ( ) ( ) ( ) ( ) 2 2 2 1 1 1 1 2 1 2 2 2 2 1 1 1 1 2 1 2 2 ; 2 . n n n n n n k p a a q k a pqk pqa q a a k a pqk p a a q k pqa q a a + + ì ¢ ¢ ¢ ¢ ¢= + + = +ï í ¢ ¢ ¢ ¢= + + = +ïî (4) thỏa mãn (2), nếu nk , nk¢ thỏa mãn (4). Như vậy, (4) sinh ra một dãy (vô số) các cơ số ik , ik¢ thỏa mãn (2’) và (3), bắt đầu từ một chỉ số 0i nào đó. Dãy này nói chung không chứa tất cả các nghiệm. Nếu ta cho thêm một quan hệ nào đó giữa hai cơ số k , k¢ thì ta có thể nhận được, bằng rất nhiều con đường, nghiệm của (2) phụ thuộc tham số nào đó. Thí dụ, chọn 2 1k k¢ = + , 1 2 2 3 3 1, ,a a a a a a¢ ¢ ¢= = = thì phương trình (1) trở thành ( ) ( )221 2 3 2 3 12 1 2 1a k a k a k a k a a+ + = + + + + . (5) Suy ra ( ) ( )1 2 0 moda a k+ º . Do 1 20 ,a a k£ < nên 1 2a a k+ = . Thay 1 2a k a= - vào phương trình (5) ta được ( ) ( ) ( ) ( )222 2 3 2 3 22 1 2 1k a k a k a k a k a k a- + + = + + + + - . Ước lượng các số hạng đồng dạng, ta đi đến ( )2 2 31 5 3 2k k a a- = + + . Suy ra 2 3 2 22 2 ( 1) 5( 1)a a k k a- = - - + (6) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 88 hay 3 22 2 0(mod( 1))a a k- º + , tức là 3 22 2 ( 1)a a m k- = + với m nguyên. Vì 2 30 ,a a k£ < nên 3 22 2 2 2k a a k- < - < . Vậy 3 22 2 ( 1)a a m k- = + với 0, 1m = ± . Thay vào (6) ta được 2( 1) 5m k a= - - hay 21 5k a m= + - với 0, 1m = ± . Vậy (với 0m = ): 21 5k a= + ; 3 2a a= ; 1 24 1a a= + , 2a bất kì; (với 1m = ): 25k a= ; 23 7 1 2 aa += ; 1 24a a= , 2a là số lẻ bất kì. Khi 1m = - thì 25 2k a= + và 3 2 2 22 2 (5 1) 3 1 0a a a a= - + = - + < nên loại. Tương tự, nếu chọn 1k k¢ = + , ( ) ( )1 2 3 3 1 2k ka a a a a a= thì ta có các nghiệm riêng là 24 3k a= + ; 1 23 3a a= + ; 3 23 1a a= + , 2a bất kì. Nếu chọn 2 1k k¢ = - , ( ) ( )1 2 3 2 3 1k ka a a a a a ¢= thì ta có các nghiệm riêng là 2 35 2 1k a a= - - ; 1 24 1a a= - ; 2 32a a> ; 3a bất kì. Nếu chọn 1k k¢ = + , ( ) ( )1 2 3 2 3 1k ka a a a a a ¢= thì ta có các nghiệm riêng là 1 33 1k a a= + + ; 2 1 32 1a a a= + + , 1 3,a a bất kì. Nếu chọn 2k k¢ = , ( ) ( )1 2 3 2 3 1k ka a a a a a ¢= thì ta có các nghiệm riêng là 27 2k a= + ; 1 24 1a a= + , 1 3,a a k< bất kì. Nếu chọn 2k k¢ = + , ( ) ( )1 2 3 3 2 1k ka a a a a a ¢= thì ta có các nghiệm riêng là 32 1k a= + ; 1 3 2a a= + , 2 0a = , 3a bất kì. Nếu chọn 1k nu¢ = + , ( ) ( )1 2 3 3 2 1k ka a a a a a ¢= thì ta có các nghiệm riêng là 1k nv= + ; 21a u= , 2 2a uv= , 2 3a v= , trong đó , ,u v n là những số nguyên bất kì thỏa mãn hệ bất đẳng thức u v> ; { }2max 1;2 1kv u uv> - - . 2.4 Dãy nhị phân Một dãy n số hạng ( )1 2, ,..., nx x x mà ix chỉ bằng 0 hoặc bằng 1 được gọi là một dãy nhị phân độ dài n . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 89 Nhiều bài toán về dãy nhị phân liên quan mật thiết với hệ đếm cơ số 2. Dưới đây là một số thí dụ. Bài toán 22 (Vô địch Canada, 1991) Tìm tổng tất cả các số nguyên dương có n chữ số 0 và n chữ số 1 viết trong hệ đếm cơ số 2. Giải Ta cần tìm tổng của tất cả các số có dạng ( )1 2 2 2... na a a với 1 1a = và có n chữ số 0, n-1 chữ số 1. Do chữ số đầu tiên bên trái là 1 ( 1 1a = ) nên trong 2 1n - chữ số còn lại thì phải có n chữ số 0 và 1n - chữ số 1. Như vậy có tất cả ( ) ( ) 2 1 ! ! 1 ! n n n - ´ - số thỏa mãn điều kiện đầu bài. Nếu 2 1a = thì 2 2n - chữ số còn lại sẽ có n chữ số 0 và n-2 chữ số 1 nên có ( ) ( ) 2 2 ! ! 2 ! n n n - ´ - số mà có 1 2 1a a= = và trong 2 2n - chữ số còn lại sẽ có n chữ số 0 và 2n- chữ số 1. Tương tự ta xét 3 1a = thì 2 2n - chữ số còn lại sẽ có n chữ số 0 và 2n - chữ số 1 nên có ( ) ( ) 2 2 ! ! 2 ! n n n - ´ - số mà có 1 3 1a a= = và trong 2´n -2 chữ số còn lại sẽ có n chữ số 0 và 2n- chữ số 1. Quá trình cứ tiếp tục như vậy và ta sẽ thu được kết quả ( )1 2 2 2... nS a a a= å = ( )2 1 2 2 2 31 2 3 22 2 2 ...n n n na a a a´ - ´ - ´ -+ + + +å = 2 1 2 2 2 31 2 3 22 2 2 ... n n n na a a a ´ - ´ - ´ - ´´ + ´ + ´ +å å å å = ( ) ( ) ( ) ( ) ( ) 2 1 2 2 2 32 1 ! 2 2 !2 2 2 ... 1 ! 1 ! ! 2 ! n n nn n n n n n ´ - ´ - ´ -- -´ + ´ + + + ´ - ´ - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 90 = ( ) ( ) ( ) ( ) ( ) 2 1 2 12 1 ! 2 2 !2 2 1 ! 1 ! ! 2 ! n nn n n n n n ´ - ´ -- -´ + ´ - ´ - ´ - . Bài toán 23 (Vô địch Hàn Quốc, 1997) Một từ được mã hóa bằng 8 chữ số, mỗi chữ số bằng 0 hoặc bằng 1. Gọi x và y là hai từ có đúng ba vị trí các chữ số khác nhau. Chứng minh rằng tổng số tất cả các từ khác với mỗi một trong hai từ x và y ít nhất 5 vị trí chữ số bằng 38. Bài toán 24 (Dự tuyển vô địch Quốc tế lần thứ 34, 1993) Gọi nS là số các dãy( )1 2, ,..., nx x x với { }0,1ix Î , trong đó không có sáu cụm phần tử liên tiếp nào bằng nhau. Thí dụ, ( )1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0 không chấp nhận được do có sáu cụm giống nhau là ( )1,0,0 . Chứng minh rằng lim nn S®¥ = ¥ . Bài toán 25 (Vô địch Trung Quốc, 2002) Giả sử { }{ }1 2 10. ... 1 0,1 ,1 1n n iM a a a a i n-= Î £ £ - là tập các số thập phân trong hệ đếm cơ số 10. Gọi nT và nS tương ứng là số phần tử của nM và tổng của tất cả các phần tử của nM . Tính lim n n n S T®+¥ . Bài toán 26 (Vô địch toán toàn nước Mỹ, 1996; Vô địch Trung Quốc, 1997) Gọi na là số các dãy nhị phân độ dài n không chứa 3 số hạng liên tiếp 0, 1, trong mỗi dãy. Gọi nb là số các dãy nhị phân độ dài n không chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0 (theo thứ tự như thế) trong mỗi dãy. Chứng minh rằng với mọi số nguyên dương ta có 1 2n nb a+ = . Bài toán 27 (Dự tuyển vô địch Quốc tế lần thứ 42, 2001) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 91 Dãy nhị phân ( )1 2 2, ,..., na x x x= được gọi là dãy cân bằng nếu nó chứa n số 0 và n số 1. Hai dãy nhị phân a và b được gọi là láng giềng nếu ta có thể dịch chuyển một vị trí của a đến một vị trí khác thì được b . Thí dụ, khi 4n = , hai dãy 01101001a = và 00110101b = là láng giềng vì có thể chuyển số 0 ở vị trí thứ sáu (hoặc thứ bảy tính từ bên trái) của a sang vị trí đầu thì được dãy b . Chứng minh rằng tồn tại tập hợp S gồm không quá 2 1 1 n nCn + dãy cân bằng sao cho mỗi dãy cân bằng bất kì độ dài 2n đều bằng hoặc là láng giềng của ít nhất một dãy cân bằng trong S . Bài toán 28 (Peter Ulgar) Những đoạn thẳng ba chữ số của số 1110001011 cho phép nhận được tất cả các số ba chữ số trong hệ đếm cơ số 2, ngoài ra một số nhận được đúng một lần. Với số tự nhiên n bất kì cho trước ta cũng có thể xây dựng được một dãy tương tự gồm hữu hạn các số 0 và 1 theo cách sau. Đầu tiên viết liên tiếp n chữ số 1, sau đó mỗi lần dịch chuyển một kí tự sang bên phải, ta sẽ viết vào chỗ trống chữ số 0, nếu số n chữ số trong cơ số 2 nhận được theo cách làm này chưa gặp trước đây, và viết số 1 nếu ngược lại. Chứng minh rằng dãy số xây dựng theo cách này từ 2 1n n+ - kí tự cũng có tính chất hoàn toàn tương tự như dãy số 0 và số 1 nói ở phần đầu khi 3n = . 2.5 Một số bài toán khác về hệ đếm hoặc sử dụng hệ đếm để giải Bài toán 29 (Vô địch Bungaria, 1968) Chứng minh rằng số knC là lẻ khi và chỉ khi hai số tự nhiên k và n thỏa mãn điều kiện: nếu tại vị trí nào đó trong biểu diễn cơ số 2 của k là chữ số 1, thì tại vị trí ấy trong biểu diễn của n cũng là số 1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 92 Bài toán 30 (Vô địch Châu Á-Thái Bình dương lần thứ 6, 1994) Chứng minh rằng, với bất kì số tự nhiên 1n > , hoặc là tồn tại một lũy thừa của 10 mà khi viết trong hệ cơ số 2 nó sẽ có n chữ số, hoặc là tồn tại một lũy thừa của 10 mà khi viết trong hệ cơ số 5 nó sẽ có n chữ số, nhưng không tồn tại cả hai dạng đó. Bài toán 31 (Dự tuyển vô địch Quốc tế lần thứ 34, 1993) Gọi , ,a b n là các số nguyên dương, 1b > và 1nb a- . Chứng minh rằng biểu diễn của n theo cơ số b phải chứa ít nhất n chữ số khác 0. Bài toán 32 (Vô địch Nhật bản, 1996) Cho một số thực q thỏa mãn 1 5 2 2 q+ < < . Với một số n viết trong hệ nhị phân 11 1 02 2 ... 2 k k kn a a a - -= + + + + , trong đó { }0,1ia Î , 0,1,...,i n= ta định nghĩa np như sau: 1 1 1 0... k k n kp q a q a q a - -= + + + + . Chứng tỏ rằng tồn tại vô hạn số nguyên k sao cho không có số nguyên l nào để 2 2 1k l kp p p +< < . Bài toán 33 (Chọn đội tuyển Hồng Kông thi IMO, lần 2, 1997) Với số nguyên dương n , ta gọi ( )f n là số nguyên k lớn nhất sao cho 2k chia hết n và ( )g n là tổng các chữ số trong biểu diễn nhị phân của n . Chứng minh rằng với mọi số nguyên dương n ta có 1) ( !) ( )f n n g n= - ; 2) ( )2 2 ! ! ! n n n C n n = chia hết cho 4 khi và chỉ khi n không phải là lũy thừa của 2. Bài toán 34 (Dự tuyển vô địch Quốc tế lần thứ 41, 2000) Hàm số f được xác định trên tập hợp các số nguyên không âm và nhận giá trị trên tập hợp các số nguyên không âm, thỏa mãn các điều kiện sau với mọi 0n ³ : 1) (4 ) (2 ) ( )f n f n f n= + ; 2) (4 2) (4 ) 1f n f n+ = + ; 3) (2 1) (2 ) 1f n f n+ = + . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 93 Chứng minh rằng với mỗi số nguyên dương m , số các số nguyên n với 0 2mn£ < và (4 ) (3 )f n f n= bằng 1(2 )mf + . Bài toán 35 (Dự tuyển vô địch Quốc tế lần thứ 34, 1993) Tồn tại hay không một hàm f từ tập các số nguyên dương vào chính nó sao cho với mọi n ta có: (1) 2; ( ( )) ( ) ; ( ) ( 1). f f f n f n n f n f n =ì ï = +í ï < +î Bài toán 36 (Dự tuyển vô địch Quốc tế lần thứ 39, 1998. Canada đề nghị) Cho 0 1 2, , ,...a a a là dãy tăng các số nguyên không âm sao cho mỗi số nguyên không âm có thể biểu diễn duy nhất dưới dạng 2 4i j ka a a+ + , trong đó , ,i j k là các số nguyên phân biệt. Tính 1998a . Bài toán 37 (Dự tuyển vô địch Quốc tế lần thứ 34, 1993) Một tập hữu hạn T các số nguyên dương phân biệt được gọi là DS-tập nếu với mỗi số nguyên thuộc T chia hết tổng của tất cả các số nguyên dương trong T. Chứng minh rằng một tập hữu hạn các số nguyên dương là một tập con của một DS-tập nào đó. Bài toán 38 (Vô địch Ba Lan, 1979) Cho các số tùy ý 1 2, ,..., ma a a NÎ . Chứng minh rằng: 1) Tồn tại một bộ gồm 2mn < số mà tất cả các tập hợp con của nó có tổng khác nhau, đồng thời các tổng ấy có mặt tất cả các số 1 2, ,..., ma a a . 2) Tồn tại một bộ gồm n m£ số mà tất cả các tập hợp con của nó có tổng khác nhau, đồng thời các tổng ấy có mặt tất cả các số 1 2, ,..., ma a a . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 94 KẾT LUẬN Từ nội dung của hai chương luận văn trình bày ở trên ta thấy có thể đưa lý thuyết về hệ đếm và những bài tập từ đơn giản đến phức tạp vào một nội dung học tập trong trường phổ thông. Điều này không những làm tăng khả năng tư duy toán học mà còn thúc đẩy quá trình nghiên cứu, học tập và thực hành trên máy tính của học sinh. Hơn nữa chúng ta cũng biết hệ đếm với cơ số 2, cơ số 8 và cơ số 16 chính là cơ sở hoạt động của máy vi tính. Vì vậy trang bị cho các em kiến thức về hệ đếm cũng giúp các em hiểu hiểu sâu sắc các kiến thức về tin học và toán học. Việc giải quyết các bài toán được phát biểu thông qua ngôn ngữ hệ đếm không phải là vấn đề quá khó khăn nếu như chúng ta đã được trang bị đầy đủ những kiến thức cơ bản về hệ đếm. Mặt khác ta cũng thấy rằng việc suy nghĩ, tư duy để đưa đến cách giải các bài toán trên nó cũng rất phù hợp với trình độ của các em học sinh phổ thông. Đồng thời hệ đếm cũng có thể được xem như một phương pháp để giải quyết các bài toán về phương trình hàm, đặc biệt là các bài toán về phương trình hàm trên tập số tự nhiên. Những bài toán về hệ đếm cũng kích thích những khám phá tìm tòi mới trong giải toán, giúp học sinh nâng cao tư duy sáng tạo trong học tập. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com 95 TÀI LIỆU THAM KHẢO [1] Stephen Barnett, Discrete Mathematics: Numbers and Beyond, Addison Wesley Longman, Singapore, 1998, pp. 1--124. [2] Hoàng Chúng, Số học - Bà chúa của toán học, Nhà xuất bản Giáo dục, Hà Nội, 1997. [3] Phạm Huy Điển, Đinh Thế Lục, Tạ Duy Phượng, Hướng dẫn thực hành tính toán trên chương trình Maple V, Nhà xuất bản Giáo dục, Hà Nội, 1998. [4] Phạm Huy Điển, Hà Huy Khoái, Mã hóa thông tin: Cơ sở toán học và ứng dụng, Nhà xuất bản Đại học Quốc Gia, Hà Nội, 2004. [5] Hà Huy Khoái, Nhập môn Số học thuật toán, Nhà xuất bản Khoa học, Hà Nội, 1996. [6] Hà Huy Khoái, Phạm Huy Điển, Số học thuật toán: Cơ sở lý thuyết và Tính toán thực hành, Nhà xuất bản Đại học Quốc Gia, Hà Nội, 2003. [7] Nguyễn Văn Mậu (Chủ biên), Trần Nam Dũng, Vũ Đình Hòa, Đặng Huy Ruận, Tạ Duy Phượng, Một số ứng dụng của giải tích trong đại số, hình học, số học và toán rời rạc (Tài liệu bồi dưỡng giáo viên hè 2008), Đại học khoa học tự nhiên, Hà Nội, 2008, trang 131 --241. [8] Tạ Duy Phượng, Hệ đếm và ứng dụng (trong bộ sách Chuyên đề bồi dưỡng học sinh giỏi Giải toán trên máy tính điện tử), Nhà xuất bản Giáo dục, Hà Nội, 2007, trang 5--96. [9] Các trang WEB, các tạp chí Toán và các sách tuyển tập thi Olympic. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên www.VNMATH.com