Nguyên lý Dirichle và nguyên lý cực hạn

Nguyên lý Dirichle và nguyên lý cực hạn Nguyên lý Dirichle và nguyên lý cực hạn là hai nguyên lý có nội dung khá đơn giản, song lại có thể áp dụng rộng rãi trong việc chứng minh các bài toán hình học tổ hợp, số học, đại số, ... Bài viết này sẽ giới thiệu một cách tổng quan về hai nguyên lý này. A.Nguyên lý Dirichle I.Giới thiệu: -Dạng 1: Nếu có một ánh xạ từ tập hợp M có n+1 phần tử vào tập hợp có n phần tử thì có ít nhất 2 phần tử của tập hợp M có cùng một ảnh của tập hợp N qua ánh xạ đó. -Dạng 2: Nếu nhốt N chú thỏ vào n chuồng mà N>nk thì có ít nhất một chuồng nhốt nhiều hơn hai chú thỏ. Mở rộng: nếu chia tập hợp vô hạn các “chú thỏ” vào hữu hạn “chuồng” thì tồn tại ít nhất một chuồng có vô hạn “chú thỏ”. II. Ví dụ: Các bài toán trong phần này sẽ giúp bạn đọc làm quen với cách áp dụng nguyên lý này. Bài toán 1: Cho bảng vuông gồm n x n ô vuông. Mỗi ô vuông ghi một trong các số 0,1,2. CM: không tồn tại bảng vuông nào mà tổng các ô trên hàng ngang, cột dọc và đường chéo là các số khác nhau hoàn toàn. Giải: Giá trị trên cột, hàng, đường chéo có giá trị nhỏ nhất là 0 x n=0 và có giá trị lớn nhất là 2n, mà ta có 2n+2 tổng nhưng chỉ có 2n+1 giá trị (từ 0 đến 2n) nên theo nguyên lý Dirichle phải có ít nhất 2 tổng có giá trị bằng nhau => đpcm. Bài toán 2: Cho hình tròn diện tích S, lấy n điểm bất kỳ (n>2).CMR: có ba điểm tạo thành tam giác có diện tích nhỏ hơn S/k với k là số nguyên lớn nhất nhỏ hơn (n-1)/2 Giải: Ta dễ dàng nghĩ đến việc chia đường tròn thành k phần hình quạt bằng nhau, theo nguyên lý Dirichle, tồn tại 3 điểm thuộc cùng một hình quạt. Gọi ba điểm đó là A,B,C.Ta có: SABC<Shình quạt =S/k (đpcm). Bài toán 3: Bên trong hình tròn bán kính 5 lấy 10 điểm bất kỳ. CM: tồn tại hai điểm có khoảng cách nhỏ hơn 4 (Nhật-97) Giải: đầu tiên ta nghĩ đến việc chia hình tròn thành 9 hình quạt bằng nhau như bài toán 2, nhưng cách chia này sẽ không giải quyết được bài toán vì tồn tại 2 điểm trong hình quạt có khoảng cách lớn hơn 4. Sau một lát suy nghĩ ta nhận thấy không cần phải chia hẹp và dài như thế , từ đó ta có cách chia hợp lý như sau: một hình tròn bán kính 2 đồng tâm với hình tròn ban đầu và 8 hình vành khăn bằng nhau Theo nguyên lý Dirichle thì tồn tại 2 điểm cùng thuộc một phần. . O A B C D Nếu 2 điểm ấy thuộc hình tròn bán kính 1 => đpcm. Nếu 2 điểm ấy thuộc hình vành khăn, bạn đọc có thể chứng minh khoảng các lớn nhất giữa 2 điểm thuộc hình vành khăn là Max{CD,AD,AC} dễ dàng có AC=3 < 4 AD=OA2 +OD2 -2OA.OD.cos45o <4 CD=OC2 +OD2 -2OC.OD.cos45o <4 =>đpcm. Bài 4: Cho 17 điểm trong mặt phẳng ,nối tất cả những điểm lại với nhau và tô màu các đoạn thẳng đó bằng một trong 3 màu xanh,trắng, đen. CM: tồn tại tam giác có 3 cạnh cùng màu. (bạn đọc tự chứng minh ) B.Nguyên lý cực hạn: I.Giới thiệu: -Trong một tập hợp hữu hạn các số thực, luôn luôn có thể chọn một số nhỏ nhất và một số lớn nhất. -Trong trường hợp tập hợp vô hạn các số tự nhiên (thõa mãn một tính chất nào đó) ta có thể chọn được số nhỏ nhất trong tập hợp đó II.Ví dụ: Bài toán 1: Cho n (n>2) đường thẳng trong mặt phẳng, cứ 3 đường bất kỳ thì đồng quy. CM : n đường thẳng ấy đồng quy. Giải: Vừa đọc đề , bạn đọc có thể nghĩ ngay đến việc chứng minh bài toán bằng phương pháp quy nạp. Nhưng với phép quy nạp ta dễ mắc sai lầm trong lúc chứng minh từ k sang k+1 và phép chứng minh không chặt chẽ. Ta sẽ giải quyết bài toán bằng cách sử dụng nguyên lý cực hạn. Giả sử các đường thẳng không đồng quy. Xét các khoảng cách khác 0 từ mỗi điểm đến các đường thẳng không đi qua nó ( tồn tại một điểm như vậy theo giả thiết phản chứng ). Trong các khoảng cách đó, chọn ra đoạn ngắn nhất, giả sử đó là đoạn AH từ điểm A đến đường thẳng d. Qua A có ít nhất có ba đường thẳng đi qua, gọi giao điểm của chúng là B,C,D. Tồn tại hai điểm nằm cùng phía với H, chẳng hạn là C,D.Giả sử C nằm giữa H và D khi đó dễ dàng chứng minh khoảng cách từ C đến AD nhỏ hơn AH (vô lý). Vậy điều giả sử là sai tức là các đường thẳng điều đồng quy. A B C H D E Bài toán 2 Cho tập hợp gồm n điểm ,trong đó bất kỳ đường thẳng nào đi qua hai điểm đó cũng đi qua điểm thứ ba. CM: n điểm đã cho thẳng hàng. (bạn đọc tự giải) Mở rộng : Cho n hình lồi (n>2) sao cho cứ 3 hình lồi bất kỳ có thì có giao khác rỗng. CM n hình lồi đã cho có giao khác rỗng. Đó là nội dung của định lý Hely. (một hình được gọi là hình lồi nếu 2 điểm bất kỳ thuộc hình đó thì đoạn thẳng nối hai điểm thuộc cũng thuộc hình đó) Áp dụng định lý này ta có thể chứng minh các bài toán sau: 1) Cho đa giác lồi có chu vi bằng 1. CM: có thể chứa đa giác trong hình tròn có bán kính là ¼. gợi ý: hình tròn chứa tam giác nhọn có bán kính nhỏ nhất là hình tròn ngoại tiếp, còn tam giác tù là hình tròn đường kính cạnh lớn nhất, ta sẽ cm một đa giác lồi có thể chứa trong hình tròn có bán kính lớn nhất trong số các hình tròn chứa tam giác (có đỉnh là đỉnh đa giác). 2) Cho n hình tròn ,sao cho có thể đặt 1 chiếc dĩa bán kính r cắt 3 đường tròn bất kỳ. CM: có thế tìm được một vị trí đặt chiếc dĩa đó sao cho nó cắt n đường tròn. Bài toán 3: Cho tập hợp gồm n điểm trên mặt phẳng không cùng thuộc một đường thẳng , kẻ các đường thẳng đi qua từng cặp hai điểm trong n điểm đó. CM: tồn tại một đường thẳng đi qua đúng 2 điểm của tập hợp. (bạn đọc tự giải) Bài toán 4: Tìm hàm f:N*àN* thỏa các điều kiện sau: i) f (n+f (n) ) = f (n) ii) tồn tại n0 sao cho f(n0)=1 Giải:Ta sẽ chứng minh f(n)=1 với mọi n Nếu f(a)=1 thì ta có f (a+f (a) ) = f (a) hay f(a+1)=1, tức là f(n)=1 với mọi n>=no. Gọi S là tập hợp các số n sao cho f(n) khác 1.Vì S là hữu hạn nên gọi b là phần tử lớn nhất của S. Ta có : f(b+f(b))=f(b) nên b+f(b) thuộc S mà b+f(b)>b vô lý với cách chọn b. Vậy f(n)=1 với mọi n. Bài toán 5: Giải phương trình nghiệm nguyên dương sau x 3+3y3+9z3=27xyz Giải: Gọi x,y,z là một nghiệmdương của pt đã cho suy ra x,y,z chia hết cho 3 thì x/3,y/3,z/3 cũng là nghiệm của phương trình. tiếp tục ta được x/3n,y/3n,z/3n cũng là nghiệm của phương trình mà trong tập N ta không thể thực hiện được điều này nên x=y=z=0 là nghiệm duy nhất của phương trình. Trong bài toán trên ta đã áp dụng tính chất: trong tập con bất kỳ của tập số tự nhiên ta có thể chọn được phần tử nhỏ nhất. C.Bài tập: Khi giải các bài toán sau, các bạn không nhất thiết phải sử dụng hai nguyên lý trên nhưng nên cố gắng sử dụng chúng như là một cách rèn luyện cho mình Bài 1:CMR với mọi số nguyên dương k tồn tại số nguyên dương m sao cho m3+10 chia hết cho 3k. Bài 2:Cho dãy số nguyên (xn) được xác định bởi công thức truy hồi: x n+k = x n+k-1a1+...+ x n+1ak-1+xnak và k số hạng đầu tiên nguyên. Khi đó với mọi số nguyên dương N; dãy số dư của xn chia cho n sẽ tuần hoàn. Bài 3: Cho a,b,c là nghiệm của phương trình x3+x-1=0.CMR:ap+bp+cp chia hết cho 3 với p là số nguyên tố. (áp dụng bài 2) **Bài 4: Cho 10 tập con ,mỗi tập con 8 phần tử của {1,2,...38}. CM: tồn tại 2 tập có giao lớn hơn hoặc bằng 2 phần tử. Bài 5: Trên mặt phẳng có một vết mực có S>1.CM: luôn tồn tại hai điểm A,B trong vết mực sao cho bình phương khoảng cách giữa chúng là một số nguyên. Bài 6: CM không tồn tại ngũ giác đều có các đỉnh có tọa độ nguyên. mở rộng : tìm tất cả các số tự nhiên n sao cho tồn tại một đa giác đều n cạnh có dỉnh nguyên. Bài 7: Trong một hội nghị ,cứ 2 người bất kỳ thì có người quen chung, cứ 2 người không quen nhau thì có đúng 2 người quen chung. CMR: trong hội nghị này tất cả mọi người đều có số người quen như nhau. Bài 8: CM rằng phương trình 5n2 = 36a2 + 18b2 + 6c2 có nghiệm duy nhất là a = b = c = n = 0 Bài 9: Gọi C là một đa giác 1993 đỉnh có tọa độ nguyên ,không nhất thiết là đa giác lồi. Mỗi cạnh của C không chứa điểm có tọa độ nguyên nào cả (trừ hai đỉnh của C) . CM: có ít nhất một cạnh chứa điểm có tọa độ (x,y) sao cho 2x,2y là những số nguyên lẻ. Bài 10: Cho A={x1,x2,...,xn }với xi là các số thực khác nhau. Cho hàm f : Aà A thỏa mãn trị tuyệt đối của (f(x)-f(y)) không lớn hơn trị tuyệt đối của (x-y). CM: tồn tại k để f(xk)=xk với xk thuộc A. Bài 11:Trong tập hợp n phần tử (n>4) , chọn ra n+1 tập con ,mỗi tập con gồm 3 phần tử. CM có thể tìm 2 tập con mà chúng có chung đúng 2 phần tử. Gợi ý Bài 1: Xét các số n có dạng 3k+2 với k=1,2,...,3k-2+1 thì n3+10 chia hết cho 32 , và chứng minh không có hai số nào đồng dư nhau theo modulo 3k. Bài 2: Gọi yn là dãy số dư của xn khi chia cho N ( yn<N ). Xét Nk+1 bộ (yi,yi+2,...,yi+k) để suy ra có hai bộ trùng nhau (đpcm) Bài 3: Tính dãy Sn=an + bn + cn và dãy Pn=(ab)n + (bc)n + (ab)n rồi áp sụng bài 2. Bài 5: Chia mặt phẳng thành các ô vuông đơn vị rồi tịnh tiến các ô về một ô chuẩn, để suy ra tồn tại hai điểm có bình phương là số nguyên (dựa vào định lý pitago) Bài 6: Gọi ABCDE là ngũ giác đều có cạnh nhỏ nhất, áp dụng tính chất sau: giao điểm các đường chéo của ngũ giác đều cũng là ngũ giác đều và chứng minh các giao điểm đó nguyên => vô lý. mở rộng: n=4 là giá trị duy nhất. Bài 7: chứng minh hai người quen nhau có số người quen bằng nhau trước rồi chứng minh phần còn lại của bài toán Bài 8: xét đồng dư theo mod 16 và sử dụng nguyên lý cực hạn Bài 9: Xét trung điểm của mỗi cạnh Bài 10 : Giả sử /f(xk)-xk/ min .... Bài 11 : Bạn đọc tự chứng minh.