Trong rất nhiều bài toán tổ hợp, việc chỉ ra sự
tồn tại của một cấu hình tổ hợp thỏa mãn các tính
chất cho trước có ý nghĩa quan trọng về mặt lí
thuyết cũng như thực tế.
62 trang |
Chia sẻ: lylyngoc | Lượt xem: 1946 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Chương 3 Lý thuyết tổ hợp, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
LÝ THUYẾT TỔ
HỢP
Chương 3:
3. 1 BÀI TOÁN TỒN TẠI
3.3 BÀI TOÁN LIỆT KÊ
3.4 BÀI TOÁN TỐI ƯU
TỔ HỢP
3.2 BÀI TOÁN ĐẾM
BÀI TOÁN TỒN
TẠI
MỞ ĐẦU
Trong rất nhiều bài toán tổ hợp, việc chỉ ra sự
tồn tại của một cấu hình tổ hợp thỏa mãn các tính
chất cho trước có ý nghĩa quan trọng về mặt lí
thuyết cũng như thực tế.
Trong tổ hợp xuất hiện một bài toán quan
trọng là Bài toán tồn tại: Xét sự tồn tại của các cấu
hình tổ hợp thỏa mãn các tính chất cho trước.
Một bài toán tồn tại tổ hợp xem là giải xong
nếu hoặc chỉ ra một cách xây dựng cấu hình, hoặc
chứng minh rằng chúng không có. Tuy nhiên cả hai
khả năng trên đều không phải dễ. Để thấy rõ sự phức
tạp của vấn đề, dưới đây ta sẽ xét một số bài toán tồn
tại tổ hợp cổ điển nổi tiếng.
Bài toán 36 sĩ quan:
MỘT SỐ VÍ DỤ
Bài toán này do nhà toán học Euler đưa ra,
nội dung như sau:
Người ta triệu tập từ 6 trung đoàn, mỗi trung
đoàn 6 sĩ quan có 6 cấp bậc khác nhau: thiếu úy, trung
úy, thượng úy, đại úy, thiếu tá, trung tá. Hỏi có thể sắp
xếp 36 sĩ quan này thành hình vuông 66 sao cho mỗi
hàng dọc cũng như hàng ngang đều có đại diện của 6
trung đoàn và cũng có 6 cấp bậc khác nhau.
Để đơn giản ta dùng các chữ cái in hoa A, B,
C, D, E, F để chỉ 6 trung đoàn và các chữ cái thường
a, b, c, d, e, f để chỉ 6 cấp bậc.
Bài toán có thể tổng quát hóa bằng cách thay
số 6 bằng n.
BdCbAcDa
AaDcBbCd
DbAdCaBc
CcBaDdAb
Trong trường hợp n = 4, một lời giải của bài toán 16
sĩ quan:
CbBaAeEdDc
AdEcDbCaBe
DaCeBdAcEb
BcAbEaDeCd
EeDdCcBbAa
Một lời giải cho trường hợp n = 5 của bài toán 25
sĩ quan:
Do lời giải của bài toán có thể biểu diễn bởi
hai hình vuông với các chữ cái hoa và thường xếp
cạnh nhau nên bài toán tổng quát còn có tên gọi là bài
toán hình vuông la tinh trực giao.
Sinh thời, nhà toán học Euler đã mất nhiều
công sức đi tìm lời giải cho bài toán nhưng đã không
thành công. Vì vậy, ông đã đưa ra giả thuyết rằng lời
giải cho bài toán tổng quát là không tồn tại.
Giả thuyết này được nhà toán học Pháp
Tarri chứng minh năm 1901 bằng cách duyệt tất cả
các khả năng xếp. Dựa trên giả thuyết không tồn
tại lời giải cho n = 2 và n = 6, Euler còn đưa ra giả
thuyết tổng quát hơn là: Không tồn tại hình vuông
la tinh trực giao cấp 4k + 2.
Giả thuyết này tồn tại suốt 2 thế kỷ. Mãi đến
năm 1960 ba nhà toán học Mỹ là Boce, Parker,
Sricanda mới chỉ ra một lời giải với n = 10 và sau
đó đưa ra phương pháp xây dựng hình vuông la tinh
trực giao cấp 4k + 2 với k > 1.
Bài toán 2n điểm trên lưới nn ô vuông
Cho một lưới gồm nn ô vuông. Hỏi có thể đặt 2n
điểm trên lưới sao cho không có 3 điểm nào cùng
nằm trên 1 hàng hay 1 cột?
Hiện nay người ta mới biết lời giải đối với n 15.
Sau đây là lời giải với n = 12.
NGUYÊN LÝ DIRICHLET
Nguyên lý Dirichlet (nguyên lý chuồng chim):
Nếu xếp nhiều hơn n đối tượng vào n chiếc hộp thì
tồn tại hộp chứa ít nhất 2 đối tượng.
Ví dụ:
1. Trong 367 người bao giờ cũng có ít nhất 2 người
trùng ngày sinh nhật, bởi vì trong năm có nhiều nhất
366 ngày.
2. Trong một kì thi học sinh giỏi, điểm bài thi
được dánh giá bời một số nguyên trong khoảng từ 0
đến 100.
Hỏi rằng có ít nhất bao nhiêu thí sinh dự thi để
chắc chắn tìm được hai học sinh có kết quả thi như
nhau?
Nguyên lý Dirichlet tổng quát
Nếu xếp n đối tượng vào k chiếc hộp thì tồn tại hộp
chứa không ít hơn n/k đối tượng.
Ví dụ:
1. Trong 100 người thì có ít nhất 9 người trùng
tháng sinh.
2. Có 5 loại học bổng khác nhau. Hỏi rằng phải có ít
nhất bao nhiêu sinh viên để chắc chắn rằng có ít nhất 6
người cùng nhận học bổng như nhau?
Ví dụ:
Chứng minh rằng: Trong hội nghị có n người bao giờ
cũng có 2 người có số người quen trong số những
người tham dự bằng nhau.
HD
Gọi ni là số người quen của người thứ i (i = 1, 2,...,n),
ni {0, 1, …, n – 1}.
Nhưng không thể đồng thời xảy ra có người không
quen ai cả và có người quen (n – 1) người còn lại.
Vậy xảy ra một trong hai trường hợp sau:
n,1i},1n...,,2,1{n
n,1i},2n...,,1,0{n
i
i
Theo nguyên lý Dirichlet thì có 2 người cùng số
người quen.
3.2.3 MỘT SỐ VÍ DỤ ỨNG DỤNG
3.2 BÀI TOÁN ĐẾM
3.2.1 CÁC NGUYÊN LÝ CƠ BẢN
3.2.2 CÁC CẤU HÌNH TỔ HỢP ĐƠN GiẢN
3.2.4 NGUYÊN LÝ BÙ TRỪ
3.2.1 MỘT SỐ NGUYÊN LÍ CƠ BẢN
a. Nguyên lí cộng:
- Nếu A và B là hai tập rời nhau (AB = ) thì
BABA
- Nếu A1, A2, …Ak là k tập đôi một rời nhau thì
kk AAAAAA ...... 2121
+ Phương án 1: có m1 cách thực hiện
+ Phương án 2: có m2 cách thực hiện
……………………………………
+ Phương án k: có mk cách thực hiện
Tổng số cách thực hiện công việc là:
m1 + m2 + …+mk
Một công việc được thực hiện theo k phương án:
Chú ý: Nguyên lí cộng còn được phát biểu như sau:
b. Nguyên lí nhân:
Một công việc được chia làm k bước thực hiện, bước
thứ i có ni cách thực hiện. Khi đó tổng số cách thực
hiện công việc:
n1n2 …nk (cách)
Ví dụ 1:
Một nhà hàng có thực đơn sau:
Khai vị:
1. Salad 2. Súp
Món ăn chính:
1. Thịt bò 2. Thịt lợn 3. Cá
Đồ uống:
1. Trà 2. Sữa 3. Bia 4. Coca
Có bao nhiêu cách chọn bữa ăn gồm: 1 món khai vị, 1
món chính và 1 loại đồ uống?
Ví dụ 2:
Cho 5 kí tự A, B, C, D, E
(a) Có bao nhiêu xâu kí tự có độ dài 4 có thể lập
được từ các kí tự đã cho nhưng không lặp kí tự.
(b) Có bao nhiêu xâu kí tự trong (a) bắt đầu từ B.
(c) Có bao nhiêu xâu kí tự trong (a) không bắt đầu
từ B.
HD:
Gọi xâu s = abcd
a) a có 5 cách chọn, b có 4 cách, c có 3 cách, d có 2
cách
Theo nguyên lý nhân số xâu chữ là:
5.4.3.2 = 120
b) Số xâu chữ bắt đầu từ B: 4.3.2 = 24
c) Số xâu chữ không bắt đầu từ B: 120 – 24 = 196
Ví dụ 3:
a- Đếm các xâu nhị phân có kích thước 1 byte.
b-Đếm các xâu nhị phân có kích thước 1 byte có
hai bit đầu 10 hoặc 01
HD:
a- 1byte = 8 bit, mỗi bit có 2 cách chọn (0 hoặc 1).
Theo nguyên lí nhân có: 28 = 256 số 1 byte
b- Bắt đầu bằng 10 có 26 = 64 số
- Bắt đầu bằng 01 có 26 = 64 số
Vậy có 64 + 64 =128 số 1 byte bắt đầu bằng 10 hoặc 01
a. Hoán vị
3.2.2 CÁC CẤU HÌNH TỔ HỢP ĐƠN GIẢN
* Một hoán vị của n phần tử là một cách sắp xếp
thứ tự n phần tử đó.
* Số các hoán vị của n phần tử: n!
Có bao nhiêu cách xếp 3 người Việt, 5 người Pháp
và 6 người Mỹ ngồi một ghế dài sao cho người
cùng quốc tịch ngồi cạnh nhau?
Ví dụ 4:
b. Chỉnh hợp lặp
* Một chỉnh hợp lặp chập k của n phần tử là một bộ
có thứ tự gồm k phần tử lấy từ n phần tử đã cho, các
phần tử có thể được lặp lại.
* Số các chỉnh hợp lặp chập k của n phần tử:
kk
n nA
Ví dụ 5:
Có bao nhiêu số hàng trăm được thiết lập từ các
chữ số: 1, 2, 3, 4, 5?
* Số các chỉnh hợp không lặp chập k của n phần tử:
)!kn(
!n
)1kn)...(1n.(nAkn
c. Chỉnh hợp (không lặp)
* Một chỉnh hợp chập k của n phần tử là một bộ có
thứ tự gồm k phần tử lấy từ n phần tử đã cho, các phần
tử không được lặp lại.
Ví dụ 6:
Có bao nhiêu số hàng trăm với 3 chữ số khác nhau
được thiết lập từ các chữ số: 1, 2, 3, 4, 5?
d. Tổ hợp
* Một tổ hợp chập k của tập X gồm n phần tử là một
tập con có k phần tử của X.
* Số các tổ hợp chập k của n phần tử:
)!(!
!
knk
n
C kn
Ví dụ 7:
a. Có n đội thi đấu vòng tròn. Hỏi phải tổ chức chức
bao nhiêu trận đấu?
b. Có bao nhiêu xâu nhị phân độ dài 32 mà trong đó
có đúng 6 số 1?
HD:
b. Số xâu nhị phân: 6
32C
a. Số trận đấu: 2
nC
Ví dụ 8:
a. Có bao nhiêu hoán vị của các chữ cái trong xâu
ABCDEF mà trong đó có chứa xâu con DEF?
3.2.3 MỘT SỐ VÍ DỤ ỨNG DỤNG
a. Bài toán đếm cách xếp chỗ
b. Có bao nhiêu hoán vị của các chữ cái trong xâu
ABCDEF mà trong đó 3 chữ các D, E, F đứng
cạnh nhau?
Ví dụ 9:
Một nhóm sinh viên có 7 nam và 5 nữ xếp thành
hàng dọc. Hỏi có bao nhiêu cách sắp xếp hàng để
không có 2 nữ nào đứng cạnh nhau?
(*Cho sv đề xuất cách giải, nếu ko được gọi 2
sinh lên ghi 2 cách xếp sau cho 2 nữ không
đứng cạnh nhau*=> tổng quát cách giải.*)
Ví dụ 10:
Có bao nhiêu cách xếp k bít 0 và m bít 1 (k m)
trên hàng ngang sao cho không có 2 bit 0 kề nhau?
Ví dụ 11:
Cho lưới hình chữ nhật gồm mxn ô vuông (xem hình vẽ)
(0, 0)
(n, m)(0, m)
(n, 0)
b. Bài toán đếm số đường đi
Có bao nhiêu cách đi từ nút (0, 0) đến (n, m) nếu
chỉ cho phép đi trên cạnh các ô vuông theo chiều
sang phải hoặc lên trên?
3.2.4 NGUYÊN LÝ BÙ TRỪ
- Cho A và B là hai tập bất kì thì
BABABA
- A, B, C là 3 tập bất kì thì
CBACB
CABACBACBA
Ví dụ 12:
Có bao nhiêu xâu nhị phân có độ dài 10 hoặc bắt
đầu bởi 00 hoặc kết thúc bởi 11?
3.3.3 THUẬT TOÁN QUAY LUI
3.3 BÀI TOÁN LIỆT KÊ
3.3.1 GiỚI THIỆU BÀI TOÁN
3.3.2 PHƯƠNG PHÁP SINH
3.3.1 GiỚI THIỆU BÀI TOÁN
Ví dụ:
Một băng video có thể ghi được C giây. Ta có n phim
video với lượng thời gian tương ứng là: t1, t2, …, tn. Ta
phải chọn k phim i1, i2, …, ik sao cho tổng thời gian:
}i,...i,i{i
i
k21
t
lớn nhất và không vượt quá C.
Một cách chân phương là liệt kê tất cả các tập
con {i1, i2, …, ik} của tập gồm n phim và chọn tập có
tổng trên là lớn nhất và không vượt quá C.
Trong nhiều trường hợp, khi không có thuật
toán để giải quyết những bài toán như trên thì phương
pháp liệt kê với sự trợ giúp của máy tính vẫn là
phương pháp khả dĩ.
* Bài toán liệt kê là bài toán đưa ra danh sách tất cả
cấu hình tổ hợp có thể có.
* Bài toán liệt kê xác định thuật toán xây dựng lần
lượt cấu hình quan tâm, thuật toán cần bảo đảm
các yêu cầu sau:
- Không lặp lại cấu hình
- Không bỏ sót cấu hình
3.3.2 PHƯƠNG PHÁP SINH
a. Thứ tự từ điển
Cho s = s1, s2,..., sp và t = t1, t2,..., tq là hai dãy gồm
các số hoặc ký tự.
i. p < q và si = ti với mọi i = 1, 2, ..., p
ii. Tồn tại k min{p, q} sao cho: si = ti với mọi
i = 1, 2,...,k – 1 và sk < tk
Ta nói rằng s nhỏ hơn t (theo nghĩa từ điển), ký hiệu s
< t, nếu thoả mãn 1 trong 2 điều kiện sau đây:
Ví dụ:
* 132 … 1324
* AN … ANH
* BANDIT … BANK
* 13246 … 1341
b. Thuật toán sinh tổng quát
+ B1: Khởi tạo, gán s so
Kí hiệu s là cấu hình hiện hành, so là cấu hình đầu
tiên (theo thứ tự từ điển)
+ B2: Kết xuất s
+ B3: Kiểm tra tiêu chuẩn kết thúc:
Nếu s là cấu hình cuối thì kết thúc, ngược lại
sang bước 4
+ B4: Tìm cấu hình t đứng sau s theo thứ tự từ điển.
Gán s t và quay lại bước 2
c. Liệt kê tất cả các dãy nhị phân có độ dài bằng n
Cho n N. Hãy liệt kê (theo nghĩa từ điển) tất cả
các dãy nhị phân độ dài n, tức là dãy [b1, b2, ...,bn]
với bi {0, 1}, i = 1, 2, …, n.
Số dãy nhị phân là 2n và dãy nhị phân đầu tiên:
so = [0, 0, ..., 0]
* Phát biểu bài toán
Cho dãy nhị phân s = [s1, s2, …, sn], ta tìm dãy
kế tiếp t = [t1, t2, …, tn].
- Từ dãy s, xuất phát từ sn đi từ phải sang trái tìm
phần tử đầu tiên sm, 1 m n, thỏa sm = 0.
+ Nếu không tìm thấy thì s = [1, 1, ..., 1] là dãy cuối
cùng kết thúc
Phương pháp tìm dãy kế tiếp
+ Nếu tìm thấy thì ta xây dựng dãy t = [t1, t2, ..., tn]
như sau:
ti = si với i = 1, 2, ..., m – 1
tm = 1
ti = 0 với i = m + 1, m + 2, ...., n
Ví dụ:
Cho dãy nhị phân s = [010011], tìm dãy kế tiếp?
Thuật toán liệt kê dãy nhị phân
- Đầu ra: Danh sách tất cả các dãy nhị phân độ dài n
theo thứ tự từ điển tăng dần.
+ B2: Kết xuất s.
+ B1: Khởi tạo: Gán si = 0 với mọi i = 1, 2, ...., n
- Đầu vào: nhập n
+ Bước 3: Tìm m thoả mãn m = max{i | si = 0}
Nếu không tìm thấy thì s = [1,1,...,1] là dãy cuối
cùng kết thúc
Nếu tìm thấy ta đặt:
sm 1 và si 0 với mọi i = m + 1, m + 2, ..., n
Quay lại bước 2.
VÍ DỤ
Liệt kê các dãy nhị phân có độ dài 3
3.3.3 THUẬT TOÁN QUAY LUI
Nội dung chính của thuật toán này là xây dựng dần
các thành phần của cấu hình bằng cách thử tất cả các
khả năng.
Giả thiết cấu hình cần được mô bằng một dãy gồm n
thành phần x1x2...xn
Giả sử đã xác định được i – 1 thành phần x1, x2, ..., xi-1.
Ta xác định thành phần thứ i là xi bằng cách duyệt tất
cả các khả năng có thể có (đánh số các khả năng từ 1
đến ni).
Với mỗi khả năng j, kiểm tra xem khả năng j có chấp
nhận được không. Có thể có 2 trường hợp sau:
- Nếu j được chấp nhận thì xác định được xi theo j,
sau đó nếu i = n thì ta có được một cấu hình, còn nếu
i < n thì tiến hành xác định xi+1
- Nếu thử tất cả các khả năng mà không có khả năng
nào được chấp nhận thì quay lại bước trước để xác
định lại xi-1
Bước xác định xi có thể được diễn tả qua thủ tục đệ quy sau:
Procedure try(i:integer)
var j: integer
begin
for j 1 to ni do
if then
begin
if i = n then
else try(i + 1);
end;
End;
Đoạn chương trình chính của bài toán liệt kê có dạng:
Begin
Init; Try(1)
End.
Đoạn chương trình liệt kê các dãy nhị phân có độ dài n:
Var
n:integer
x: array[0..20] of 0..1
VÍ DỤ
Procedure Try(i:integer);
Var j: integer;
Begin
for j 0 to 1 do
begin
x[i] j;
if i = n then Result else Try(i+1)
end;
Begin
Init; Try(1);
End.