Nguyên Lí Cực Hạn – Một Số Bài Toán Tổ Hợp Và Hình Học | CMaths

Trang chủ » Nguyên Lý Cực Hạn Trong Tổ Hợp » Nguyên Lí Cực Hạn – Một Số Bài Toán Tổ Hợp Và Hình Học | CMaths

Có thể bạn quan tâm

Nguyên lý cực hạn được phát biểu đơn giản như sau:

  1. Trong một tập hữu hạn khác rỗng các số thực luôn có thể chọn được số bé nhất và số lớn nhất.
  2. Trong một tập hợp khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất.

Hãy bắt đầu bằng một ví dụ khá đơn giản và vui để có thể làm quen và dễ dàng nhớ được nội dung này:

Bài toán 1: a. Tám người ngồi xung quanh một bàn ăn hình tròn. Biết rằng, tuổi của mỗi người bằng trung bình cộng của hai người kế bên (phải và trái). Chứng tỏ rằng tất cả mọi người đều cùng tuổi với nhau. b. Nam, 26 tuổi cùng với 14 người bạn ngồi xung quanh một bàn tiệc hình tròn. Biết rằng tuổi của mỗi người khác hai người kế bên (phải và trái) nhiều nhất 1 tuổi. Có thể gọi bia cho tất cả mọi người hay không? Lời giải – Gợi ý: a. Trong 8 người, luôn có một người có tuổi nhiều (hoặc ít) nhất. Ta chứng minh anh ta bằng tuổi với tất cả mọi người. b. Gọi A là người có số tuổi nhỏ nhất, chứng minh được A trên 18 tuổi.

Bài toán 2: a. Trên một mạng lưới ô vuông vô hạn trên một mặt phẳng, đặt vào mỗi ô vuông một số tự nhiên sao cho số trong mỗi ô bằng trung bình cộng của bốn số trong các ô vuông có cạnh kề với ô đó. Chứng minh tất cả các số bằng nhau. b. Nếu số trong mỗi ô bằng trung bình cộng của bốn số trong các ô vuông bốn góc. Ta có thể đặt được tối đa bao nhiêu giá trị của các số? Lời giải – Gợi ý: a. Tồn tại ô vuông với số được điền bé nhất, 4 ô kề cạnh cũng được đặt cùng số bé nhất đó. Với ô vuông khác bất kì ta luôn tìm được một dãy các ô vuông kề cạnh bắt đầu từ ô vuông đó tới ô vuông với số bé nhất, do vậy cũng được đặt số bé nhất. Vậy tất cả các số đều bằng nhau. b. Tô màu đen trắng theo kiểu bàn cờ, ta chứng minh được tất cả các số trong các ô cùng màu phải bằng nhau. Tối đa đặt được 2 giá trị của các số vào mạng lưới ô vuông.

Với các bài toán đơn giản, bằng cảm quan đôi khi có thể chọn ngay các giá trị biên thỏa mãn yêu cầu:

Bài toán 3: Bảy người câu được 100 con cá. Biết rằng không có hai người nào câu được số cá như nhau. Chứng minh rằng có ba người câu được tổng cộng không ít hơn 50 con cá. Lời giải – Gợi ý: Ta sắp xếp các người câu cá theo thứ tự để số cá câu được của họ giảm dần. Như thế người thứ nhất câu được nhiều cá nhất và người thứ bảy câu được ít cá nhất. Nếu người thứ tư câu được không ít hơn 15 con cá, thì ba người đầu câu được không ít hơn 16+17+18=51 con cá. Nếu người thứ tư câu được 14 con cá hoặc ít hơn thì cả bốn người sau câu được không quá 14+13+12+11=50 con. Như vậy ba người đầu câu được không ít hơn 50 con. Vậy ba người đầu luôn câu được tổng cộng không dưới 50 con cá.

