Nguyên tắc Dirichlet

[myhanh]

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.