Tài liệu Các bài toán cơ bản của lý thuyết tổ hợp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ Lê Thị Thanh Tâm CÁC BÀI TOÁN CƠ BẢN CỦA LÝ THUYẾT TỔ HỢP Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.0113 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học TS. Phạm Văn Thạo HÀ NỘI- 2014 1 Mục lục Mở đầu 1 4 Bài toán tồn tại 1.1 Giới thiệu bài toán . . . . . . . . . . . . . . 1.2 Các phương pháp chứng minh sự tồn tại . . . 1.2.1 Phương pháp chứng minh phản chứng 1.2.2 Nguyên lý Diriclet . . . . . . . . . . . 2 Bài toán liệt kê 2.1 Giới thiệu bài toán . . . . . . . . . . . 2.2 Thuật toán và độ phức tạp tính toán . . 2.2.1 Khái niệm thuật toán . . . . . . 2.2.2 Mô tả thuật toán bằng ngôn ngữ 2.2.3 Độ phức tạp của thuật toán . . 2.3 Phương pháp sinh . . . . . . . . . . . . 2.4 Thuật toán quay lui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . phỏng PASCAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 . 6 . 9 . 9 . 16 . . . . . . . . . . . . . . 39 39 40 40 41 43 45 48 . . . . . . . . 52 52 52 52 65 68 70 75 75 3 Bài toán đếm 3.1 Các bài toán đếm cơ bản . . . . . . . . . . . . . . . . . . 3.1.1 Giới thiệu bài toán . . . . . . . . . . . . . . . . . 3.1.2 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . 3.1.3 Tam giác Pascal và nhị thức Newton . . . . . . . . 3.1.4 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . 3.1.5 Hệ thức truy hồi . . . . . . . . . . . . . . . . . . . 3.2 Phân loại các bài toán đếm . . . . . . . . . . . . . . . . . 3.2.1 Bài toán đếm có sử dụng hai quy tắc đếm cơ bản . 3.2.2 Bài toán đếm các số tự nhiên thỏa mãn điều kiện cho trước . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Phương trình, hệ phương trình, bất phương trình và đẳng thức chứa công thức tổ hợp . . . . . . . . . . 3.2.4 Bài toán đếm các đối tượng hình học . . . . . . . 3.2.5 Bài toán phân chia (hoặc lấy ra) các đồ vật vào (hoặc ra khỏi) các hộp . . . . . . . . . . . . . . . . . . . . 77 . 80 . 83 . 84 2 3.2.6 3.2.7 3.2.8 3.2.9 Hệ số ak của xk trong khai triển Newton . . . Bài tập nguyên lý bù trừ . . . . . . . . . . . Bài tập hệ thức truy hồi . . . . . . . . . . . Đẳng thức phương trình liên quan đến khai Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . triển . . . 4 Bài toán tối ưu 4.1 Giới thiệu bài toán . . . . . . . . . . . . . . . . . . . . 4.2 Bài toán tối ưu trong đồ thị . . . . . . . . . . . . . . . 4.2.1 Các khái niệm cơ bản của lý thuyết đồ thị . . . . 4.2.2 Biểu diễn đồ thị bằng ma trận . . . . . . . . . . 4.2.3 Bài toán tìm cây bao trùm có trọng số nhỏ nhất 4.2.4 Bài toán tìm đường đi có trọng số nhỏ nhất . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 . 90 . 91 . 96 108 . 108 . 108 . 108 . 117 . 120 . 126 . 130 . 131 3 Lời cảm ơn Tác giả xin chân thành cảm ơn tập thể cán bộ, giảng viên trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện và giúp đỡ tác giả trong suốt quá trình học tập và hoàn thành luận văn tốt nghiệp. Tác giả xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến TS. Phạm Văn Thạo. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tác giả trong suốt quá trình tôi thực hiện đề tài. Tác giả cũng xin chân thành cảm ơn Lãnh đạo và các đồng nghiệp trường THPT Chuyên Ngoại Ngữ - Đại học Ngoại Ngữ - ĐHQGHN đã tạo điều kiện thuận lợi và giúp đỡ tác giả trong suốt quá trình học tập và thực hiện luận văn này. Tác giả xin cảm ơn các bạn đồng khóa, gia đình và bạn bè đã quan tâm giúp đỡ, động viên, tạo mọi điều kiện thuận lợi cho tác giả trong suốt quá trình học tập và hoàn thành luận văn. Mặc dù đã có rất nhiều cố gắng, song luận văn này không thể tránh khỏi những thiếu sót, tác giả rất mong nhận được những ý kiến chỉ dẫn, đóng góp của thầy cô và các bạn. Trân trọng! Hà Nội, tháng 08 năm 2014 Học viên Lê Thị Thanh Tâm 4 Mở đầu Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lý thú của Toán học nói chung và Toán học rời rạc nói riêng. Tư duy về tổ hợp đã xuất hiện từ rất sớm trong lịch sử phát triển của nhân loại và đến thế kỉ thứ 17 nó được hình thành như một ngành toán học bằng một loạt các công trình nổi tiếng của các nhà toán học như Pascal, Fermat, Lenibniz, Euler,... Kể từ sau khi tin học ra đời, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ, có nội dung phong phú và được ứng dụng nhiều trong thực tế đời sống. Trong toán học sơ cấp, tổ hợp cũng xuất hiện với nhiều bài toán hay với độ khó cao. Những ai mới bắt đầu làm quen với khái niệm tổ hợp thường khó hình dung hết độ phức tạp về về cấu trúc trên các tập đặc biệt. Do vậy tôi đã chọn đề tài "bài toán cơ bản của lý thuyết tổ hợp". Luận văn đã trình bày bốn bài toán cơ bản của lý thuyết tổ hợp, xây dựng một số bài toán áp dụng. Luận văn gồm phần mở đầu, bốn chương, kết luận và danh mục tài liệu tham khảo. Chương 1: Bài toán tồn tại. Trong chương này tác giả đã giới thiệu bài toán tồn tại bằng ba bài toán cổ nổi tiếng là bài toán về bẩy cây cầu của Euler, bài toán bốn màu và bài toán chọn 2n điểm trên lưới n.n điểm. Trong chương này tác giả cũng nêu được hai phương pháp chứng minh sự tồn tại là phương pháp chứng minh bằng phản chứng và phương pháp sử dụng nguyên lý Diriclet. Chương 2: Bài toán liệt kê. Chương 2 được trình bày theo bốn mục bao gồm: giới thiệu bài toán, thuật toán và độ phức tạp tính toán cùng với phương pháp sinh và thuật toán quay lui. Chương 3: Bài toán đếm. Đây là nội dung chính của luận văn. Trong chương này tác giả đã nêu được các bài toán đếm cơ bản, phân loại các 5 bài toán đếm theo từng dạng bài tập cụ thể. Trong mỗi dạng tác giả đều có ví dụ minh họa cũng như bài tập tự luyện. Chương 4: Bài toán tối ưu. Trong chương này tác giả đã giới thiệu bài toán, nhắc lại các khái niệm cơ bản của lý thuyết đồ thị, biểu diễn đồ thị bằng ma trận và trình bày hai bài toán cơ bản là: Bài toán tìm cây bao trùm có trọng số nhỏ nhất và bài toán tìm đường đi có trọng số nhỏ nhất. Mặc dù bản thân đã rất cố gắng và nghiêm túc trong học tập và nghiên cứu khoa học nhưng do thời gian có hạn, kiến thức bản thân còn hạn chế nên trong quá trình thực hiện luận văn không tránh khỏi những sơ suất. Rất mong nhận được sự góp ý của thầy cô và các bạn. Tôi xin chân thành cảm ơn. 6 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 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. 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.Appel và W.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. 9 1.2 1.2.1 Các phương pháp chứng minh sự tồn tại 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. Chú ý 1.1. 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ụ 10 Ví dụ 1.1. 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. Lời giải. 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. Ví dụ 1.2. 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. (THPT Chuyên Lam Sơn - Thanh Hoá 2011-2012) Lời giải. 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. Ví dụ 1.3. Cho 441 số nguyên dương a1 ; a2 ; ...; a441 thoả mãn: 1 1 1 = 41 √ + √ + ... + √ a1 a2 a441 Chứng minh rằng trong 441 số đã cho có ít nhất 2 số bằng nhau. Lời giải. 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 < ... < a441 . Do đó: 1 1 1 1 1 6√ √ 6 1; √ 6 √ ; ...; √ a1 a2 a441 2 441 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. √ n n+ n−1 √ √ √ ⇔ n+ n−1<2 n √ √ ⇔ n − 1 < n (lunØng) Do đó, h√ √ √  √ i 1 1 1 <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. Ví dụ 1.4. 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 ; ...; b2006 = √ 2007 a2007 − √ 2007 a2006 Ta có: b1 ; b2 ; ...; b2006 > 0. Giả sử không có số bi (i = 1; 2; ...; 2006) nào đó nhỏ hơn 1, suy ra: b1 ; b2 ; ...; b2006 > 1. Do đó, b1 + b2 + ... + b2006 > 1 + 1 + ... + 1 = 2006 (1) √ √ √ b1 + b2 + ... + b2006 = 2007 a2 − 2007 a1 + ... + 2007 a2007 − √ √ = 2007 a2007 − 2007 a1 (2) √ 2007 a2006 12 Từ (1) và (2) suy ra: √ 2007 a2007 − √ ⇔ 2007 a2007 √ a1 > 2006 √ > 2006 + 2007 a1 > 2006 2007 ⇔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. Ví dụ 1.5. 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. Giả thiết điều này không xảy ra, tức là đồng thời xảy ra các bất đẳng thức: a1 + a2 6 a3 ; a2 + a3 6 a4 ; a3 + a4 6 a5 ; a4 + a5 6 a6 ; a5 + a6 6 a7 Từ giả thiết a1 ; a2 có giá trị lớn hơn 10 ta nhận được a3 > 20. Từ a2 > 10 và a3 > 10 ta nhận được a4 > 30; a5 > 50; a6 > 80; a7 > 130. Bất đẳng thức cuối cùng mâu thuẫn với giả thiết các độ dài nhỏ hơn 100. Từ đó chứng minh kết luận của bài toán. Ví dụ 1.6. Các đỉnh của một thập giác đều được đánh số bởi các số nguyên 0; 1; 2; 3; 4; 5; 6; 7; 8; 9 một cách tuỳ ý. Chứng minh rằng luôn tìm được ba đỉnh liên tiếp có tổng các số lớn hơn 13. Lời giải. Gọi x1 ; x2 ; ...; x10 là các số gán cho các đỉnh của 1; 2; ...; 10 của thập giác. Giả sử ngược lại là không tìm được ba đỉnh nào thoả mãn đề bài. Khi đó ta có: k1 = x1 + x2 + x3 6 13 k2 = x2 + x3 + x4 6 13 ..... 13 k9 = x9 + x10 + x1 6 13 k10 = x10 + x1 + x2 6 13 Từ đó suy ra:k1 + k2 + ... + k10 6 130. Mặt khác do: k1 + k2 + ... + k10 =3(x1 + x2 + ... + x10 ) =3(0 + 1 + 2 + ... + 9) = 135 Từ đó ta có: 135 = k1 + k2 + ... + k10 6 130(Vô lý) Vậy giả sử trên là sai. Từ đó ta có điều cần chứng minh. Chú ý 1.2. Bài toán có nhiều cách phát biểu khác nhau và có thể phát biểu dạng tổng quát hơn. Chẳng hạn ta có bài toán sau: Một đội bóng có 21 cầu thủ gồm cả chính thức và dự bị mang các áo từ 4 đến 24. Mỗi cầu thủ mang một số áo khác nhau. Họ đứng một cách tuỳ ý thành một vòng tròn. Chứng minh rằng luôn tồn tại 4 cầu thủ đứng cạnh nhau mà tổng các số trên áo của họ không nhỏ hơn 52. Ví dụ 1.7. Cho đa giác lồi n cạnh (n > 4) trong đó tất cả các đường chéo bằng nhau. Tìm giá trị lớn nhất của n. (Vòng 2, THPT Chuyên Hà Tây, 2008 - 2009) Lời giải. Với n = 4 ta có hình vuông có hai đường chéo bằng nhau. Với n = 5 ta có ngũ giác đều có các đường chéo bằng nhau. Với n > 6, giả sử đa giác A1 A2 ...An có tất cả các đường chéo bằng nhau, khi đó ta đặt: A1 A4 = A1 A5 = A2 A4 = a với a là độ dài của các đường chéo. Gọi I là giao điểm của A1 A4 và A2 A5 . Ta có: IA1 + IA5 > A1 A5 ; IA2 + IA4 > A2 A4 . Do đó: (IA1 + IA4 ) + (IA2 + IA5 ) > A1 A5 + A2 A4 ⇔A1 A4 + A2 A5 > 2a(Vô lý) Vậy n 6 5. Do đó n đạt giá trị lớn nhất bằng 5. Ví dụ 1.8. Trên mặt phẳng xOy, A(x; y) được gọi là điểm nguyên nếu x; y ∈ Z. Giả sử A1 A2 ...An là n- giác lồi có tất cả các đỉnh là điểm nguyên. Biết rằng miền đa giác đó (bao gồm các điểm thuộc miền trong và thuộc 14 cạnh) không chứa bất kì điểm nguyên nào ngoài các đỉnh. Chứng minh rằng n 6 4. (Vòng 2, THPT Chuyên ĐHSP Hà Nội 1994 - 1995)] Lời giải. Giả sử n > 5, toạ độ các đỉnh có các dạng: (chẵn; chẵn); (chẵn; lẻ);(lẻ; chẵn);(lẻ; lẻ). Do đó tồn tại hai đỉnh có toạ độ cùng dạng trên, nên trung điểm của hai đỉnh đó có toạ độ nguyên, trái với giả thiết. Vậy n 6 4. Ví dụ 1.9. Bên trong đường tròn tâm O bán kính 1 cho M ABC có diện tích > 1. Chứng minh rằng điểm O nằm trong hoặc nằm trên cạnh của M ABC . (THPT Chuyên Phan Bội Châu - Nghệ An - 2009- 2010) Lời giải. Giả sử O nằm ngoài M ABC . Trước hết ta chứng minh:"Nếu O nằm ngoài M ABC thì có đường thẳng chứa cạnh tam giác mà O và đỉnh còn lại của tam giác nằm khác phía nhau đối với đường thẳng này".(*) Giả sử (*) sai. Do đó, O và A nằm cùng nửa mặt phẳng với bờ là đường thẳng BC nên O không thuộc miền (III). Tương tự O không thuộc miền (I) và (II). Vì vậy, O thuộc miền trong hoặc trên các cạnh của M ABC . Điều này là mâu thuẫn với điều kiện ban đầu là O nằm ngoài M ABC nên điều giả sử là sai. Vậy (*) đúng. Không mất tính tổng quát ta giả sử O và A nằm ở hai nửa mặt phẳng khác nhau với bờ là đường thẳng chứa cạnh BC . Suy ra đoạn OA cắt BC tại K . Vẽ AH ⊥ BC tại H . suy ra: AH 6 AK < OA < 1 hay AH < 1. Khi đó : 1 1 1 SMABC = AH.BC < AH.2 < .1.2 = 1 2 2 2 Điều này mâu thuẫn với giả thiết nên điều giả sử là sai. Ta có điều phải chứng minh. 15 Ví dụ 1.10. Chứng minh rằng một tam giác có hai đường phân giác bằng nhau thì tam giác đó là tam giác cân. Lời giải. Cho M ABC có hai đường phân giác AM ; BN bằng nhau. Ta chứng minh M ABC cân tại C . \ > BCA \ ⇔ Giả sử M ABC không cân tại C với BC < AC hay ABC c1 > A c1 . B c1 > A c1 nên AN > Xét M ABN và M BAM có: BN = AM ; AB chung; B BM . Dựng hình bình hành AM DN ta có: M D = AN > BM nên trong c3 > D c2 . Mặt khác: B c2 > A c2 = D c1 nên ta có: N \ M M BD ta có: B BD > \ . Do đó, N D > N B hay AM > N B (vô lý). BDN Vậy giả sử trên là sai hay M ABC cân tại C . 16 1.2.2 Nguyên lý Diriclet Nguyên lý Diriclet là phương pháp chứng minh sự tồn tại mà học sinh được làm quen từ rất sớm (từ bậc tiểu học) và là một trong những phương pháp thể hiện rõ cái đẹp của Toán học, làm cho học sinh thêm yêu thích môn Toán. Lập luận của phương pháp Diriclet thường được sử dụng trong các bài toán cho học sinh giỏi và dùng để chứng minh sự tồn tại một khả năng nào đó mà không cần chỉ rõ khả năng đó tồn tại khi nào, ở đâu và có bao nhiêu khả năng như vậy tồn tại. Phương pháp chứng minh như vậy còn được gọi là phương pháp chứng minh không kiến thiết. a, Cơ sở lý thuyết Nguyên lý Diriclet được phát biểu đầu tiên bởi nhà toán học người Đức Peter Gustav Lejeune Diriclet (1805 − 1859). Nguyên lý Diriclet (hay còn được gọi là nguyên lý chuồng thỏ). Nếu nhốt n + 1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng nhốt ít nhất hai con thỏ. Nguyên lý Diriclet tổng quát: Nếu nhốt n con thỏ vào k chuồng + Nếu n chia hết cho k thì tồn tại ít nhất một chuồng chứa không ít hơn n k con thỏ. + Nếu n không chia hết cho k thì tồn tại ít nhất một chuồng chứa không 17   ít hơn nk + 1 con thỏ. Dùng nguyên lý Diriclet ta chứng minh được nhiều kết quả hết sức sâu sắc của Toán học. Với nguyên lý này ta dễ dàng chứng minh sự tồn tại mà không đưa ra phương pháp tìm cấu hình, nhưng trong thực tế nhiều bài toán ta chỉ cần chỉ ra sự tồn tại là đã đủ rồi! b, Phương pháp giải toán qua các ví dụ Ví dụ 1.11. Chứng minh rằng trong 100 người có ít nhất 9 người sinh cùng một tháng. Lời giải. Xếp những người sinh cùng một tháng vào một nhóm, có 12   nhóm. Theo nguyên lý Diriclet tồn tại một nhóm có ít nhất 100 12 + 1 = 8 + 1 = 9(người). Ví dụ 1.12. Một hội nghị có 52 đại biểu được ngồi vào 10 dãy nghế. Chứng minh rằng tồn tại một dãy ghế có số đại biểu ngồi lớn hơn hoặc bằng 6. Lời giải. Theo nguyên lý Diriclet, tồn tại một dãy ghế có số đại biểu ngồi  52  lớn hơn hoặc bằng 10 +1=6 Ví dụ 1.13. Có 5 loại học bổng khác nhau. Hỏi phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít nhất là 6 người cùng nhận học bổng như nhau. Lời giải. Số sinh viên ít nhất cần có để đảm bảo chắc chắn có 6 sinh viên cùng nhận học bổng như nhau là số nguyên nhỏ nhất n sao cho n5 > 5. Dễ thấy rằng n = 26 thỏa mãn đề bài. Ví dụ 1.14. Một nhóm 6 người đôi một thân nhau hoặc ghét nhau. Chứng minh rằng trong nhóm có 3 người hoặc cùng thân nhau hoặc cùng ghét nhau. Lời giải. Giả sử 6 người trong nhóm là A; B; C; D; E; F . A có quan hệ thân hoặc ghét với 5 người còn lại. Theo nguyên lý Diriclet, tồn tại ít nhất 3 người cùng thân hoặc cùng ghét A. Giả sử B; C; E cùng thân A. Nếu B; C; E có ít nhất một cặp thân nhau thì cùng với A tạo thành bộ ba người đôi một thân nhau. Nếu B; C; E không có cặp nào thân nhau thì ta có nhóm ba người đôi một 18 ghét nhau. Chú ý rằng ví dụ trên còn được phát biểu theo cách khác như sau: " 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". Ví dụ 1.15. Chứng minh rằng trong n + 1 số nguyên dương không vượt quá 2n, luôn tồn tại hai số sao cho số này chia hết cho số kia. Lời giải. Giả sử có n + 1 số nguyên dương a1 ; a2 ; ...; an+1 . Số nguyên dương ai có dạng ai = 2ki .qi với ki ∈ N; qi là số nguyên lẻ nhỏ hơn 2n. Do chỉ có n số nguyên dương lẻ nhỏ hơn 2n nên theo nguyên lý Diriclet, tồn tại hai số bằng nhau: qi = qj = q . Khi đó, ai = 2ki .q và aj = 2kj .q . Giả sử ki 6 kj thì aj chia hết cho ai . Ví dụ 1.16. Trong một tháng có 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất một trận và cả tháng thi đấu không quá 45 trận. Chứng minh rằng tồn tại một số ngày liên tục đội bóng đó thi đấu đúng 14 trận. Lời giải. Gọi ai là tổng số trận mà đội đã thi đấu liên tục từ đầu tháng đến ngày thứ i. Khi đó, 1 6 a1 < a2 < ... < a30 6 45 và 15 6 a1 + 14 < a2 + 14 < ... < a30 + 14 6 59 Các số a1 ; a2 ; ...; a30 đôi một khác nhau nên các số a1 +14; a2 +14; ...; a30 + 14 đôi một khác nhau. 60 số nguyên dương a1 ; a2 ; ...; a30 ; a1 + 14; a2 + 14; ...; a30 + 14 chỉ nhận không quá 59 giá trị nên tồn tại ai ; aj sao cho: aj = ai + 14. Nghĩa là từ ngày thứ i + 1 đến ngày thứ j đội thi đấu đúng 14 trận. Ví dụ 1.17. Cho 5 số nguyên dương đôi một khác nhau sao cho mỗi số không có ước nguyên tố nào khác 2 và 3. Chứng minh rằng trong 5 số đó tồn tại hai số mà tích của chúng là một số chính phương. (Vòng 2, THPT Chuyên ĐHSP Hà Nội 2012 - 2013) 19 Lời giải. Gọi các số đã cho là a1 ; a2 ; ...; a5 với ai = 2xi .3yi (xi ; yi ∈ N). Năm cặp số (x1 ; y1 ); ...; (x5 ; y5 ) mà mỗi cặp số thuộc một trong bốn dạng: (chẵn; chẵn); (chẵn; lẻ); (lẻ; chẵn); (lẻ; lẻ). Do đó tồn tại hai cặp số cùng dạng. Giả sử (x1 ; y1 ); (x2 ; y2 ) là hai cặp số cùng dạng. Khi đó, x1 + x2 và y1 + y2 đều là số chẵn nên a1 .a2 = 2x1 +x2 .3y1 +y2 ⇒ a1 .a2 là số chính phương. Ví dụ 1.18. Cho 53 số nguyên dương phân biệt có tổng không lớn hơn 2004. Chứng minh rằng luôn tìm được 6 số trong 53 số đã cho thoả mãn điều kiện: 6 số này chia được thành 3 cặp số mà mỗi cặp số đều có tổng bằng 53. (HSG lớp 9 - TP Hà Nội 2004 - 2005) Lời giải. Giả sử 53 số đã cho có nhiều nhất 28 số nhỏ hơn 53 thì tổng của 53 số này lớn hơn hoặc bằng: (1 + 2 + .. + 28) + (53 + 54 + ... + 77) = 2031 > 2004 (vô lý). Vậy trong 53 số đã cho có ít nhất 29 số nhỏ hơn 53. Chia 52 số nguyên dương nhỏ hơn 53 thành 26 cặp, mỗi cặp có tổng bằng 53 như sau: (1; 52); (2; 51); ...; (26; 27). Khi đó với ít nhất 29 số nhỏ hơn 53 ta luôn tìm được 3 cặp mà các phần tử của chúng thoả mãn đề bài. Ví dụ 1.19. Cho tập X gồm 700 số nguyên dương đôi một khác nhau, mỗi số không lớn hơn 2006. Chứng minh rằng trong tập X luôn tìm được hai phần tử x; y sao cho x − y thuộc tập E = {0; 6; 9} (Vòng 2, THPT Chuyên ĐHSP Hà Nội, 2006 - 2007) Lời giải. Sắp xếp các số đã cho theo thứ tự tăng: 1 6 a1 < a2 < ... < a700 (1) Xét các dãy a1 + 3; a2 + 3; ...; a700 + 3 (2) a1 + 9; a2 + 9; ...; a700 + 9 (3) và Ba dãy (1); (2); (3) có 2100 số và a700 + 9 6 2006 + 9 = 2015 nên các số đó nhận không quá 2015 giá trị. Các số cùng dãy khác nhau và ai ; ai +3; ai +9 cũng đôi một khác nhau nên theo nguyên lý Diriclet ta có ai = aj + 3 hoặc