Nguyên tắc Dirichlet
 

Chủ Nhật vừa qua em myhanh có hỏi myhanh một trong đề thi học sinh giỏi cấp huyện năm vừa rồi có liên quan đến nguyên tắc Dirichlet nên sẵn đây myhanh chia sẻ lại những điều liên quan đến nguyên tắc này.
1.Nguyên tắc:
Đặt n+1 vật vào trong n ngăn kéo thì tồn tại ít nhất một ngăn kéo có ít nhất 2 vật
2. Các hệ quả:
2.a Hệ quả 1:
Đặt n*k+1 vật vào trong n ngăn kéo thì tồn tại ít nhất một ngăn kéo có ít nhất k+1 vật.
2.b Hệ quả 2:
Đặt các đoạn thẳng ai (i=1,...,n) trên một đoạn thẳng AB có độ dài a. Gọi L=tổng độ dài các đoạn ai. Nếu L >= k*a+1 thì tồn tại điểm M trên AB sao cho M được phủ bởi ít nhất k+1 đoạn trong các đoạn ai trên.
2.c Hệ quả 3:
Cho hình F có diện tích S. Trên hình F bố trí các hình hữu hạn các hình Fi có diện tích Si. Gọi SS= tổng các Si. Nếu SS >= k*S+1 thì tồn tại điểm M thuộc F sao cho M được phủ bởi ít nhất k+1 hình Fi ở trên.
Mệnh đề phản đảo ở hệ quả này thường được sử dụng:
Tồn tại M thuộc F sao cho không có hình Fi nào ở trên phủ M nếu SS < S.
Sau đây là một số bài tập áp dụng không biết có cao thủ nào ra tay không?
1. Cho 2004 số nguyên dương a1, a2, ... , a2004 có tổng bằng 4008. Không có số nào lớn hơn 2004. Chứng minh rằng trong 2004 số trên có thể tìm được một bộ số gồm một, hai hay nhiều hơn mà tổng của các số trong bộ này bằng 2004.
2. Cho ngũ giác lồi trong mặt phẳng toạ độ vuông góc. Các đỉnh của ngũ giác này là các đỉnh nguyên ( hoành độ và tung độ nguyên). Chứng minh rằng tồn tại ít nhất một điểm nguyên trên cạnh hay bên trong ngũ giác ngày.

Ðề: Nguyên tắc Dirichlet
 

Peanux xin tham gia giải bài số 1 như sau:
Nếu a1, a2, ..., a2004 không có hai số nào khác nhau thì từ:
a1+a2+...+a2004=4008 ta có:
a1=a2=a3=...=a2004=2. Từ đây ta dễ dàng suy ra điều phải chứng minh.
Nếu a1, a2, ..., a2004 tồn tại ít nhất có hai số khác nhau. Do vai trò như nhau của các số này nên ta giả sử hai số khác nhau này là a1 < a2.
Ta xét các tổng sau:
S1=a1
S2=a2
S3=a1+a2
S4=a1+a2+a3
.......................
S2004=a1+a2+...+a2003
Ta có Si>Sj nếu 1<=j<i<=2004 và Sk < 4008 k=1,..,2004 (1)
Giả sử trong các số S1, S2, ..., S2004 có số chia hết cho 2004 giả sử là Sn. Kết hợp (1) ta có Sn=2004 đây là điều phải chứng minh.
Trong trường hợp các số S1, S2, ..., S2004 không có số nào chia hết cho 2004. Vì có 2004 số mà chỉ có 2003 số dư nên phải có hai số cùng số dư ( theo nguyên tắc Dirichlet). Giả sử hai số này là Si và Sj (i>j) thì ta có Si-Sj chia hết cho 2004, Si-Sj < 4008 do đó Si-Sj =2004. Xem lại một chút ta thấy Si-Sj cũng là tổng của một số số trong a1,..., a2004 vì Si không thể là S2 và Sj không thể là S1 do S2-S1=a2-a1 < 2004.

