TRƯỜNG THPT CHUYÊN TỈNH THÁI NGUYÊN
CHUYÊN ĐỀ TRẠI HÈ HÙNG VƯƠNG NĂM 2015

SỬ DỤNG DÃY NHỊ PHÂN TRONG MỘT SỐ BÀI TOÁN ĐẾM
•

Mã: TO04

I. MỞ ĐẦU
Trong các kì thi học sinh giỏi và kì thi Quốc gia Trung học phổ thông,
học sinh gặp nhiều bài toán đếm. Các em có thể vận dụng các nguyên lí đếm
cơ bản, nguyên lí đơn ánh, nguyên lí song ánh, sử dụng hệ thức truy hồi hay
hàm sinh… vào giải quyết bài toán. Phương pháp sử dụng dãy nhị phân vào
bài toán đếm là một nội dung nhỏ trong phương pháp sử dụng nguyên lí
song ánh và ít được nhắc đến trong các tài liệu tham khảo. Tuy nhiên, qua
thực tiễn giảng dạy chúng tôi nhận thấy học sinh rất thích thú với phương
pháp này. Do đó, chúng tôi cố gắng sưu tầm một số bài tập cho các em làm
và từ đó bước đầu rút ra một số kinh nghiệm bản thân về phương pháp sử
dụng dãy nhị phân trong một số bài toán đếm.
II. DÃY NHỊ PHÂN VÀ NHỮNG VẬN DỤNG CỦA DÃY NHỊ PHÂN
TRONG MỘT SỐ BÀI TOÁN ĐẾM
1. Một số kiến thức cơ bản về dãy nhị phân
- Dãy nhị phân độ dài n là một dãy bao gồm n phần tử trong đó mỗi
phần tử chỉ nhận một trong hai giá trị là “ 0” hoặc “ 1”.
- Số dãy nhị phân có độ dài n là 2n.
- Số dãy nhị phân có độ dài n, trong mỗi dãy có đúng k thành phần bằng
“ 1” là: Cnk , (k ∈ • , n ∈ • * ).
2, Vận dụng dãy nhị phân trong một số bài toán đếm


Bài 1: Cho một lưới gồm các ô vuông. Các nút được đánh số từ 0 đến

Một đường đi như thế được xem gồm (m + n) đoạn (mỗi đoạn là một
cạnh ô vuông). Tại mỗi đoạn chỉ được chọn một trong hai giá trị đi lên (ta
mã hoá là 1) hay sang phải (ta mã hoá là 0). Số đoạn đi lên đúng bằng n và
số đoạn sang phải đúng bằng m. Bài toán dẫn đến việc tìm xem có bao nhiêu
dãy nhị phân có độ dài (m + n) trong đó có đúng n thành phần bằng 1.
n
Kết quả cần tìm là C m + n .

Nhận xét: Trong bài toán này chúng ta quan tâm tới hướng đi tại mỗi thời
điểm chỉ có hai khả năng là đi lên hoặc sang ngang. Từ đó quy ước mã hóa
để đưa về dãy nhị phân.


Bài 2. Một rạp chiếu phim có 15 máy điều hòa gắn ở các vị trí khác nhau.
Để điều hòa được không khí thì tại mọi thời điểm phải có ít nhất một máy
điều hòa hoạt động. Hỏi có bao nhiêu cách vận hành các máy điều hòa này
để không khí trong rạp luôn được điều hòa?
Giải:
Ta gọi các điều hòa đã cho là H1, H2, …, H15. Tại mỗi thời điểm, điều hòa Hi
bật ta mã hóa bởi số 1 và nếu nó tắt ta mã hóa bởi số 0. Khi đó mỗi cách vận
hành 15 máy điều hòa tương ứng với một dãy nhị có độ dài 15. Cách vận
hành thỏa mãn yêu cầu bài toán tương ứng với dãy nhị phân độ dài 15, trong
đó có ít nhất một thành phần bằng 1. Có duy nhất một dãy nhị phân độ dài
15 mà tất cả các phần tử đều là 0. Do đó kết quả cần tìm là 215 -1 = 32767
cách.
Nhận xét: Trong nhiều bài toán thực tiễn ta gặp hai khả năng chính trong bài
toán là hai quan hệ trái ngược nhau như: “bật” và “tắt”; “đóng” và “mở”;
“thuộc” và “ không thuộc”; “ được” và ‘không được”… Khi gặp những quan
hệ như thế ta có thể nghĩ đến việc đưa bài toán về bài toán liên quan đến dãy
nhị phân. Sau đây là một số bài toán như thế.

