1 ỨNG DỤNG CỦA NGUYÊN LÝ DIRICHLET TRONG CÁC BÀI TOÁN TỔ HỢP, SỐ HỌC, HÌNH HỌC VÀ BẤT ĐẲNG THỨC TOÁN TRUNG HỌC CƠ SỞ CHỦ ĐỀ 1: CÁC BÀI TOÁN ỨNG DỤNG NGUYÊN LÝ DIRICHLET TRONG CÁC BÀI TOÁN TỔ HỢP, SỐ HỌC VÀ HÌNH HỌC I. Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle) hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật v|o ngăn kéo (The Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp. Nguyên lý Dirichlet cơ bản: 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 chứa ít nhất hai con thỏ. Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại N một hộp chứa ít nhất đồ vật.
(Ở đ}y x là số nguyên nhỏ nhất có giá trị nhỏ hơn k hoặc bằng x) Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m 2 cái chuồng thì tồn tại một n m 1 chuồng có ít nhất con thỏ. m Nguyên lí Dirichlet dạng tập hợp: Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc n|o đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A m| chúng tương ứng với một phần tử của B. Phƣơng pháp ứng dụng.
Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó l| một công cụ hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học. Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể hiện qua hệ thống bài tập sau: Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt ‚thỏ‛ v|o ‚chuồng‛ v| thoả mãn c{c điều kiện: + Số ‘thỏ‛ phải nhiều hơn số chuồng. + ‚Thỏ‛ phải được nhốt hết vào các ‚chuồng‛, nhưng không bắt buộc chuồng nào cũng phải có thỏ. Thường thì phương ph{p Dirichlet được áp dụng kèm theo phương ph{p phản chứng.
Ngoài ra nó còn có thể áp dụng với các nguyên lý khác. Một số ví dụ minh họa. Cho bảng ô vuông kích thước 10.10 gồm 100 ô vuông đơn vị. Điền v|o mỗi ô vuông của bảng n|y một số nguyên dương không vượt qu{ 10 sao cho hai số ở hai ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau.
Chứng minh rằng trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần. Lời giải Xét hình vuông cạnh 2x2 , do hình vuông n|y có mỗi hình vuông nhỏ luôn chung cạnh hoặc chung đỉnh nên tồn tại nhiều nhất 1 số chẵn, nhiều nhất 1 số chia hết cho 3 do đó có ít nhất 2 số lẻ không chia hết cho 3. Bảng 10x10 được chia th|nh 25 hình vuông có cạnh 2x2 nên có ít nhất 50 số lẻ không chia hết cho 3. Từ 1 đến 0 có 3 số lẻ không chia hết cho 3 là 1, 5, 7.
Áp dụng nguyên lí Dirichlet ta được một trong ba số trên xuất hiện ít 50 nhất 1 17 lần 3 3 Ví dụ 2. Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng. Chứng minh rằng với c{ch sơn m|u bất kì thì trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở 4 góc là các ô cùng màu. Lời giải Mẫu sơn m|u có thể xảy ra với bàn cờ này có dạng từ 1 đến 8.
Giả sử một trong số các cột thuộc dạng 1. Bài toán sẽ được chứng minh nếu tất cả các cột còn lại thuộc dạng 1, 2, 3 hoặc 4. Giả sử tất cả các cột còn lại thuộc dạng 5, 6, 7, 8 khi đó theo nguyên lí Dirichlet thì hai trong số sau cột có 2 cột cùng 1 dạng v| như vậy b|i to{n cũng được chứng minh Chứng minh ho|n to|n tương tự nếu 1 cột có dang 8. Giả sử không có cột nào trong các cột 1, 8 thì theo nguyên lí Dirichlet cũng có 2 cột cùng dạng v| b|i to{n cũng đựoc chứng minh Ví dụ 3.
Trong hình chữ nhật kích thước 1.2 ta lấy 6n 2 1 điểm với n là số nguyên dương. 1 Chứng minh rằng tồn tại 1 hình tròn có bán kính chứa không ít hơn 4 trong số c{c điểm n đã cho. Lời giải Chia các cạnh của hình chữ nhật th|nh n đoạn v| 2n đoạn bằng nhau ,mỗi đoạn có 1 độ dài. Nối c{c điểm chia bằng c{c đường thẳng song songvới các cạnh của hình chữ n 1 nhật ta được n.2n 2n2 hình vuông nhỏ với cạnh là.
Nếu mỗi hình vuông chứa không n qu{ 3 điểm thì tổng số điểm đã cho không qu{ 3. Do đó phải 1 tồn tại 1 hình vuông chứa không ít hơn 4 điểm. Rõ ràng hình vuông cạnh nội tiếp n 2 đường tròn bán kính là v| đường tròn n|y được chứa trong đường tròn đồng tâm bán 2n 1 kính. Cho bảng vuông gồm n.
Mỗi ô vuông ghi một trong các số 1; 0; 2. Chứng minh rằng không tìm được bảng vuông nào mà tổng các số trên cột, trên hàng, trên đường chéo là các số khác nhau. Lời giải Do trong các ô có thể nhận một trong ba số 0; 1; 2 nên có thể có trường hợp tất cả các ô của một hàng hoặc một cột hoặc một đường chéo nhận giá trị 0 hoặc nhận giá trị 2. Do đó tổng các số trên cột hoặc trên hàng hoặc trên đường chéo có giá trị nhỏ nhất là 0.n 0 và giá trị lớn nhất là 2.
Như vậy các tổng các số trên mỗi hàng, mỗi cột, mỗi đường chéo có thể nhận 2n 1 giá trị là 0;1; 2;.; 2n Do bảng ô vuông n.n nên sẽ có n hàng, n cột v| hai đường chéo. Do đó sẽ có 2n 2 tổng nhận một trong 2n 1 giá trị số nguyên từ 0 đến 2n. Theo nguyên tắc Dirichlet phải có ít nhất 2 tổng có giá trị bằng nhau. Điều n|y có nghĩa l| không tìm được bảng vuông nào mà tổng các số trên cột, trên h|ng, trên đường chéo là các số khác nhau.
Ở vòng chung kết cờ vua có 8 bạn tham gia. Hai bạn bất kỳ đều phải đấu với nhau một trận v| người n|o cũng phải gặp đủ 7 đấu thủ của mình. Chứng minh rằng trong mọi thời điểm của cuộc đấu, bao giờ cũng có hai đấu thủ đã đấu một số trận như nhau. Lời giải Giả sử số trận thi đấu của các bạn tham gia thi đấu cờ vua là a1 ; a 2 ;.
Do hai bạn thi đấu với nhau một trận nên ta có 0 ai 7, 1 i 8. Xét c{c trường hợp sau: Tính đến thời điểm đó có một bạn chưa đấu trận nào suy ra không có bạn n|o đấu đủ 7 trận. Khi đó 0 ai 6, 1 i 8 do đó tồn tại a k a m có nghĩa l| có hai đấu thủ đã đấu một số trận như nhau. Tính đến thời điểm đang xét, mỗi bạn đều đã đấu ít nhất một ván.
5 Khi đó ta có 0 ai 7, 1 i 8 , do đó tồn tại a k a m có nghĩa l| có hai đấu thủ đã đấu một số trận như nhau. Vậy b|i to{n được chứng minh. Cho 40 số nguyên dương a1 ,a 2 ,., b21 thoả mãn hai điều kiện: 1 a1 a 2 . b21 200 Chứng minh rằng tồn tại bốn số a i ;a j ;bk ;bp với 1 i, j 19;1 k,p 21 thỏa mãn a i a j ; bk bp a j a i bp bk Lời giải Xét các tổng có dạng a m bn với a m a1 ; a 2 ;.
Do tập hợp a1 ; a 2 ;.; a19 có 19 phần tử và tập hợp b1 ; b2 ;.; b21 có 21 phần tử nên, nên ta có tất cả 19.21 399 tổng dạng a m bn như thế. Nên các tổng a m bn nhận các giá trị nguyên dương từ 2 đến 400. Đến đ}y ta xét c{c trường hợp sau: Nếu các tổng trên nhận đủ 399 giá trị từ 2 đến 400. Khi đó từ giả thiết cảu bài toán ta được a1 b1 2 a b1 1 1 a19 b21 400 a19 b21 200 a a19 ; b1 b21 Từ đó ta suy ra được 1 a19 a1 b21 b1 199 Nếu các tổng trên không nhận đủ 399 giá trị từ 2 đến 400.
Khi đó với 399 tổng thì theo nguyên lí Dirichlet sẽ tồn tại hai tổng có giá trị bằng nhau. 6 a i a j ; bk bp Không mất tính tổng quát ta giả sử hai tổng đó l| a j bk bp a i a i a j ; bk bp Từ đó suy ra a j a i bp bk Vậy b|i to{n được chứng minh. Trong một cuộc tranh giải vô địch quốc gia về bóng đ{ có 20 đội tham gia. Số nhỏ nhất các trận đấu l| bao nhiêu để trong 3 đội bất kỳ luôn tìm được 2 đội đã chơi với nhau.
Lời giải Ta chia 20 đội thành 2 nhóm, mỗi nhóm 10 đội và chỉ c{c đội trong cùng1 nhóm mới thi đấu với nhau. Rõ ràng cách sắp xếp này thoả mãn c{c điều kiện của bài toán và tất cả có 90 trận đấu. Ta chứng minh rằng nếu c{c điều kiện của bài toán thoả mãn thì số trận đấu sẽ lớn hơn hoặc bằng 90. Giả sử ngược lại ta tìm đội một A đấu số trận k 8.
Ta ký hiệu c{c đội đã đấu với A l| X. C{c đội không đấu với A l| Y, khi đó X k; Y 19 k. Dĩ nhiên c{c đội trong Y sẽ đấu với nhau nếu không hai đội thuộc Y và A sẽ l| 3 đội m| không có đội n|o chơi với nhau. Giả sử trong X có P cặp không chơi với nhau.
Do đó mỗi đội Y phải đấu với mỗi đội trong P cặp đó của X và mỗi đội trong X có mặt không quá k 1 cặp trong số P cặp (X có 19 k tất cả k đội).