Ðề: Nguyên tắc Dirichlet
 

Ðề: Nguyên tắc Dirichlet
 

Lâu quá các cao thủ ẩn danh hết nên myhanh cũng đành ra tay thôi
Tọa độ mỗi đỉnh của ngũ giác có dạng (i,j) i,j là các số nguyên. Cặp (i,j) thuộc vào 1 trong 4 trường hợp (chẵn, chẵn), (chẵn,lẻ), (lẻ, chẵn), (lẻ, lẻ). Vì có 5 đỉnh mà có 4 trường hợp nên theo nguyên tắc Dirichlet thì có ít nhất hai đỉnh có cùng tính chất. Xét trung điểm của đoạn thẳng nối hai đỉnh này. Trung điểm này là một điểm nguyên và điểm này nằm trên cạnh của ngũ giác lồi hoặc bên trong ngũ giác lồi. Như vậy ta có điều phải chứng minh

Ðề: Nguyên tắc Dirichlet
 

trùi ui, bùn anh myhanh ghê chưa, em nhỏ đang suy nghĩ ngon lành. Mà thôi kệ, dù sao cũng nhức óc mà chưa nghĩ ra vấn đề :P. Bài khác đi anh ^^

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Anh Myhanh giai bai nay quá đẹp, ngắn gọn, dễ hiểu. Thật khâm phục. Dựa vào cách giải này chúng ta chứng minh được một kết quả mạnh hơn. Tồn tại một điểm nguyên nằm bên trong ngũ giác. Từ đó đi đến một bài toán tổng quát khác. Cảm ơn anh Myhanh đã post lời giải rất hay này.

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Nếu M và N có cùng tính chất, ta viết M~N.

Giả sử ABCDE là ngũ giác lồi đã cho và A~B. Nếu trong ba điểm C,D,E có một điểm cùng tính chất với A thì ta tìm được một đường chéo với hai đầu mút có cùng tính chất và trung điểm của đường chéo này là một điểm nguyên nằm bên trong ABCDE. Bây giờ xét trường hợp C,D,E khác tính chất với A. Gọi F là điểm nguyên trên cạnh AB và gần A nhất. Như vậy, F không cùng tính chất với A. Trong năm điểm AFCDE có ít nhất hai điểm có cùng tính chất, đó là C~D hoặc D~E ( Nếu điểm F tham gia vào việc này thì ta có ngay kết luận).
TH1. C~D. Gọi G là điểm nguyên trên cạnh CD và khác tính chất với C. Trong 5 điểm AFCGE có ít nhất hai điểm cùng tính chất, nếu đó không phải là hai đầu mút của đường chéo CE thì một trong hai điểm F, G phải tham gia vào và ta có kết luận.
TH2. D~E. Gọi H là điểm nguyên trên cạnh DE và khác tính chất với E. Phần còn lại được lập luận tương tự như trên.

Bài toán tổng quát: Chứng minh rằng bên trong một đa giác lồi n đỉnh nguyên, tồn tại ít nhất [(n-3)/2] điểm nguyên. Trong đó [x] là số nguyên lớn nhất không lớn hơn x.

Ðề: Nguyên tắc Dirichlet
 

Cách suy nghĩ của chinhlh rất hay và táo bạo cần phát huy nhưng chứng minh của em có điểm sơ hở:

AE là cạnh chứ không là đường chéo nha!

Re: Nguyên tắc Dirichlet
 

Thưa anh, khi đó BE là đường chéo. Hiện giờ em chưa vẽ được một 7-giác lồi nguyên nào mà có đúng hai điểm nguyên nằm bên trong. Anh có thể giúp em không? .

Ðề: Nguyên tắc Dirichlet
 

Ðề: Nguyên tắc Dirichlet
 