! Đếm xem có bao nhiêu cách chia kẹo thỏa mãn yêu cầu bài toán?
? Theo em, trong bài toán có bao nhiêu đối tượng chính?
! Có hai đối tượng chính là em bé và kẹo.
? Điều này có gợi ý cho em ý tưởng gì không?
! Em sẽ đưa bài toán về bài toán liên quan đến dãy nhị phân.
? Vậy em phải quy ước đối tượng nào là 0, đối tượng nào là 1?


! Em nghĩ trong hai đối tượng chính thì một đối tượng là 0 còn đối
tượng kia là 1. Ví dụ, em quy ước mỗi em bé là một số 0, mỗi chiếc kẹo là
một số 1.
? Làm thế nào để có mỗi cách chia kẹo tương ứng với một dãy nhị
phân nào đó?
! Em phải xếp các số 0 và 1 thành một hàng.
? Vậy ý tưởng tiếp theo của em là gì?
! Nếu em bé được 0 kẹo thì em chỉ viết: 0.
Nếu em bé được nhận k chiếc kẹo thì em viết: 0 11...1
{
k
 sË
 1

Em sẽ viết liên tiếp từ em thứ nhất tới em thứ m để tạo thành dãy nhị
phân có m số 0 và n số 1.
? Em có thể minh họa ý đó rõ hơn bằng một ví dụ cụ thể?
! Ví dụ một cách chia 7 kẹo giống nhau cho 3 em bé với em thứ 1
được 3 chiếc kẹo, em thứ 2 không được nhận chiếc kẹo nào còn em thứ 3
nhận 4 chiếc kẹo. Em viết 0111001111.
? Tốt lắm! Vậy bài toán ban đầu em đã biết cách giải?
! Mỗi cách chia kẹo tương ứng với một dãy nhị phân có độ dài

j l . Khi ú trong dóy b j +1 , b j + 2 ,..., bl , mi ai xut hin s chn ln. Vy

tớch b j +1.b j + 2 .....bl l mt s chớnh phng.
Bi 7. [ Balkan 1997]
Lấy m và n là số tự nhiên lớn hơn 1. Gọi S tập hợp có n phần tử. Lấy
A1, A2, A3,,Am là những tập con của S. Giả sử rằng, cứ 2 phần tử bất
kỳ x, y thuộc S đều có 1 tập hợp Ai ( i = 1, m ) thỏa mãn điều kiện: nếu
x Ai thì y Ai còn nếu x Ai thì y Ai. Chứng minh rằng: n 2 .
m

Phõn tớch:


Bi toỏn yờu cu chng minh mt bt ng thc nờn cú th s dng
Nguyờn lớ n ỏnh. Ta thy tp S cú n phn t nờn s tỡm mt n ỏnh t S
ti mt tp T no ú. Tp T phi cú 2 m phn t. Bi toỏn cú hai quan h
thuc v khụng thuc nờn cú th a v bi toỏn dóy nh phõn. M ta ó bit
tp hp cỏc dóy nh phõn cú di m thỡ cú 2 m phn t (do ti mi v trớ
ch cú th chn l 1 hoc 0). Tp T phi liờn quan n m tp nờu trong
bi. Ta cú cỏch xõy dng n ỏnh nh trong li gii sau:
Giải:
Mỗi phần tử x của S ta cho tương ứng với một dãy nhị phân

f ( x ) = ( x1 , x2 ,..., xm ) , với xi = 1 nếu xi Ai và xi = 0 nếu xi Ai .
Chúng ta có ánh xạ:
f: S T =

{( x , x ,..., x
1



Chỳ ý : Cú nhng bi toỏn ta khụng nht thit mó húa v s 0 hoc s 1 m
ta cú th mó húa bi cỏc s khỏc.
Bi 9. Để xem một buổi biểu diễn xiếc, mỗi người phải mua
một vé vào giá 1 USD. Mỗi khán giả chỉ được phép mua một vé. Mọi
người đến mua vé đứng xếp thành một hàng dọc trước cửa bán vé. Mỗi
người chỉ mang đúng một tờ 1 USD hoặc đúng 1 tờ 2 USD. Người bán
vé quên không mang theo tiền. Giả sử có n người mang tờ 1 USD và m
người mang tờ 2 USD ( m n ). Tìm số cách xếp hàng sao cho người có
tờ 1 USD thì được nhận ngay vé, người có tờ 2 USD thì khi đến lượt
của mình được nhận ngay vé và một tờ 1 USD trả lại ?
Giải :
Mã hóa người có tờ 1 USD bởi số 1, người có tờ 2 USD bởi số
2. Mỗi cách xếp hàng bất kỳ tương ứng với một véc tơ có (m+n) thành
phần trong đó n thành phần bằng 1, m thành phần bằng 2. Thành
phần thứ i tương ứng với người xếp hàng ở vị trí thứ i. Số véc tơ như
m
thế là Cn + m .


Một véc tơ gọi là tốt nếu tương ứng với cách xếp hàng thỏa
mãn yêu cầu bài toán. Các véc tơ còn lại gọi là các véc tơ xấu.
Chúng ta đi đếm xem có bao nhiêu véc tơ xấu bằng cách
xây dựng một song ánh từ tập A các véc tơ xấu đến tập B các véc tơ
có (m + n + 1) thành phần .
Mỗi véc tơ của B có hai tính chất :
i, Có m thành phần 2, (n+1) thành phần 1
ii, Thành phần 2 đứng vị trí đầu tiên.
m1
Ta có: B = Cm+n .

Vậy có một song ánh từ A đến B nên số véc tơ tốt bằng:

Cnm+ m - Cmm+n1
Đây cũng là kết quả cần tìm của bài toán.
Nhn xột: Nu thêm giả thiết ở Bi 9 rằng có đã có q người xếp hàng
sẵn . Mỗi người trong họ đều có đúng một tờ 1 USD. Hỏi có bao nhiêu
cách xếp hàng thỏa mãn?
m
n +1
Kt qu: Cn+mq Cm+nq .

Bi 10. Xột tp hp M gm 1985 s nguyờn dng phõn bit, sao cho khụng
cú s no cú c s nguyờn t ln hn 23. Chng minh rng M cha mt tp
con gm 4 phn t m tớch ca 4 phn t ny l ly tha bc 4 ca mt s
nguyờn.
Hng dn:
Vỡ ch cú 9 s nguyờn t khụng ln hn 23 nờn mi mt phn t trong
1985 phn t k ca tp hp M cú th phõn tớch c thnh tha s nguyờn t
trong ú cú nhiu nht l 9 s nguyờn t phõn bit: k = p1 1 . p2 2 ... p9 9 , (*)
k

k

k

trong ú ki 0 v ki nguyờn. Vi mi s hng ca M ta gỏn tng ng vi
mt vector (x1; x2,x9) trong ú: xi = 0 nu s m ki ca pi trong (*)


là chẵn và xi = 1 nếu ki là lẻ. Như thế ta có được 29 vector phân biệt. Theo

2. Balakrishnan, V. K. (1995), Schaum's outline of theory and problems
of combinatorics:[including concepts of graph theory], McGraw-Hill.
3. Bóna, M. (2011), A walk through combinatorics: an introduction to
enumeration and graph theory, World Scientific.
4. Chuan-Chong, C., & Koh, K. M. (1992), Principles and techniques in
combinatorics, World Scientific.