Luận văn thạc sĩ Toán học - Hệ đếm và ứng dụng trong toán Phổ thông - Đỗ Thị Thảo

 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 
 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 
 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 
 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 
 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 
 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 
 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