Chương 1 Bài toán tồn tại 1.1 Giới thiệu bài toán 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 thoả mãn các tính chất cho trước là hết sức khó khăn. Bài toán về bẩy cây cầu của nhà toán học Euler vào thể kỉ XVIII đã khiến người dân thành phố Konigsberg và các nhà toán học thời bấy giờ mất bao công tìm kiếm lời giải. Hay đơn giản hơn, khi một kì thủ cần phải tính toán các nước đi của mình để giải đáp xem liệu có khả năng thắng hay không, hoặc là một người giải mật mã cần tìm chìa khoá giải cho một bức mật mã mà anh ta không biết liệu đây có đúng là bức điện thật được mã hoá của đối phương hay không, hay chỉ là bức mật mã giả của đối phương tung ra nhằm đảm bảo an toàn cho bức điện thật. Như vậy, trong tổ hợp xuất hiện một vấn đề 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.
Các bài toán thuộc dạng này được gọi là các bài toán tồn tại tổ hợp. Một bài toán tồn tại tổ hợp xem như giải xong nếu 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 tồn tại. Tuy nhiên, cả hai khả năng đều không phải dễ. Để thấy rõ được sự phức tạp của vấn đề, dưới đây xin được xét một số bài toán tồn tại cổ điển nổi tiếng.
a, Bài toán về bẩy cây cầu của Euler Thành phố Konigsberg thuộc Thổ (bây giờ gọi là Kaliningrad thuộc cộng hoà Nga), được chia thành bốn vùng bằng các nhánh sông Pregel. Các vùng này gồm hai vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa hai nhánh sông Pregel. Vào thế kỉ XVIII, người ta xây bẩy chiếc cầu nối các vùng này với nhau. Hình 1, vẽ các vùng và các cầu qua sông của LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 thành phố.
Vào chủ nhật người dân ở đây thường đi bộ dọc theo các phố. Họ tự hỏi không biết có thể xuất phát tại một điểm nào đó trong thành phố đi qua tất cả các cầu, mỗi chiếc cầu đúng một lần, rồi trở về điểm xuất phát được không. Nhà toán học Thụy Sĩ, Leonhard Euler, đã giải bài toán này. Lời giải của ông công bố năm 1736 có thể là một ứng dụng đầu tiên của lý thuyết đồ thị.
Ông đã chứng minh được rằng không có được đường đi nào thoả mãn yêu cầu bài toán (lời giải chi tiết của bài xin được trình bày rõ ở chương IV) b, Bài toán bốn màu Có những bài toán mà nội dung của nó có thể giải thích cho bất kì ai, tuy lời giải của nó thì ai cũng có thể tự tìm nhưng mà khó có thể tìm được. Ngoài định lý Fermat thì bài toán bốn màu là một trong những bài toán như vậy. Bài toán có thể phát biểu trực quan như sau: Chứng minh rằng mọi bản đồ trên mặt phẳng đều có thể tô bằng bốn màu sao cho không có hai nước láng giềng nào được tô bởi cùng một màu. Chú ý rằng ta xem mỗi nước là một vùng liên thông và hai nước gọi là láng giềng nếu chúng có chung biên giới là một đường liên tục.
Con số 4 không phải là ngẫu nhiên, người ta đã chứng minh được rằng mọi bản đồ đều được tô với số màu lớn hơn 4, còn với số màu ít hơn 4 thì không tô được, chẳng hạn bản đồ gồm bốn nước ở hình dưới đây không thể tô được với số màu ít hơn 4. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Bài toán này xuất hiện vào khoảng những năm 1850 - 1852 từ một nhà buôn người Anh là Gazri, khi tô bản đồ hành chính nước Anh đã cố gắng chứng minh rằng có thể tô bằng 4 màu. Sau đó, năm 1952, ông đã viết thư cho De Morgan để thông báo về giả thuyết này. Năm 1878, Keli trong một bài báo đăng ở tuyển tập các công trình của Hội toán học Anh có hỏi rằng bài toán này đã được giải quyết hay chưa? Từ đó bài toán này trở thành nổi tiếng và trong hơn một thế kỉ, có rất nhiều người làm toán nghiệp dư cũng như chuyên nghiệp đã cố gắng chứng minh giả thuyết này.
Tuy nhiên, mãi đến năm 1976 hai nhà toán học Mỹ là K.Haken mới chứng minh được giả thuyết này bằng máy tính điện tử. c, Bài toán chọn 2n điểm trên lưới n × n điểm Chọn một lưới ô vuông gồm n × n điểm. Hỏi có thể chọn trong số chúng 2n điểm sao cho không có ba điểm được chọn nào thẳng hàng hay không? hiện nay người ta biết lời giải của bài này khi n 6 15. Hình dưới đây cho một lời giải bài toán với n = 12.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Các phương pháp chứng minh sự tồn tại 1.1 Phương pháp chứng minh phản chứng Phương pháp chứng minh phản chứng có lẽ là một trong những phương pháp chứng minh sớm nhất mà loài người đã biết đến, đặc biệt trong nghệ thuật diễn thuyết và tranh luận. Trong toán học, phương pháp chứng minh phản chứng thường được sử dụng, đặc biệt khi cần chứng minh tính duy nhất của một đối tượng T nào đó thoả mãn điều kiện cho trước (mà sự tồn tại của T đã được chứng minh trước đó) ta thường giả sử còn ∀T 0 6= T ; T 0 cũng thoả mãn điều kiện đó, từ đó suy ra một điều vô lý. Vậy điều giả sử của chúng ta là sai, tức là T duy nhất. a, Cơ sở lý thuyết Giả sử ta phải chứng minh một mệnh đề có dạng P =⇒ Q với P là giả thiết, Q là kết luận.
Ta tiến hành như sau: Bước 1: Giả sử Q sai. Bước 2: Từ giả sử Q sai và từ P ta dùng các lập luận, suy diễn để dẫn đến một điều vô lý. Bước 3: Từ đó ta suy ra Q đúng. Ta có thể dùng phương pháp chứng minh phản chứng để chứng minh nguyên lý Diriclet.
Do đó, với nhiều bài toán ta có thể chứng minh bằng nguyên lý Diriclet hoặc phương pháp chứng minh phản chứng. b, Phương pháp giải toán qua các ví dụ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Một lớp học có 43 em, gồm các em họ Nguyễn, họ Phạm, họ Trần. Chứng minh rằng lớp có ít nhất 19 em họ Nguyễn hoặc ít nhất 14 em họ Phạm hoặc ít nhất 12 em họ Trần.
Giả sử ngược lại, số em họ Nguyễn, họ Phạm, họ Trần tương ứng không lớn hơn 18; 13; 11. Khi đó số học sinh của lớp không lớn hơn 42. Điều này vô lý vì số học sinh của lớp là 43. Từ đó ta suy ra điều cần chứng minh.
Cho tâp hợp A = {0; 1; 2; 3; 4; 5; 6; 7; 8; 9}. Chứng minh rằng với mỗi tập con B gồm 5 phần tử của tập A thì trong các tổng x + y với x, y khác nhau thuộc B , luôn tồn tại ít nhất hai tổng có chữ số hàng đơn vị như nhau. Với mỗi tập B = {a1 ; a2 ; a3 ; a4 ; a5 } ⊂ A ta có tất cả 10 tổng: a1 +a2 ; a1 +a3 ; a1 +a4 ; a1 +a5 ; a2 +a3 ; a2 +a4 ; a2 +a5 ; a3 +a4 ; a3 +a5 ; a4 +a5. Giả sử chữ số hàng đơn vị của 10 tổng trên đôi một khác nhau, khi đó tổng tất cả các chữ số hàng đơn vị của chúng là: 0+1+2+3+4+5+6+7+8+9 = 45.
Do đó, tổng S của 10 tổng trên là một số lẻ.(1) Ta lại có: S = (a1 + a2 ) + (a1 + a3 ) + (a1 + a4 ) + (a1 + a5 ) + (a2 + a3 ) + (a2 + a4 ) + (a2 +a5 )+(a3 +a4 )+(a3 +a5 )+(a4 +a5 ) = 4(a1 +a2 +a3 +a4 +a5 ) =⇒ S là số chẵn.(2) Ta thấy (1) và (2) mâu thuẫn, nên điều giả sử trên là sai. Từ đó ta có điều phải chứng minh. Cho 441 số nguyên dương a1 ; a2 ;. + √ = 41 a1 a2 a441 Chứng minh rằng trong 441 số đã cho có ít nhất 2 số bằng nhau.
Giả sử 441 số đã cho không có hai số nào bằng nhau, không mất tính tổng quát, giả sử: 1 6 a1 < a2 < .; √ 6√ a1 a2 2 a441 441 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Ta chứng minh bổ đề sau: Với mọi số nguyên dương n ta có: 1 √ √ √ <2 n− n−1 (1) n Thật vậy, 1 n−n+1 (1) ⇔ √ < 2. + √ <1 + 2 2 − 1 + ··· + 441 − 440 a1 a2 a441 =41 Điều này trái với giả thiết. Do đó tồn tại ít nhất hai số bằng nhau. Chứng minh rằng trong 2007 số khác nhau tuỳ ý được lấy từ tập hợp A = 1; 2; 3; .; 20062007 có ít nhất hai số x; y thoả mãn: √ √ 0 < 2007 x − 2007 y < 1 [(THPT Chuyên Hà Nội - Amsterdam 2006-2007) Lời giải.
Gọi 2007 số đã chọn là: 1 6 a1 < a2 < a3 <. < a2007 6 20062007 Ta xét 2006 số sau: √ √ √ √ √ √ b1 = 2007 a2 − 2007 a1 ; b2 = 2007 a3 − 2007 a2 ;. Giả sử không có số bi (i = 1; 2; .; 2006) nào đó nhỏ hơn 1, suy ra: b1 ; b2 ;. + 2007 a2007 − 2007 a2006 √ √ = 2007 a2007 − 2007 a1 (2) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Từ (1) và (2) suy ra: √ √ a2007 − 2007 a1 > 2006 2007 √ √ ⇔ 2007 a2007 > 2006 + 2007 a1 > 2006 ⇔a2007 > 20062007 (trái với giả thiết) Vậy điều giả sử trên là sai.
Từ đó ta có điều phải chứng minh. Cho 7 đoạn thẳng có độ dài lớn hơn 10 và nhỏ hơn 100. Chứng minh rằng luôn tìm được ba đoạn thẳng để có thể ghép thành một tam giác Lời giải. Chú ý rằng điều kiện cần và đủ để ba đoạn thẳng có thể ghép thành một tam giác là tổng độ dài của hai đoạn nhỏ phải lớn hơn độ dài của đoạn lớn.
Ta sắp xếp các đoạn đã cho theo thứ tự tăng dần của độ dài a1 ; a2 ; .; a7 và chứng minh rằng trong dãy đã xếp luôn tìm được ba đoạn liên tiếp sao cho tổng của hai đoạn đầu lớn hơn đoạn cuối.