LÝ THUY
LÝ THUY
Ế
Ế
T T
T T
Ổ
Ổ
H
H
Ợ
Ợ
P
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
B
À
À
I TO
I TO
Á

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

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

a.
Nguyên
Nguyên
l
l
í
í
c
c
ộ
ộ
ng
ng
:
:
- Nếu A và B là hai tập rời nhau (A

B =

) thì
BABA 
- Nếu A
1
, A
2
, …A
k
là k tập đôi một rời nhau thì
kk
AAAAAA 

l
í
í
nhân
nhân
:
:
Một công việc được chia làm k bước thực hiện, bước
thứ i có n
i
cách thực hiện. Khi đó tổng số cách thực
hiện công việc:
n
1
n
2
…n
k
(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?