Chứng minh rằng

Question

1.Chứng minh rằng trong 100 số tự nhiên bất kì bao giờ cũng có thể chọn ra hai số mà hiệu của chúng chia hết cho 99.

Answer 1

Đây là một bài toán điển hình về nguyên lý hồi đủ (Pigeonhole Principle). Ta có thể chứng minh như sau:

Giả sử ta có 100 số tự nhiên bất kì. Khi chia cho 99, mỗi số sẽ cho phần dư từ 0 đến 98. Tức là có 99 phần dư khác nhau.

Theo nguyên lý hồi đủ, nếu ta chia 100 số này cho 99, thì ít nhất phải có hai số cho cùng một phần dư. Đặt hai số này là a và b (với a > b), và cả hai đều chia cho 99 đều cho cùng một phần dư.

Vậy a - b sẽ chia hết cho 99. Điều này chứng tỏ rằng trong 100 số tự nhiên bất kì, luôn có thể chọn ra hai số mà hiệu của chúng chia hết cho 99.