Bài toán 4: Đặt các số nguyên 1,2,3,\ldots ,{{n}^{2}} vào một bàn cờ n\times n~\left( n\ge 2 \right) một cách ngẫu nhiên, mỗi số đúng một lần, mỗi ô một số. Chứng minh rằng tồn tại hai ô vuông kề nhau (chung cạnh hoặc chung đỉnh) mà có giá trị khác nhau ít nhất n+1. Lời giải – Gợi ý: Với 2 ô bất kì ta luôn tìm được một dãy không quá n các ô vuông kề nhau nối chúng (tính cả 2 ô đó). (1) – Bạn tự giải thích nhé! 🙂 Giả sử ngược lại, hai ô vuông kề nhau bất kì có giá trị khác nhau nhiều nhất n. (2) Xét hai ô vuông chứa số 1 và {{n}^{2}}. Theo nhận xét (1) ta có một dãy không quá n ô vuông kề nhau nối chúng. Nhưng kết hợp với điều kiện (2), giá trị hai ô này khác nhau không quá n\times \left( n-1 \right). Như vậy ta thu được {{n}^{2}}-1\le n\times \left( n-1 \right)\Leftrightarrow n\le 1. Không thể xảy ra vì n\ge 2. Ta có đpcm.

Bình luận: Việc chọn ra hai phần tử cực biên là điều khá tự nhiên nếu mục tiêu của chúng ta là chỉ ra điều vô lí.

Việc nhìn ra đại lượng để áp dụng Nguyên lý cực hạn đôi khi là không đơn giản, ta phải chọn một “hàm đo” thích hợp nhằm áp dụng được nguyên lý cho tập hợp số để thu được lời giải:

Bài toán 5: Cho trước một bảng m\times n các số thực. Một phép biến đổi bảng là một lần ta đổi dấu của tất cả các số trong một hàng hay một cột nào đó của bảng. Chứng minh rằng ta luôn có thể thực hiện được một dãy hữu hạn các phép biến đổi bảng để kết quả thu được là một bảng với tổng các số trong một dòng, một cột bất kì đều không âm. Lời giải – Gợi ý: Nếu bảng chưa đạt yêu cầu, ta thực hiện một phép biến đổi bảng “tốt” như sau: đổi dấu một hàng hay cột có tổng các số là âm. Xét số S là tổng tất cả các số có trong một bảng, khi ta thực hiện một phép biến đổi “tốt”, S tăng lên thực sự. Tập các số khi ta biến đổi bảng từ bảng ban đầu rõ ràng là hữu hạn (không thể vượt quá {2^{m \times n}}, giải thích tại sao?). Do vậy tồn tại một số S lớn nhất, xét bảng với số S lớn nhất có thể này. Rõ ràng đó là bảng mà có tổng các số trong một dòng, một cột bất kì đều không âm, vì ta không thể thực hiện thêm một phép biến đổi “tốt” từ bảng này.

Bình luận: Việc ta biến đổi dòng hay cột “âm” là khá tự nhiên nhằm làm bảng “tốt lên”, tuy nhiên ta phải chọn được đại lượng để biết khi nào bảng thu được là “tốt nhất” và để thấy việc biến đổi là hữu hạn. Các ví dụ sau sẽ đòi hỏi một sự suy luận nhất định để chọn được đại lượng phù hợp.

Bài toán 6: Trong một buổi tiệc với một số lượng người tham gia nhất định, xét quan hệ “bạn bè” theo nghĩa: “Nếu A là bạn của B thì B cũng là bạn của A”. Chứng minh rằng người trong buổi tiệc luôn có thể chia làm hai nhóm để đưa vào trong hai phòng khác nhau sao cho: Với mỗi người trong một phòng bất kì, ít nhất một nửa số bạn của người đó ở phòng còn lại. Lời giải – Gợi ý: Với một cách chia bất kì số người thành 2 nhóm, gọi \displaystyle là số lượng tất cả các cặp \left\{ P;Q \right\} sao cho P và Q ở khác phòng và P,Q là bạn của nhau. Xét cách chia với m lớn nhất có thể (vì số cách chia là hữu hạn nên m nhận hữu hạn giá trị), ta chứng minh cách chia này thỏa mãn yêu cầu. Thật vậy, với người P bất kì, gọi {{a}_{P}} là số bạn của anh ta trong cùng phòng và {{b}_{P}} là số bạn của anh ta khác phòng. Nếu ta chuyển P sang phòng còn lại thì ta sẽ cộng \left( {{a}_{P}}-{{b}_{P}} \right) vào m. Do giả thiết chọn m là lớn nhất nên ta phải có {{a}_{P}}-{{b}_{P}}\le 0 hay {{a}_{P}}\le {{b}_{P}}. Vậy với cách chia mà m lớn nhất có thể thì thỏa mãn yêu cầu.

