[Bài toán] Nguyên lý Dirichlet

Bài toán : Cho $2001$ số tùy ý. Chứng minh rằng ta có thể chọn được một hoặc một số số nào đó mà tổng của chúng chia hết cho $2001$.

Lời giải :

Gỉa sử $2001$ số đã cho là $a_1,a_2,...,a_{2001}$.

Xét $2001$ tổng sau :

$$S_1=a_1$$

$$S_2=a_1+a_2$$

$$S_3=a_1+a_2+a_3$$

…

$$S_{2001}=a_1+a_2+...+a_{2001}$$.

Nếu có ít nhất một trong các tổng trên chia hết cho $2001$ thì hiển nhiên ta có điều phải chứng minh.

Gỉa sử không có tổng nào trong các tổng trên chia hết cho $2001$, khi đó số dư trong phép chia mỗi tổng cho $2001$ thuộc tập $A=\left\{1,2,3,...,2000\right\}$.

Theo nguyên lí $Dirichlet$ thì sẽ tồn tại hai tổng có cùng số dư $r$ khi chia cho $2001$ với $r\in A$.

Gỉa sử đó là hai tổng $S_m=a_1+a_2+...+a_m$ và $S_n=a_1+a_2+....a_n$ với $m,n\in \left\{1,2,3,...,2001\right\},m<n$.

Khi đó thì $2001\mid S_n-S_m\Rightarrow 2001\mid a_{m+1}+a_{m+2}+...a_{m+(n-m)}$.

Tức là luôn chọn được các số thỏa yêu cầu đề bài (điều phải chứng minh)