Một số ứng dụng nguyên lý Dirichlet

Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 MỘT SỐ ỨNG DỤNG NGUYÊN LÝ DIRICHLET Nguyễn Đình Thanh Trường THPT Chuyên Lam Sơn, Thanh Hóa Tóm tắt nội dung Nguyên lý Dirichlet còn gọi là "nguyên tắc nhốt thỏ vào lồng", được phát biểu ở dạng đơn giản: "Nếu đem nhốt 3 con thỏ vào 2 chiếc lồng thì phải có một lồng nhốt không ít hơn 2 thỏ". Nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại có tác dụng rất lớn trong giải toán. Nhiều khi có những bài toán, người ta đã dùng rất nhiều phương pháp toán học để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lý Dirichlet mà bài toán trở nên dễ dàng giải quyết. 1 Nguyên lý Dirichlet Nguyên lý Dirichlet tổng quát được phát biểu như sau: Nếu đem nhốt m× n+ r (m, n, r là các số nguyên dương) con thỏ vào n chiếc lồng thì ít nhất cũng có một lồng nhốt không ít hơn m+ 1 con thỏ. Chứng minh (dùng phương pháp phản chứng): Giả sử ngược lại, mỗi lồng chứa không quá m con thỏ thì tổng số thỏ sẽ không quá m× n con. Mâu thuẫn với giả thiết là số thỏ bằng m× n+ r. Ưu điểm của nguyên lí Dirichlet là nó cho phép khẳng định được sự tồn tại của một đối tượng có tính chất nào đó mà không cần chỉ ra mô hình cụ thể của nó. 2 Ứng dụng nguyên lý Dirichlet vào giải toán 2.1 Ứng dụng nguyên lý Dirichlet vào giải toán về suy luận logic Ví dụ 2.1. Trong một thùng có đựng 105 quả táo, gồm 4 loại. Chứng minh rằng trong số táo ấy, bao giờ ta cũng có thể tìm được ít ra 27 quả táo cùng một loại táo nào đó. Lời giải. Trong bài này ta coi nhưquả táo đóng vai trò làthỏ, loại táo đóng vai trò làlồng, Vì: 105 = 26× 4 + 1, theo nguyên lý Dirichlettìm được một loại táo có ít nhất có 26 + 1 = 27 quả. Ví dụ 2.2. Trong 1 lớp học có 30 học sinh. Chứng tỏ rằng trong số học sinh ta sẽ tìm thấy 2 học sinh có tên bắt đầu bằng một chữ cái giống nhau. Lời giải. Bảng chữ cái Tiếng Việt gồm 29 chữ cái, trong lúc đó số học sinh lớn hơn, những 30 em. Ở đây, các chữ cái đóng vai trò các lồng, còn các bạn học sinh đóng vai trò các chú thỏ mà ta phải nhốt vào lồng,vì số thỏ lớn hơn số lồng nên ta sẽ tìm được ít nhất một 1 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 lồng nhốt nhiều hơn 1 chú thỏ, tức là tìm được ít nhất 2 học sinh có tên bắt đầu cùng một chữ cái. Ví dụ 2.3. Một lớp học có 30 học sinh. Khi viết chính tả, em A phạm 14 lỗi, các em khác phạm ít lỗi hơn. Chứng minh rằng có ít nhất là 3 học sinh không mắc lỗi hoặc mắc số lỗi bằng nhau. Lời giải. Ta phân lớp học thành 15 nhóm (ta coi như thỏ là học sinh, lồng là nhóm): Nhóm 1: Gồm các em mắc 1 lỗi. Nhóm 2: Gồm các em mắc 2 lỗi. . . . Nhóm 14: Gồm các em mắc 14 lỗi. Nhóm 15: Gồm các em không mắc lỗi. Theo giả thiết ta cóNhóm 14 chỉ có em A. Còn lại 14 nhóm chứa 29 em. Vì 29 = 2× 14 + 1, theo nguyên lý Dirichlet tồn tại một nhóm chứa ít nhất 2 + 1 = 3 em. Từ đó có điều phải chứng minh. Ví dụ 2.4. Có 15 đội bóng tham dự một giải đấu theo thể thức đấu vòng tròn một lượt. Chứng minh rằng tại bất kì thời điểm nào của giải ta luôn tìm được 2 đội có cùng số trận đã đấu bằng nhau tại thời điểm đó (có thể là 0 trận). Lời giải. Số trận đã đấucủa mỗi đội có thể nhận 15 giá trị khác nhau: 0; 1; 2; . . . , 14.Trong trường hợp này không thể áp dụng ngay nguyên lý Dirichlet được vì số đội cũng là 15. Hai trường hợp 0 trận và 14 trận không thể xảy ra đồng thời vì nếu có một đội nào chưa đấu trận nào thì đồng thời không thể có một đội nào đó đã đấu hết 14 trận, ngược lại nếu có một đội đã đá 14 trận thì không thể có 1 đội chưa đá một trận nào. Vì vậy số trận đã đấu của mỗi đội trong thực tế có thể nhận 14 giá trị từ 0 đến 13 hoặc từ 1 đến 14.Khi đó theo nguyên lý Dirichlet ta luôn có thể tìm được hai đội có cùng số trận đã đấu. 2.2 Ứng dụng nguyên lý Dirichlet vào giải toán Số học Ví dụ 2.5. Chứng minh rằng từ 52 số nguyên bất kỳ luôn có thể chọn ra hai số mà tổng hoặc hiệu của chúng chia hết cho 100 Lời giải. Tất cả các số dư trong phép chia cho 100 được chia thành 51 nhóm như sau: {0} , {1; 99} , {2; 98} , . . . , {49; 51} , {50}. Có 52 số nên theo nguyên lý Dirichlet có hai số mà các số dư khi chia cho 100 thuộc cùng một nhóm trên. Hai số này có hiệu chia hết cho 100 (nếu số dư của chúng bằng nhau) hoặc có tổng chia hết cho 100 (nếu số dư của chúng khác nhau). Ví dụ 2.6. Chứng minh rằngtồn tại số tự nhiên có tất cả các chữ số bằng 1, chia hết cho 2019 Lời giải. Xét dãy số hữu hạn:1; 11; 111; . . . ; 111 . . . 1︸ ︷︷ ︸ 2020 se`1 Dãy này có 2020 số hạng khác nhau,lấy 2020 số này chia cho 2019 ta được các phần dư thuộc tập hợp có 2019 phần tử sau: {0; 1; 2; . . . ; 2018}. Theo nguyên lý Dirichlet ta luôn có thể tìm được hai số hạng khác nhau của dãy có cùng phần dư và hiệu của chúng chia hết cho 2019. 2 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ta kí hiệu các số này là:111 . . . 1︸ ︷︷ ︸ k se`1 và 111 . . . 1︸ ︷︷ ︸ k+l se`1 . Lấy số lớn trừ cho số nhỏ,ta được hiệu là: 111 . . . 1︸ ︷︷ ︸ l se` 1 000 . . . 0︸ ︷︷ ︸ k se`0 chia hết cho 2019. Rõ ràng 1 000 . . . 0︸ ︷︷ ︸ k se`0 và 2019 là nguyên tố cùng nhau nên số 111 . . . 1︸ ︷︷ ︸ l se`1 chia hết cho 2019. Ví dụ 2.7. Cho 2020 cái kẹo vào 1010 cái hộp sao cho không có hộp nào có nhiều hơn 1010 cái kẹo và mỗi hộp có ít nhất một cái kẹo. Chứng minh rằng có thể tìm thấy một số hộp mà tổng số kẹo trong các hộp đó đúng bằng 1010. Lời giải. +) Nếu tất cả các hộp có số kẹo bằng nhau và bằng 2 thì lấy 505 cái hộp bất kì đều có tổng số kẹo bằng 1010. - Nếu tồn tại hai hộp có số kẹo khác nhau, sắp xếp các hộp thành một hàng ngang sao cho hai hộp đầu tiên không có cùng số kẹo. Kí hiệu ai là số kẹo trong hộp thứ i, i = 1, 2, . . . , 1010.Xét các số sau: S1 = a1, S2 = a1 + a2, . . . , S1010 = a1 + a2 + · · ·+ a1010 - Nếu hai số trong chúng có cùng số dư khi chia cho 1010, giả sử đó là Si, Sj (j > i). Khi đó Sj − Si = ai+1 + · · ·+ aj ... 1010. Rõ ràng 1 ≤ Sj− Si < 2020, mà Sj− Si ... 1010⇒ Sj− Si = 1010. Hay ai+1 + · · ·+ aj = 1010 Giả sử trong dãy S1, S2, . . . , S1010 không có 2 số nào có cùng số dư khi chia cho 1010. Xét 1011 số sau S1, S2, . . . , S1010, a2. Theo nguyên lý Dirichlet tồn tại hai số có cùng số dư khi chia cho 1010. Lại có S1 = a1 6= a2, 1 ≤ a1, a2 ≤ 1010, nên a1, a2 không cùng số dư khi chia cho 1010. Suy ra tồn tại k = 2, 3, . . . , 1010 thỏa mãn Sk, a2 có cùng số dư khi chia cho 1010. Khi đó Sk − a2 = a1 + a3 + · · ·+ ak ...1010. Lại có 1 ≤ a1 + a3 + · · ·+ ak < 2020, suy ra a1 + a3 + · · ·+ ak = 1010. 2.3 Ứng dụng nguyên lý Dirichlet vào giải toán Hình học Ví dụ 2.8. Trong hình vuông cạnh bằng 1, đặt 51 điểm bất kì, phân biệt. Chứng minh rằng có ít nhất 3 trong số 51 điểm đó nằm trong một hình tròn bán kính 1 7 . Lời giải. Chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnh bằng 1 5 . Theo nguyên lý Dirichlet, tồn tại ít nhất một hình vuông con (A) chứa ít nhất ba điểm trong số 51 điểm đó. Đường tròn ngoại tiếp hình vuông (A) có bán kính 1 5 √ 2 ≤ 1 7 . Vậy ba điểm nói trên nằm trong hình tròn đồng tâm với hình vuông a, có bán kính 1 7 . Ví dụ 2.9. Trong hình chữ nhật 3 × 4 đặt 6 điểm. Chứng minh rằng trong số đó luôn tìm được hai điểm có khoảng cách giữa chúng không lớn hơn √ 5. Lời giải. Chia hình chữ nhật đã cho thành năm hình ABCD, DCKEF,KFNM, NFEQR,QEDAS. 3 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Vì có 6 điểm nên theo nguyên lí Dirichlet tồn tại một trong năm hình trên, mà hình này chứa ít nhất hai trong 6 điểm đã cho. Giả sử (P) là một hình trong năm hình trên. Đặt d (P) là khoảng cách lớn nhất giữa hai điểm trong (P). Dễ thấy cả năm hình trên đều có d = √ 5. (Ví dụ: d (ABCD) = AC =√ 5, d (DCKFE) = CE = KE = CF = DK = √ 5). Từ đó suy ra luôn tìm được 2 điểm trong số 6 điểm đã cho có khoảng cách không lớn hơn √ 5. Đó là điều phải chứng minh. Nhận xét 2.1. Trong ví dụ này, ta có thể thay hình chữ nhật bằng hình bình hành. Ví dụ 2.10 (VMO 2018). Một nhà đầu tư có một mảnh đất hình chữ nhật có kích thước là 120m × 100m. Nhà đầu tư muốn xây một ngôi nhà có nền hình chữ nhật kích thước 25m × 35m và xây bên ngoài 9 bồn hoa hình tròn có đường kính 5m. Chứng minh rằng dù xây trước 9 bồn hoa ở đâu trên mảnh đất đó thì phần đất còn lại vẫn đủ chỗ để xây ngôi nhà. Lời giải. Xét hình chữ nhật ABCD có AB = CD = 120, AD = BC = 100. Chia hình chữ nhật thành 10 hình chữ nhật nhỏ kích thước 30m × 40m như hình vẽ. Xét 9 điểm là tâm của các giếng nước. Theo nguyên lí Dirichlet, tồn tại một hình chữ nhật con không chứa điểm nào trong 9 điểm nói trên. Giả sử hình chữ nhật đó là XYZT có XY = ZT = 40, XT = YZ = 30. 4 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ta xét hình chữ nhật X′Y′Z′T′ nằm bên trong hình chữ nhật XYZT và có các cạnh song song với các cạnh của hình chữ nhật XYZT và cách các cạnh của hình chữ nhật XYZT một khoảng cách bằng 2.5 thì X′Y′Z′T′ có kích thước 25m × 35m. Đây chính là mảnh đất hình chữ nhật để xây nhà. Ví dụ 2.11. Cho một chữ nhật và 2021 đường thẳng, mỗi đường thẳng đều chia hình chữ nhật thành hai tứ giác có tỉ số diện tích 1 : 2. Chứng minh rằng trong số các đường thẳng đã cho, có ít nhất 506 đường thẳng cùng đi qua một điểm. Lời giải. Gọi d là đường thẳng chia hình chữ nhật ABCD thành hai tứ giác có tỉ số diện tích là 1 : 2. Đường thẳng d không thể cắt hai cạnh kề nhau của hình chữ nhật. Giả sử d cắt hai cạnh AB và CD tại M và N, khi đó nó cắt đường trung bình QR tại I. Giả sử SBMNC = 1 2 SAMNDthì RI = 1 2 IQ. Như vậy mỗi đường thẳng đã cho chia các đường trung bình của hình chữ nhật theo tỉ số 1 : 2. Có 4 điểm chia các đường trung bình của hình chữ nhật ABCD theo tỉ số 1 : 2. Có 2021 = 505× 4 + 1 đường thẳng, mỗi đường thẳng đi qua một trong 4 điểm. Vậy theo nguyên lý Dirichlet có ít nhất 506 đường thẳng cùng đi qua 1 điểm. 2.4 Ứng dụng nguyên lý Dirichlet vào giải các bài toán tô màu Ví dụ 2.12. Chứng minh rằng trong 6 người bất kì luôn có thể tìm ra ba người đôi một quen nhau hoặc đôi một không quen nhau. Lời giải. Để giải quyết bài toán này, ta có thể phát biểu lại bài toán như sau: Cho 6 điểm trong đó hai điểm nào cũng được nối với nhau bằng một đoạn thẳng và tô bởi chỉ một trong hai màu xanh hoặc đỏ. Chứng minh bao giờ cũng tìm ra được một tam giác có ba cạnh cùng màu. 5 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Thật vậy, gọi 6 điểm là A,B,C,D,E,F.Từ điểm A ta kẻ được 5 đoạn thẳng là AB,AC,AD,AE,AF. Theo nguyên lí Dirichlet, tồn tại ba đoạn thẳng được tô bởi cùng một màu. Không mất tính tổng quát giả sử đó là các đoạn thẳng AB,AC,AD và cùng tô màu xanh. Nếu tồn tại ít nhất một đoạn thẳng trong ba đoạn thẳng BC,CD,DB được tô xanh thì bàitoán được chứng minh (giả sử BC được tô xanh thì tam giác ABC thoả mãn). Nếu cả ba đoạn thẳng BC,CD,DB đều được tô đỏ thì tam giác BCD thoả mãn.Vậy bài toán đã được chứng minh. Ví dụ 2.13. Mỗi điểm trên mặt phẳng được tô bởi một trong hai màu. Chứng minh tồn tại một hình chữ nhật có 4 đỉnh được tô bởi cùng một màu. Lời giải. Xét các giao điểm của ba đường thẳng ngang và 9 đường thẳng đứng như hình vẽ. Số cách tô màu ba giao điểm trên cùng một đường thẳng đứng là 2× 2× 2 = 8 cách. Do có 9 đường thẳng đứng nên tồn tại hai đường thẳng có cách tô màu ba giao điểm giống hệt nhau. Giả sử hai đường thẳng đó là hai đường thẳng chứa các giao điểm là A1, A2, A3 và B1, B2, B3 như hình vẽ. Ba điểm A1, A2, A3 được tô bởi hai màu nên tồn tại hai điểm cùng màu. Giả sử là A1 và A3. Như vậy hình chữ nhật A1A3B3B1 có 4 đỉnh được tô bởi cùng một màu. Vậy ta có điểu phải chứng minh. Ta có thể phái triển bài toán này như sau: Mỗi điểm trên mặt phẳng được tô bởi một trong n màu (n là số nguyên dương). Chứng minh tồn tại một hình chữ nhật có 4 đỉnh được tô bởi cùngmột màu. Chứngminhmệnh đề tổng quát tương tự như với trường hợp n = 2. Ta sẽ xét giao điểm của của ba đường thẳng ngang và n3 + 1 đường thẳng đứng. 6 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ví dụ 2.14. Mỗi điểm trên mặt phẳng được tô bởi một trong ba màu. Chứng minh rằng tồn tại hai điểm cùng màu có khoảng cách bằng 1. Lời giải. Xét hình thoi ABCD với các tam giác ABD,BCD là các tam giác đều cạnh bằng 1. Theo nguyên lí Dirichlet tồn tại hai điểm cùng màu. Nếu hai điểm ấy cùng là đỉnh của một trong hai tam giác đều ABD hoặc BCD thì đó là hai điểm cần tìm. Nếu ngược lại thì A và C phải cùng màu. Xét tập hợp các hình thoi như trên với A cố định. Nếu không có hình thoi nào thoả mãn tồn tại ít nhất một cạnh của một trong hai tam giác đều ABD hoặc BCD có hai đầu cùng màu thì C phải cùng màu với A. Khi đó tất cả các điểm nằm trên đường tròn (A, √ 3 )được tô bởi cùng một màu. Do đó hai điểm bất kì trên đường tròn này có khoảng cách bằng 1 sẽ thoả mãn yêu cầu bài toán. Ví dụ 2.15. Cho hình đa giác đều có 9 cạnh. Mỗi đỉnh của nó được tô màu bằng một trong hai màu trắng hoặc đen. Chứng minh rằng tồn tại hai tam giác phân biệt có diện tích bằng nhau mà các đỉnh của mỗi tam giác được tô cùng màu. Lời giải. Gọi chín đỉnh của đa giác là A1, A2, . . . , A9 đều được tô bằng một trong hai màu trắng hoặc đen. Nên theo nguyên lý Dirichlet có ít nhất năm đỉnh trong số đó được tô bằng cùng một màu. Giả sử có năm đỉnh được tô màu đen, năm đỉnh này tạo ra: C35 = 10 (tam giác). Ta gọi là tam giác màu đennếu tam giác có ba đỉnh cùng màu đen. Gọi P là tập hợp các đỉnh của đa giác đã cho, tức là P = {A1, A2, . . . , A9}. Gọi O là tâm của đa giác đều đã cho.Xét phép quay tâm O với góc quay lần lượt là 0◦, 40◦, 80◦, 120◦, 160◦, 200◦, 240◦, 280◦, 320◦. Rõ ràng ứng với mỗi phép quay này tập P sẽ biến thành chính nó. 7 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Sau chín phép quay trên thì có 10 tam giác đen biến thành 90 tam giác đen mà mỗi tam giác này đều có các đỉnh thuộc tập hợp P. Số tam giác khác nhau có đỉnh trong P là: C39 = 84 (tam giác). Vì 84 < 90 nên theo nguyên lí Dirichlet tồn tại hai tam giác đen ∆ và ∆′ sao cho nó cùng là ảnh của một tam giác qua 2 trong 9 phép quay trên.Vì phép quay là một phép dời hình nên bảo toàn khoảng cách vì thế nó bảo toàn toàn diện tích nên S∆ = S∆′ (đpcm). 2.5 Ứng dụng nguyên lý Dirichlet vào giải các bài toán về tập hợp Ví dụ 2.16. Cho hai tập hợp A và B thỏa mãn các 2 điều kiện sau:Mỗi tập hợp đều gồm các số nguyên dương khác nhau và nhỏ hơn 2019; Tổng số phần tử của A và B lớn hơn 2019. Chứng minh rằng tồn tại ít nhất một phần tử của A và một phần tử của B có tổng bằng 2019. Lời giải. Giả sử A = {a1, a2, . . . , am} và B = {b1, b2, . . . , bn}. Ta có m+ n > 2019 (gt) Xét ci = 2019− bi (i = 1, 2, 3, . . . , n) Do các phần tử của B đôi một khác nhau nên các số ci cũng đôi một khác nhau. Mặt khác, do mọi số bi đều là số nguyên dương khác nhau và nhỏ hơn 2019 nên mọi số ci cũng là số tự nhiên nhỏ hơn 2019. Do đó ta có m+ n số tự nhiên nhỏ hơn 2019 sau đây: a1, a2, . . . , am, c1, c2, . . . , cn. Vì chỉ có 2019 số tự nhiên nhỏ hơn 2019 trong khi m+ n > 2019 nêntheo nguyên lý Dirichlet trong dãy a1, a2, . . . , am, c1, c2, . . . , cn phải có 2 số bằng nhau. Vì các số ai khác nhau, các số ci khác nhau nên ta suy ra một và chỉ một trong 2 số đó phải thuộc A. Giả sử 2 số bằng nhau trên là ai = ck nên ai = 2019− bk hay ai + bk = 2019. Ví dụ 2.17. Cho số nguyên dương n ≥ 3. Chứng minh rằng tập hợp X = { 1; 2; 3; . . . ; n2 − n} có thể chia thành hai tập con không giao nhau sao cho không tập nào trong chúng chứa n phần tử a1, a2, . . . , an với a1 < a2 < · · · < an và ak ≤ ak−1 + ak+12 với mọi k = 2; 3; . . . , n− 1. Lời giải. Đặt Sk = { k2 − k+ 1; k2 − k+ 2; . . . ; k2} ; Tk = {k2 + 1; k2 + 2; . . . ; k2 + k}; S = n−1⋃ k=1 Sk; T = n−1⋃ k=1 Tk. Ta chứng minh S, T là các tập con cần tìm của X. Dễ dàng thấy S ⋂ T = ∅ và S ⋃ T = X Ta chứng minh phản chứng. Giả sử S gồm các phần tử a1, a2, . . . , anvới a1 < a2 < · · · < an và ak ≤ ak−1 + ak+12 với mọi k = 2; 3; . . . , n− 1. Khi đó ta có ak − ak−1 ≤ ak+1 − ak, với mọi k = 2; 3; . . . , n− 1 (1) Nếu a1 ∈ Si., ta có i < n− 1 do |Sn−1| < n. Suy ra tồn tại ít nhất n− |Si| = n− i phần tử thuộc {a1; a2; . . . ; an}⋂ (Si+1 ⋃ Si+2 ⋃ · · ·⋃ Sn−1). Áp dụng nguyên lý Dirichlet, tồn tại ít nhất một tập Sj, (i < j < n) chứa ít nhất 2 phần tử trong số các phần tử a1, a2, . . . , an.Tức là tồn tại ak sao cho ak, ak+1 ∈ Sj và ak−1 ∈ S1 ⋃ S2 ⋃ · · ·⋃ Sj−1. Khi đó ta có ak+1 − ak ≤ ∣∣Sj∣∣− 1 = j− 1; ak − ak−1 ≥ ∣∣Tj−1∣∣+ 1 = j Suy ra ak+1 − ak < ak − ak−1. Điều này, mâu thuẫn với (1) 8 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Vậy S không chứa các phần tử a1, a2, . . . , anvới a1 < a2 < · · · < an và ak ≤ ak−1 + ak+1 2 với mọi k = 2; 3; . . . , n− 1. Chứng minh tương tự ta cũng có tập T không chứa các phần tử a1, a2, . . . , anvới a1 < a2 < · · · < an và ak ≤ ak−1 + ak+12 với mọi k = 2; 3; . . . , n− 1.Vậy S, T là các tập con cần tìm của X. Ví dụ 2.18. Một quốc gia có n thành phố (n ≥ 5) . Một hãng hàng không của quốc gia đó có các chuyến bay hai chiều bay trực tiếp giữa một số cặp thành phố với nhau và có nhiều nhất là 3n− 7 chuyến bay như vậy. Một nhóm gồm 5 thành phố được gọi là một Tua 5 thành phố nếu giữa hai thành phố bất kỳ trong nhóm đều có các chuyến bay hai chiều. Chứng minh rằng hãng hàng không có thể thiết lập các chuyến bay hai chiều mới giữa hai thành phố chưa có chuyến bay trực tiếp mà không làm xuất hiện thêm một Tua 5 thành phố nào khác. Lời giải. Ta sẽ ký hiệu tập các thành phố là T = {T1, T2, . . . , Tn} và F là tập gồm tất cả các cặp thành phố (không kể thứ tự) mà có chuyến bay hai chiều giữa chúng. Giả sử kết luận của bài toán là sai, tức là với mỗi cặp {A1, A2} /∈ F tồn tại các thành phố B1, B2, B3 sao cho trong tập 5 phần tử S = {A1, A2, B1, B2, B3} có tất cả các cặp hai phần tử trừ cặp {A1, A2} đều thuộc về F. Giả sử một người cần chọn một lộ trình đi thăm mỗi thành phố đúng một lần. Tức là cần chọn 1 hoán vị σ của tập {1, 2, . . . , n} và đi thăm các thành phố theo thứ tự là: Tσ(1), Tσ(2), . . . , Tσ(n). Với một cặp {A1, A2} /∈ F gọi S là tập như trên. Ta nói rằng một lộ trình (tức một hoán vị) là tương thích với cặp {A1, A2} nếu người đó viếng thăm cả A1 và A2 trước khi viếng thăm các thành phố từ tập T\S. Nói cách khác, A1 và A2 chỉ có thể đứng trước bởi bộ A1, A2, B1, B2, B3 trong thứ tự các thành phố xác định bởi hoán vị σ. Ta đếm số các lộ trình (hoán vị) tương thích với một cặp cố định {A1, A2} /∈ F. Đầu tiên chọn 3 vị trí cho B1, B2, B3 - có n (n− 1) (n− 2) cách; chọn 2 vị trí trong số n− 3 vị trí còn lại cho A1 và A2 - có 2! cách; n− 5 vị trí cuối cùng dành cho các phần tử của tập T\S. Suy ra số các lộ trình như thế bằng n (n− 1) (n− 2) .2!. (n− 5)!. Từ điều kiện bài toán ta có |F| < 3n− 6, suy ra số các cặp thành phố không được kết nối bởi các chuyến bay trực tiếp là ∣∣FC∣∣ > C2n − (3n− 6) = (n− 3) (n− 4)2 . Vì thế, tổng số các lộ trình tương thích với mỗi cặp không thuộc F bằng: n (n− 1) (n− 2) .2!. (n− 5)!. ∣∣FC∣∣ > n (n− 1) (n− 2) .2!. (n− 5)!.(n− 3) (n− 4) 2 = n!, lớn hơn số các lộ trình (hoán vị). Theo nguyên lý Dirichlet, tồn tại một hoán vị σ sao cho nó tương thích với ít nhất hai cặp khác nhau thuộc tập FC. Chẳng hạn đó là các cặp {A1, A2} và {A′1, A′2} , và gọi S, S′ là hai tập tương ứng như ở trên (phần tử của hai tập này có thể trùng nhau). Theo định nghĩa ban đầu, A1, A2 đến trước tất cả các thành phố từ tập T\S, A′1, A′2 đến trước tất cả các thành phố từ tập T\S′. Ta sẽ chứng minh: {A1, A2} ⊂ S′ hoặc {A′1, A′2} ⊂ S. Thật vậy, giả sử trái lại ta có thể tìm được các chỉ số i, j ∈ {1, 2} sao cho Ai ∈ T\S′ và A′ j ∈ T\S, từ đó suy ra A′ j đến trước Ai và Ai đến trước A′ j, suy ra mâu thuẫn. Không mất tổng quát có thể giả sử xảy ra trường hợp thứ nhất là {A1, A2} ⊂ S′ = {A′1, A′2, B′1, B′2, B′3} . 9 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Khi đó, tập S′ chứa hai cặp khác nhau không thuộc về F đó là {A1, A2} và {A′1, A′2} , điều này mâu thuẫn với cách xây dựng ở trên. Từ đó ta được điều phải chứng minh. Tài liệu [1] Phan Huy Khải, Các bài toán hình học tổ hợp, NXB Giáo dục, 2007. [2] Phạm Minh Phương, Các chuyên đề số học, NXB