Bài toán 7: Có 3 trường học, mỗi trường có n học sinh. Mỗi học sinh quen với ít nhất n+1 học sinh từ hai trường khác. Chứng minh rằng người ta có thể chọn ra từ mỗi trường một bạn sao cho ba học sinh được chọn đôi một quen nhau. Lời giải – Gợi ý: Gọi A là học sinh có nhiều bạn nhất ở một trường khác. Gọi số bạn nhiều nhất này là k. Giả sử A ở trường thứ nhất và tập các bạn quen A là M=\left\{ {{B}_{1}};{{B}_{2}};\ldots ;{{B}_{k}} \right\} ở trường thứ 2. Cũng theo giả thiết, có ít nhất 1 học sinh C ở trường thứ 3 quen với . Vì C quen không quá k học sinh ở trường thứ nhất nên theo giả thiết C quen với ít nhất n+1-k học sinh của trường thứ 2, đặt N=\left\{ {{D}_{1}};{{D}_{2}};\ldots ;{{D}_{m}} \right\} là những người quen C ở trường thứ hai thì m\ge n+1-k. Vì đều là tập con của tập hợp gồm n học sinh và \left| M \right|+\left| N \right|\ge k+n+1-k=n+1 nên M\mathop{\cap }^{}N\ne \varnothing . Chọn B\in M\mathop{\cap }^{}N thì ta có A,B,C đôi một quen nhau.

Với các bài toán hình học với nhiều đại lượng có thể lựa chọn, việc chọn ra đại lượng để áp dụng Nguyên lý cực hạn đòi hỏi nhiều sự suy luận và tưởng tượng tốt:

Bài toán 8: Trên một mặt bàn đặt một số các đồng xu với kích cỡ không giống nhau đôi một (các đồng xu không được đè lên nhau và phải nằm sấp hoặc ngửa trên bàn). Chứng minh rằng dù ta đặt như thế nào đi nữa, cũng luôn tồn tại một đồng xu chỉ tiếp xúc được với nhiều nhất 5 đồng xu khác. Lời giải – Gợi ý: Trước hết, chú ý rằng một đồng xu không thể tiếp xúc với 6 đồng xu khác lớn hơn nó (gợi ý: dùng phản chứng, góc đối diện với cạnh lớn nhất là lớn nhất trong tam giác). Bây giờ, vì số các đồng xu là hữu hạn nên luôn tồn tại đồng xu với đường kính nhỏ nhất. Xét đồng xu này, theo nhận xét bên trên, nó chỉ có thể tiếp xúc với nhiều nhất 5 đồng xu khác.

Bài toán 9: Trong một đường tròn tâm O đã cho, xét tập hợp C gồm một số hữu hạn các dây cung thỏa mãn tính chất sau: mỗi dây cung thuộc tập C đi qua trung điểm của một dây cung khác cũng thuộc C. Chứng minh rằng tất cả các dây cung này đều là đường kính. Lời giải – Gợi ý: Xét dây cung với độ dài ngắn nhất {{l}_{0}}.

