Chứng minh rằng trong 5 số nguyên bất kì có thể tìm được ba số có tổng chia hết cho 3 nguyên lý ngăn kéo dirichlet
Để chứng minh rằng trong 5 số nguyên bất kỳ có thể tìm được ba số có tổng chia hết cho 3, chúng ta sử dụng nguyên lý ngăn kéo Dirichlet.
Nguyên lý ngăn kéo Dirichlet (hay Pigeonhole Principle) nói rằng nếu người được đặt vào cái lồng, với , thì ít nhất một lồng phải chứa ít nhất hai người.
Giả sử chúng ta có 5 số nguyên bất kỳ. Chia từng số cho 3 và xem phần dư khi chia. Có ba trường hợp:
Nếu có ít nhất 3 số chia hết cho 3, tức là có ít nhất ba số có tổng chia hết cho 3.
Nếu có ít hơn 3 số chia hết cho 3, nhưng có ít nhất 3 số có phần dư 1 khi chia cho 3. Trong trường hợp này, có ít nhất hai số có tổng chia hết cho 3.
Nếu có ít hơn 3 số chia hết cho 3 và ít hơn 3 số có phần dư 1 khi chia cho 3, thì có ít nhất ba số có phần dư 2 khi chia cho 3. Trong trường hợp này, có ít nhất hai số có tổng chia hết cho 3.
Do đó, trong mọi trường hợp, chúng ta đều có ít nhất ba số có tổng chia hết cho 3. Điều này chứng minh theo nguyên lý ngăn kéo Dirichlet