bài giảng về bài toán tồn tại bkhn

Nội dung phần 1: Lý thuyết tổ hợp Chương 1. Bài toán đếm
Chương 2. Bài toán tồn tại Toán rời rạc
Chương 3. Bài toán liệt kê tổ hợp Nhóm chuyên môn:
Chương 4. Bài toán tối ưu tổ hợp Nguyễn Khánh Phương Đỗ Phan Thuận Phạm Quang Dũng Huỳnh Thanh Bình Trần Vĩnh Đức Bùi Quốc Trung Đinh Viết Sang Ban Hà Bằng 1 3
Chương 2. BÀI TOÁN TỒN TẠI Phần thứ nhất 1. Giới thiệu bài toán
2. Các kỹ thuật chứng minh cơ bản LÝ THUYẾT TỔ HỢP 3. Nguyên lý Dirichlet Combinatorial Theory 4. Định lý Ramsey 1 1. Giới thiệu bài toán
Chương 2. BÀI TOÁN TỒN TẠI
• Trong chương trước, ta đã tập trung chú ý vào việc đếm số cấu hình tổ
hợp. Trong những bài toán đó, sự tồn tại của các cấu hình là hiển nhiên,
và công việc chính là đếm số phần tử thỏa mãn tính chất đặt ra. 1. Giới thiệu bài toán
• Tuy nhiên, trong rất nhiều bài toán tổ hợp, việc chỉ ra sự tồn tại của 1
2. Các kỹ thuật chứng minh cơ bản
cấu hình thỏa mãn các tính chất cho trước là hết sức khó khăn.
• Chẳng hạn khi 1 cầu thủ cần tính toán các nước đi của mình để giải 3. Nguyên lý Dirichlet
đáp xem liệu có khả năng thắng hay không ?
• Một người giải mật mã cần tìn kiếm chìa khóa giải cho một bức mật 4. Định lý Ramsey
mã mà anh ta không biết liệu đây có đúng là bức điện thật được mã
hóa của đối phương hay không, hay chỉ là bức mật mã của đối
phương tung ra nhằm đảm bảo an toàn cho bức điện thật...
• Trong tổ hợp xuất hiện vấn đề thứ 2 rất quan trọng là: xét sự tồn tại của
các cấu hình tổ hợp với các tính chất cho trước – bài toán tồn tại tổ hợp. Bài toán về 36 sĩ quan
2. Các kỹ thuật chứng minh cơ bản
• Bài toán này được Euler đề nghị, nội dung của nó như sau:
2.1. Chứng minh trực tiếp (Direct Proof)
2.2. Chứng minh bằng phản chứng (Proof by Contradiction)
“Có một lần người ta triệu tập từ 6 trung đoàn mỗi trung đoàn 6 sĩ quan
thuộc 6 cấp bậc khác nhau: thiếu úy, trung uý, thượng uý, đại uý, thiếu
2.3. Chứng minh bằng phản đề (Proof by Contrapositive)
tá, trung tá về tham gia duyệt binh ở sư đoàn bộ. Hỏi rằng có thể xếp 36
2.4. Chứng minh bằng qui nạp toán học (Proof by Mathematical Induction)
sĩ quan này thành một đội ngũ hình vuông sao cho trong mỗi một hàng
ngang cũng như mỗi một hàng dọc đều có đại diện của cả 6 trung đoàn
và của cả 6 cấp bậc sĩ quan.” 2
2.1. Chứng minh trực tiếp (Direct proofs)
2. Các kỹ thuật chứng minh cơ bản
Chúng ta bắt đầu bằng ví dụ chứng minh tính bắc cầu của tính chất
2.1. Chứng minh trực tiếp (Direct Proof) chia hết.
2.2. Chứng minh bằng phản chứng (Proof by Contradiction)
Định lý. Nếu a chia hết b và b chia hết c thì a chia hết c.
2.3. Chứng minh bằng phản đề (Proof by Contrapositive)
Chứng minh. Theo giả thiết, và định nghĩa tính chia hết, ta suy ra tồn tại các số nguyên k
2.4. Chứng minh bằng qui nạp toán học (Proof by Mathematical 1 và k2 sao cho a = b k Induction) 1 và b = c k2. • Suy ra a = b k2 = c k1 k2.
• Đặt k = k1 k2. Ta có k là số nguyên và a = c k, do đó theo định nghĩa về
tính chia hết, a chia hết c.
2.1. Chứng minh trực tiếp (Direct proofs)
2.2. Chứng minh bằng phản chứng Nếu P, thì Q (If P, Then Q)
• Trong chứng minh bằng phản chứng ta sử dụng các giả thiết và mệnh
• Phần lớn các định lý (các bài tập hay bài kiểm tra) mà bạn cần chứng minh
đề phủ định kết quả cần chứng minh và từ đó cố gắng suy ra các điều
hoặc ẩn hoặc hiện có dạng “Nếu P, Thì Q".
phi lý hoặc các mâu thuẫn với giả thiết ban đầu.
• Trong ví dụ vừa nêu: Nếu a chia hết b và b chia hết c thì a chia hết c.
• "P" là “Nếu a chia hết b và b chia hết c " còn "Q" là "a chia hết c".
• Nghĩa là nếu phải chứng minh “Nếu P, Thì Q", ta giả thiết rằng “P và
• Đây là dạng phát biểu chuẩn của rất nhiều định lý.
Not Q” là đúng. Mâu thuẫn thu được có thể là một kết luận trái với một
• Chứng minh trực tiếp có thể hình dung như là một dãy các suy diễn bắt đầu từ
trong những giả thiết đã cho hoặc điều phi lý, chẳng hạn như 1 = 0.
“P” và kết thúc bởi "Q“: P  ...  Q 3
2. Các kỹ thuật chứng minh cơ bản Ví dụ (P  Q) (¬Q  ¬P)
2.1. Chứng minh trực tiếp (Direct Proof)
Ví dụ. Nếu x và y là hai số nguyên sao cho x+y là số chẵn, thì x và y có
2.2. Chứng minh bằng phản chứng (Proof by Contradiction) cùng tính chẵn lẻ.
2.3. Chứng minh bằng phản đề (Proof by Contrapositive)
Chứng minh. Mệnh đề phản đề của khẳng định đã cho là
2.4. Chứng minh bằng qui nạp toán học (Proof by
“Nếu x và y là hai số nguyên không cùng chẵn lẻ, thì tổng của chúng là Mathematical Induction) số lẻ."
• Vì thế ta giả sử rằng x và y không cùng chẵn lẻ. Không giảm tổng quát,
giả sử rằng x là chẵn còn y là lẻ. Khi đó ta tìm được các số nguyên k và
m sao cho x = 2k và y = 2m+1. Bây giờ ta tính tổng x+y = 2k + 2m + 1
= 2(k+m) + 1, mà rõ ràng là số lẻ.
• Từ đó suy ra khẳng định cuả ví dụ là đúng.
2.3. Chứng minh bằng phản đề
2. Các kỹ thuật chứng minh cơ bản
• Chứng minh bằng phản đề sử dụng sự tương đương của hai mệnh đề "P
2.1. Chứng minh trực tiếp (Direct Proof)
kéo theo Q" và “Phủ định Q kéo theo phủ định P".
2.2. Chứng minh bằng phản chứng (Proof by Contradiction) (P  Q) (¬Q  ¬P).
2.3. Chứng minh bằng phản đề (Proof by Contrapositive)
• Do đó, để chứng minh “Nếu P, Thì Q" bằng phương pháp phản đề, ta
2.4. Chứng minh bằng qui nạp toán học (Proof by
chứng minh “Nếu phủ định Q thì có phủ định P” ("If Not Q, Then Not Mathematical Induction) P”). 4
2.4. Chứng minh bằng qui nạp toán học
Chương 2. BÀI TOÁN TỒN TẠI
• Đây là kỹ thuật chứng minh rất hữu ích khi ta phải chứng
minh mệnh đề P(n) là đúng với mọi số tự nhiên n  n0. 1. Giới thiệu bài toán
• Tương tự như nguyên lý “hiệu ứng domino”.
2. Các kỹ thuật chứng minh cơ bản 3. Nguyên lý Dirichlet 4. Định lý Ramsey
Sơ đồ chứng minh bằng qui nạp
Phát biểu nguyên lý Dirichlet
Giả sử ta cần chứng minh P(n) là đúng n  n
Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì bao giờ cũng tìm được ít 0 .
nhất một cái hộp chứa ít ra là hai đối tượng (  2 ).
• Cơ sở qui nạp: Chứng minh P(n0) là đúng.
• Giả thiết qui nạp: Giả sử P(n) là đúng
• Bước chuyển qui nạp: Chứng minh P(n+1) là đúng. • 7 đối tượng
• Kết luận: Theo nguyên lý qui nạp ta có P(n) là đúng n  n • 6 hộp 0.
Chứng minh. (Phản chứng).
Giả sử ngược lại là không tìm được cái hộp nào chứa  2 đối tượng.
 Điều đó có nghĩa là mỗi cái hộp chứa  1 đối tượng.
 Tổng số đối tượng xếp trong n cái hộp  n
 Trái với giả thiết là có nhiều hơn n đối tượng được xếp trong chúng. 5
Phát biểu nguyên lý Dirichlet
Nguyên lý Dirichlet tổng quát
Lập luận trên đã được nhà toán học người Đức là Dirichlet vận dụng
thành công vào việc giải quyết rất nhiều bài toán tồn tại tổ hợp.
Nguyên lý Direchlet: “Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì
bao giờ cũng tìm được ít nhất một cái hộp chứa  2 đối tượng”.
Trong tài liệu tiếng Anh lập luận đó lại được trình bày trong ngôn ngữ của các con chim bồ câu:
Khi số lượng đối tượng vào k cái hộp vượt quá số lượng cái hộp nhiều
lần thì rõ ràng khẳng định trong nguyên lý về sự tồn tại cái hộp chứa ít ra
“Nếu đem nhốt nhiều hơn n con chim bồ câu vào n cái lồng thì bao
là 2 đối tượng là quá ít. Trong trường hợp như vậy ta sử dụng nguyên lý
giờ cũng tìm được ít nhất 1 cái lồng chứa ít ra là 2 con chim bồ câu”.
Dirichlet tổng quát sau đây:
Vì thế nguyên lý còn có tên gọi là “Nguyên lý về các lồng chim bồ câu”.
“Nếu đem bỏ n đối tượng vào k cái hộp thì bao giờ cũng tìm được ít nhất
một cái hộp chứa  n/k đối tượng”.
Ở đây ký hiệu  gọi là phần nguyên già của số thực  - theo định nghĩa
là số nguyên nhỏ nhất còn lớn hơn hoặc bằng . Ví dụ Ví dụ
Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì bao giờ cũng tìm được ít
“Nếu đem bỏ n đối tượng vào k cái hộp thì bao giờ cũng tìm được ít nhất
nhất một cái hộp chứa ít ra là hai đối tượng (  2 ).
một cái hộp chứa  n/k đối tượng”.
Ví dụ 3. Trong nhóm gồm 100 người có ít nhất bao nhiêu người sinh cùng 1
Ví dụ 1. Trong số 13 người luôn tìm được 2 người sinh cùng tháng vì tháng ?.
chỉ có tất cả 12 tháng.
Giải: Xếp những người cùng sinh 1 tháng vào 1 nhóm. Có 12 tháng tất cả. Vậy
theo nguyên lý Dirichlet, tồn tại ít nhất 1 nhóm có không ít hơn 100/12 = 9
Ví dụ 2. Trong kì thi học sinh giỏi điểm bài thi được đánh giá bởi 1 số người
nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất phải có bao nhiêu
học sinh dự thi để cho chắc chắn tìm được 2 học sinh có kết quả thi như nhau?
Giải. Có 101 kết quả điểm thi khác nhau
 Theo nguyên lý Dirichlet, số học sinh cần tìm là 102 6 Ví dụ mở đầu
Chương 2. BÀI TOÁN TỒN TẠI 1. Giới thiệu bài toán
2. Các kỹ thuật chứng minh cơ bản A Nếu như một trong số 3 cung AB, AC, 3. Nguyên lý Dirichlet BC có màu xanh thì P B nó cùng với hai trong 4. Định lý Ramsey số ba cung PA, PB, PC tạo thành một tam giác xanh. C E D Toán rời rạc Fal 2006 Ví dụ mở đầu Ví dụ mở đầu
• Trong mặt phẳng cho 6 điểm được nối với nhau từng đôi một bởi các cung
màu xanh hoặc màu đỏ. Chứng minh rằng luôn tìm được 3 điểm sao cho
các cung nối chúng có cùng một màu (ta sẽ nói là chúng tạo thành tam giác xanh hoặc đỏ). A Nếu cả 3 cung
• Giải: Chọn điểm P nào đó. Từ nó có 5 cung nối với 5 điểm còn lại. Theo AB, AC, BC có
nguyên lý Dirichlet, có 3 trong số 5 cung đó phải có cùng một màu, chẳng P
hạn là màu xanh. Giả sử đó là các cung PA, PB, PC. B màu đỏ thì chúng tạo thành một tam
• Nếu như một trong số 3 cung AB, AC, BC có màu xanh thì nó cùng với
hai trong số ba cung PA, PB, PC tạo thành một tam giác xanh. Nếu ngược giác đỏ.
lại thì tam giác ABC là một tam giác đỏ. C E D Toán rời rạc Toán rời rạc Fal 2006 Fal 2006 7 Phân tích ví dụ Các số Ramsey
• Một cách phát biểu khác của kết quả vừa chứng minh là: Trong số 6 người tại
một bàn tiệc luôn tìm được hoặc ba người đôi một quen nhau hoặc ba người
Để có thể phát biểu những kết quả tổng quát hơn chúng ta cần đến một đôi một không quen nhau. số khái niệm. • Định nghĩa 1. Gọi K
• Có thể thấy rằng nếu thay con số 6 bởi n > 6 thì khẳng định trong ví dụ vẫn
n là bộ gồm hai tập V, E, trong đó V là tập gồm n
điểm còn E là tập các đoạn nối giữa tất cả các cặp điểm trong V.
đúng. Nhưng nếu thay con số 6 bởi 5 thì khẳng định trong ví dụ không còn
đúng nữa như chỉ ra trong hình vẽ sau đây
• Ta sẽ ký hiệu Kn = (V, E).
• Các phần tử của V được gọi là các đỉnh, và V là tập đỉnh của Kn.
• Mỗi đoạn nối hai đỉnh u, v  V sẽ được gọi là một cạnh của Kn và ký
hiệu là (u, v), và tập E được gọi là tập cạnh của Kn. Toán rời rạc Toán rời rạc Fal 2006 Fal 2006 Phân tích ví dụ Các số Ramsey
• Như vậy có thể thấy 6 là giá trị n nhỏ nhất để khẳng định trong ví dụ là
• Ta có thể phát biểu lại kết quả trong ví dụ mở đầu như sau: “Giả đúng. sử mỗi cạnh của K
• Chúng ta có thể đặt ra các câu hỏi tương tự như: Hỏi ít nhất phải có bao
6 được tô bởi một trong hai màu xanh hoặc đỏ.
nhiêu người để chắc chắn tìm được hoặc 4 người đôi một quen nhau
Khi đó K6 luôn chứa hoặc K3 với tất cả các cạnh được tô màu
hoặc 4 người đôi một không quen nhau? Hỏi ít nhất phải có bao nhiêu xanh (gọi tắt là K
người để chắc chắn tìm được hoặc 5 người đôi một quen nhau hoặc 5
3 xanh) hoặc K3 với tất cả các cạnh được tô màu
người đôi một không quen nhau?
đỏ (gọi tắt là K3 đỏ).
• Con số nhỏ nhất nhắc đến trong các câu hỏi trên được gọi là các số
• Chúng ta sẽ nói rằng số 6 có tính chất (3,3)-Ramsey.
Ramsey, mang tên nhà toán học người Anh đã chứng minh được định
lý nổi tiếng trong lý thuyết tập hợp là sự tổng quát hoá nguyên lý Dirichlet. Toán rời rạc Toán rời rạc Fal 2006 Fal 2006 8 Các số Ramsey Các số Ramsey
• Ta có thể chứng minh khẳng định này bằng cách duyệt tất cả 215 = 32
768 cách tô màu cạnh. Luôn tìm được tam giác cùng màu (xanh hoặc
Ví dụ. Tìm R(2,7) - số nguyên dương nhỏ nhất có tính chất (2,7)- đỏ). Ramsey.
• Loại bỏ các cấu hình không khác nhau bởi phép biến hình: còn 78 tình Giải: huống:
• Trước hết ta tìm số nguyên dương n sao cho với mọi cách tô các cạnh
của Kn bởi hai màu xanh, đỏ luôn tìm được hoặc K2 đỏ hoặc K7 xanh.
R(2,7) là số nhỏ nhất có tính chất này. Toán rời rạc Toán rời rạc Fal 2006 Fal 2006 Các số Ramsey Các số Ramsey
• Định nghĩa 2. Giả sử i và j là hai số nguyên sao cho i  2, j  2. Số
• Xét một cách tô màu (tuỳ ý) các cạnh của K7. Rõ ràng hoặc là tìm được
nguyên dương m có tính chất (i, j)-Ramsey nếu Km với mỗi cạnh được
ít nhất một cạnh của K7 được tô màu đỏ, hoặc là tất cả các cạnh của nó
tô bởi một trong hai màu xanh, đỏ luôn chứa hoặc là Ki đỏ hoặc là Kj
đều được tô bởi màu xanh. Nếu có cạnh tô màu đỏ thì rõ ràng ta có K2 xanh.
đỏ. Còn nếu tất cả các cạnh đều tô bởi màu xanh thì ta có K7 xanh. Vậy
• Từ phân tích ở trên ta thấy 6 có tính chất (3,3)-Ramsey, và mọi số n<6
số 7 có tính chất (2,7)-Ramsey, và vì thế R(2,7)  7.
đều không có tính chất này. Vậy 6 là số nhỏ nhất có tính chất (3,3)-
• Nhưng R(2,7) không thể nhỏ hơn 7, bởi vì nếu tô tất cả các cạnh của K6 Ramsey.
bởi màu xanh ta sẽ không tìm được K2 đỏ và cũng không tìm được K7 xanh.
• Định nghĩa 3. Số Ramsey R(i,j) là số nguyên dương nhỏ nhất có tính • Vậy R(2,7) = 7. chất (i,j)-Ramsey.
• Chẳng hạn, từ kết quả vừa trình bày ở trên, ta có R(3,3) = 6. Toán rời rạc Toán rời rạc Fal 2006 Fal 2006 9 Các số Ramsey Các số Ramsey
• Các tính chất cơ bản sau đây của số Ramsey R(i,j) có thể chứng minh
• Các số R(i, j) vừa trình bày ở trên chỉ là một trong số nhiều dòng số Ramsey đã được nghiên cứu.
bằng các lập luận tương tự như trong các ví dụ đã trình bày:
• Việc xác định R(i, j) với những giá trị i, j cụ thể luôn là các bài toán tổ hợp • R(i,j) = R(j,i);
không tầm thường. Hiện nay người ta mới biết giá trị của R(i, j) với rất ít giá trị của (i, j).
• Nếu m có tính chất (i,j)-Ramsey, thì mọi số n > m cũng có tính chất này;
• Nếu m không có tính chất (i,j)-Ramsey, thì mọi số n < m cũng không có tính chất này; • Nếu i  1 i2 thì R(i1,j)  R(i2,j). Toán rời rạc Toán rời rạc Fal 2006 Fal 2006 Các số Ramsey Các số Ramsey
• Việc xác định số Ramsey R(i,j) đòi hỏi chúng ta phải tìm số nguyên • R(3,3) = 6 (tìm được năm 1955)
dương nhỏ nhất có tính chất (i,j)-Ramsey. Liệu số này có tồn tại với
• R(4,4) = 18 (tìm được năm 1955)
mọi i  2, j  2 hay không? Định lý Ramsey cho ta khẳng định về sự
• R(4,5) = 25 (tìm được năm 1993)
tồn tại của các số này. • R(5,5) = ?
(mới xác nhận: 43 ≤ R(5,5) ≤ 49) ??
• Định lý Ramsey. Nếu i  2, j  2 là các số nguyên dương thì luôn tìm • R(6,6) =
Bài toán trở nên khó một cách bất ngờ khi đối số tăng!
được số nguyên dương với tính chất (i,j)-Ramsey (từ đó suy ra số R(i,j)
Chú ý: Có 2n(n-1)/2 cách tô màu cạnh của Kn. là tồn tại).
Khi n = 10, số này là > 1030; n=30, số này là >10135 Toán rời rạc Fal 2006 10