bài 9Giả sử {{l}_{0}} không là một đường kính, theo giả thiết {{l}_{0}} đi qua trung điểm của một dây cung {{l}_{1}} khác. Gọi {{M}_{0}},{{M}_{1}} lần lượt là trung điểm của {{l}_{0}},{{l}_{1}}, ta dễ dàng chứng minh được {M}_{0}\ne{M}_{1} và do đó O{{M}_{0}}< O{{M}_{1}}\Rightarrow {{l}_{0}} > {{l}_{1}}, trái với tính ngắn nhất của {{l}_{0}}. Vậy {{l}_{0}} phải là một đường kính và do vậy tất cả các dây cung trong tập C đều là các đường kính.

Bài toán 10: (Định lý Sylvester) Cho tập hợp S gồm hữu hạn các điểm trên mặt phẳng thỏa mãn tính chất sau: Một đường thẳng đi qua 2 điểm thuộc S đều đi qua ít nhất một điểm thứ ba thuộc S. Khi đó tất cả các điểm của S nằm trên một đường thẳng. Lời giải – Gợi ý:

bài 10Giả sử phản chứng là tồn tại một tập hợp S gồm hữu hạn điểm không thẳng hàng nhưng mọi đường thẳng qua hai điểm trong S đều chứa ít nhất ba điểm. Một đường thẳng gọi là đường nối nếu nó đi qua ít nhất hai điểm trong S. Giả sử (P,l) là cặp điểm và đường nối có khoảng cách dương nhỏ nhất trong mọi cặp điểm-đường nối. Theo giả thiết, l đi qua ít nhất ba điểm trong S, nên nếu hạ đường cao từ P xuống l thì tồn tại ít nhất hai điểm nằm cùng một phía của đường cao (một điểm có thể nằm ở ngay chân đường cao). Trong hai điểm này, gọi điểm ở gần chân đường cao hơn là B, và điểm kia là C. Xét đường thẳng m nối P và C. Khoảng cách từ B tới m nhỏ hơn khoảng cách từ S tới l, mâu thuẫn với giả thiết về P và l. Một cách để thấy điều này là tam giác vuông với cạnh huyền BC đồng dạng và nằm bên trong tam giác vuông với cạnh huyền PC. Do đó, không thể tồn tại khoảng cách dương nhỏ nhất giữa các cặp điểm-đường nối. Nói cách khác, mọi điểm đều nằm trên đúng một đường thẳng nếu mọi đường nối đều chứa ít nhất ba điểm.

Bài toán 11: Cho B và W lần lượt là tập hữu hạn (lớn hơn 2 phần tử) gồm các điểm đen và trắng trên mặt phẳng, thỏa mãn tính chất sau: Mỗi đoạn thẳng nối hai điểm cùng màu luôn qua một điểm khác màu. Chứng minh rằng cả hai tập điểm đều thuộc một đường thẳng. Lời giải – Gợi ý: Giả sử ngược lại, hai tập điểm không cùng nằm trên một đường thẳng. Khi đó, tồn tại một hoặc hơn các tam giác với đỉnh là các điểm thuộc B,W.

bài 11Xét tam giác có diện tích nhỏ nhất. Rõ ràng, ít nhất hai đỉnh của tam giác cùng màu theo nguyên lý Dirichlet. Do vậy, phải có một điểm với màu khác giữa chúng. Tuy nhiên điểm này cùng với hai điểm khác (là đỉnh của tam giác bên trên) lập thành một tam giác có diện tích nhỏ hơn diện tích của tam giác đã xét. Ta thu được mâu thuẫn. Vậy tất cả các điểm thuộc hai tập đều nằm trên một đường thẳng.

Bài toán 12: Cho n điểm \left( n\ge 3 \right) nằm trên một mặt phẳng thỏa mãn tính chất sau: Nếu ta chọn ra từ đó ba điểm bất kì A,B,C thì diện tích của tam giác luôn bé hơn 1. Chứng minh rằng toàn bộ n điểm đó nằm bên trong hoặc trên biên của một tam giác với diện tích bé hơn 4. Lời giải – Gợi ý: Gọi ABC là ta giác có diện tích lớn nhất trong số các tam giác với ba đỉnh lấy từ n điểm đã cho. Để cho gọn ta kí hiệu diện tích tam giác ABC bởi \left[ ABC \right]. Ta có, \left[ {ABC} \right] < 1. Xét tam giác LMN là tam giác sao cho A,B,C lần lượt là trung điểm của các cạnh LM,MN,NL.