Một bài mới đây xin mời các bạn yêu toán học nhảy vào nha:
Trong một hình vuông cạnh 1 đv, người ta đặt 51 điểm. Chứng minh rằng luôn luôn tìm được ba điểm nằm trong một đường tròn có bán kính không lớn hơn 1/7 đv.

Re: Nguyên tắc Dirichlet
 

Chia hình vuông ban đầu thành 25 hình vuông nhỏ bằng cách chia mỗi cạnh thành 5 đoạn bằng nhau. Tồn tại ít nhất môt hình vuông chứa 3 điểm. Đường tròn ngoại tiếp hình vuông ấy có bán kính 1/5căn 2 nhỏ hơn 1/7.

Ðề: Nguyên tắc Dirichlet
 

Ðề: Nguyên tắc Dirichlet
 

Em thấy Chinh giải vậy là quá rõ và quá dễ hiểu rồi mà ... Nhìn mọi người làm toán thấy thích mê luôn, mặc dù mình chẳng biết làm :(

Re: Nguyên tắc Dirichlet
 

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Đề thi học sinh giỏi cấp huyện của anh Myhanh còn khó hơn cả đề thi HSG cấp tỉnh nữa. Sao kỳ lạ vậy nhỉ.

Re: Nguyên tắc Dirichlet
 

Để giải bài toán trên, em xin đưa ra một bổ đề sau.
Trong mặt phẳng cho một dãy các đường thẳng song song, trong đó hai đường kề nhau thì cách nhau một khoảng r>0. Khi đó, mỗi đường tròn đường kính R sẽ cắt ít nhất [R/r]-1 đường thẳng trên và nếu nếu có một đường thẳng tiếp xúc với đường tròn này thì con số sẽ là [R/r].

Re: Nguyên tắc Dirichlet
 

Giả sử bên trong đường tròn đường kính 3 dv có n đường tròn nhỏ đường kính . Tồn tại số đủ lớn sao cho ( Dùng tính chất giới hạn của dãy số). Xét một dãy các đường thẳng song song với , hai đường liên tiếp cách nhau một khoảng , và trong số đó có hai đường thẳng tiếp xúc với đường tròn bự. Gọi là tập hợp gồm đường thẳng nằm trong. Mỗi đường tròn nhỏ cắt ít nhất đường thẳng trong . Từ đó suy ra rằng có ít nhất một đường thẳng cắt không ít hơn đường tròn nhỏ và con số này lớn hơn 8.

Re: Nguyên tắc Dirichlet
 

.

.

.

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Đọc bài của anh Myhanh em chợt nhớ đến ngày xưa. Lúc đó em học lớp Toán của thầy Huy. Mỗi bài thầy ra tụi em giải cả tuần, cả trang giấy. Thầy giải có mấy dòng và chỉ trong vài nốt nhạc. Bài sau em sẽ rút kinh nghiệm. Anh hay thật, Ngày xưa anh cũng học trong đội Toán đúng không? Nếu vậy anh là bậc tiền bối rồi. Xin được anh chỉ dạy thêm.

Re: Nguyên tắc Dirichlet
 

Anh Myhanh có cách chứng minh sơ cấp cho hệ quả thứ hai của nguyên lý Dirichlet không? Em chỉ biết kiểu chứng minh dùng tích phân Lesbegue thôi và đây là lĩnh vực toán sơ cấp nên em nghĩ rằng có cách chứng minh đơn giản hơn.

Ðề: Nguyên tắc Dirichlet
 

Đâu có ngày xưa anh có học Toán nhưng anh thi Tin nên không có thời gian khổ luyện nên bây giờ chỉ nhớ bao nhiêu thì xào bấy nhiêu thôi. Anh hồi đó học chỉ biết thôi chứ không chứng minh.
Là chứng minh như bài trước đó phải không?

Re: Nguyên tắc Dirichlet
 

Dạ không phải. Chứng minh đó sử dụng các kiến thức về độ đo và tích phân Lesbegue. Anh còn bài nào khác không? Em muốn luyện tập thêm. Học một mình buồn lắm. Coi như anh là thầy, tụi em là học trò đi.

Ðề: Nguyên tắc Dirichlet
 

Đâu có thầy trò gì ở đây! Cùng nhau luyện mà!
Bài khác nè:
Cho một hình tròn bán kính R=16 đv. Người ta bố trí 650 điểm trong hình tròn này. Chứng minh rằng chúng ta luôn tìm được một vành tròn có bán kính trong R1=2 đv, bán kính ngoài R2=3 đv chứa không ít hơn 10 điểm.

Re: Nguyên tắc Dirichlet
 

Giả sử X là một điểm trong 650 điểm đã cho. Ta dựng một vành tròn (C) bán kính trong và ngoài là 2 và 3. Khi đó, mỗi điểm trong vành tròn (C) cách X một khoảng cách lớn hơn 2 nhỏ hơn 3. Do đó, làm ngược lại, mọi vành tròn tâm A (A thuộc (C) bất kỳ) đều phủ X.

Tại mỗi điểm trong 650 điểm trên ta có một vành tròn. tất cả chúng nằm trong hình tròn bán kính 19. Tổng diện tích của 650 vành tròn này là . Theo hệ quả 3, tồn tại ít nhất một điểm M được phủ bởi không ít hơn vành tròn, và con số này lớn hơn 9. Cả 10 tâm của 10 vành tròn này đều cách M từ hai đến ba đơn vị.

Re: Nguyên tắc Dirichlet
 

Như vậy là anh Myhanh đã ra đề áp dụng đủ 3 hệ quả rồi. Bài này cũng ghê thật. Em phải đọc kỹ phần lý thuyết phía trước mới giải được. Cách giải cũng giống như bài trước nhưng cần phải suy luận ngó trước ngó sau. Bài của anh rất hay.
Em xin góp thêm một bài (em chưa giải, mới đọc đề thấy hay nên post lên):

Cho S là một tập gồm 101 số nguyên dương khác nhau từ 1 đến 200. Chứng minh rằng có thể chọn ra x,y,z thuộc S sao cho x+y=z.

Ngày xưa, khi em thi HSG quốc gia, người ta ra bài toán tô màu. Đó là một hệ quả của bài toán này. Bây giờ nhìn lại thấy hồi đó mình kém quá.

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Dạ, đúng phải khác nhau. Em ghi thiếu. Thành thật xin lỗi

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Dạ có. Tương tự như vậy em xin đưa ra hai bài toán sau:

Bài 1: Cho A là một tập gồm 10 số tự nhiên khác nhau từ 1 đến 100. Chứng minh rằng có thể lấy ra hai tập con rời nhau của A sau cho tổng của các phần tử của hai tập này là bằng nhau.

Bài 2: Trong mặt phẳng cho 25 điểm. Biết rằng với ba điểm bất kỳ luôn tồn tại hai điểm mà khoảng cách giữa chúng nhỏ hơn 1. Chứng minh rằng có một hình tròn bán kính 1 mà bên trong hình tròn này có không ít hơn 13 điểm.

Re: Nguyên tắc Dirichlet
 

Anh Myhanh có biết kết quả thi HSG của trường mình đợt vừa rồi không? Và khi nào sẽ tổ chức thi vòng hai? Khi nào có đề, anh post lên cho tụi em tham khảo với.

Ðề: Nguyên tắc Dirichlet
 

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Anh Myhanh giải bài 2 quá chính xác và kỹ lưỡng rồi. Nhưng anh đã gõ thiếu vài chữ : " có ít nhất một chuồng chứa không ít hơn 13 con". Anh Myhanh post tiếp một bài nữa đi. Em đang tìm thêm vài bài toán hay về Dirichlet.

Ðề: Nguyên tắc Dirichlet
 

Re: Nguyên tắc Dirichlet
 

Sao topic này nhìn quanh đi quẩn lại chỉ có vài người tham gia vậy anh Myhanh?