Nguyên tắc Dirichlet

myhanh · 11-11-2007, 06:52 PM

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.

peanux · 14-11-2007, 01:44 PM

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.

myhanh · 14-11-2007, 03:14 PM

Bài giải của Peanux thật tuyệt vời! Bài thứ hai có cao thủ nào ra tay không?

myhanh · 21-11-2007, 04:14 PM

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

phanthuyen · 21-11-2007, 07:19 PM

Trích:

Nguyên văn bởi myhanh

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

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 ^^

myhanh · 21-11-2007, 10:01 PM

Uh còn nhiều lắm nhưng anh không nhớ để chủ nhật này về quê chép ké của thằng em.

chinhlh · 22-11-2007, 09:29 PM

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.

myhanh · 23-11-2007, 06:52 AM

Em thử post bài giải của em lên thử xem! Cho anh tham khảo học hỏi với

chinhlh · 23-11-2007, 12:03 PM

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.

myhanh · 23-11-2007, 01:35 PM

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ở:

Trích:

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.

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