bài 12Thế thì \left[ LMN \right]=4\left[ ABC \right]<4. Ta chứng minh n điểm đã cho nằm bên trong hoặc trên biên của tam giác LMN. Thật vậy, giả sử ngược lại, tồn tại điểm nằm ngoài tam giác LMN. Khi đó, ta có thể nối P với hai đỉnh của ABC để tạo thành một tam giác với diện tích lớn hơn diện tích tam giác ABC. Ta thu được mâu thuẫn. Từ đó ta có đpcm.

Bài tập tự giải:

Bài 1.1: Có 2n+1 quả cầu với khối lượng là các số nguyên. Biết rằng cứ 2n quả cầu bất kì đều có thể chia thành hai nhóm, mỗi nhóm n quả cầu sao cho tổng khối lượng của các quả cầu trong từng nhóm bằng nhau. Chứng minh rằng khối lượng của tất cả các quả cầu đều như nhau.

Bài 1.2: Có n đấu thủ tham gia thi đấu bóng bàn theo nguyên tắc đấu vòng tròn. Chứng minh rằng sau khi giải đấu kết thúc, ta luôn có thể sắp xếp cả n đấu thủ theo một hàng dọc sao cho người đứng trước thắng người đứng kề sau.

Bài 1.3: Trên một ô của bàn cờ viết một số nguyên không âm thỏa mãn điều kiện sau: Nếu tại một ô nào đó viết số 0 thì tổng các số được viết trong các ô cùng hàng và cùng cột với ô đó không nhỏ hơn n. Chứng minh rằng tổng của số được viết không nhỏ hơn \frac{{{n}^{2}}}{2}.

Bài 1.4: Tôi mời 10 cặp vợ chồng tới nhà để tham gia một buổi tiệc. Khi bữa tiệc kết thúc, tôi hỏi mọi người (bao gồm cả vợ mình) một câu hỏi, họ đã bắt tay với bao nhiêu người. Câu trả lời nhận được của tất cả mọi người không ai giống nhau. Biết rằng mỗi người không bắt tay với vợ/chồng mình và hai người bất kì không bắt tay nhau quá một lần. Bao nhiêu người vợ tôi đã bắt tay?

Bài 1.5: Trong một hội nghị, cứ hai người bất kì thì có người quen chung, cứ hai người không quen nhau thì có đúng hai người quen chung. Chứng minh rằng trong hội nghị này, tất cả mọi người đều có số người quen là như nhau.

Bài 1.6: 15 mảnh tờ giấy với các kích cỡ và hình dáng khác nhau phủ kín một mặt bàn. Các tờ giấy có thể phủ lẫn nhau hoặc thậm chí vượt ra khỏi mép bàn. Chứng minh rằng có thể bỏ đi 5 tờ giấy sao cho 10 tờ còn lại bao phủ ít nhất 2/3 diện tích mặt bàn.

Bài 1.7: Cho n điểm trên mặt phẳng, tất cả không thẳng hàng. Chứng minh rằng tồn tại một đường thẳng đi qua đúng hai điểm trong số các điểm đó.

Bài 1.8: Trên mặt phẳng cho n điểm (n>3) trong đó không có ba điểm nào thẳng hàng. Chứng minh rằng tồn tại một đường tròn đi qua 3 trong số các điểm đã cho sao cho không có điểm nào trong số các điểm đã cho nằm trong hình tròn đó.

Bài 1.9: Cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh ta có thể nối 2n điểm này bởi n đoạn thẳng có hai đầu mút khác màu sao cho chúng đôi một không cắt nhau.

Chia sẻ:

  • Twitter
  • Facebook
Thích Đang tải...

Tagged: cực hạn, nguyên lí cực hạn, tổ hợp

Từ khóa » Nguyên Lý Cực Hạn Trong Tổ Hợp