Hi mọi người,
Mình đọc trong sách có 1 bài toán như sau: Cho các số tự nhiên từ 1 đến 2012. Hỏi có thể chọn ra nhiều nhất bao nhiêu số sao cho tổng của hai số bất kỳ trong chúng không chia hết cho hiệu của nó?
Còn đây là cách giải (của sách):
Nhận thấy, nếu hai số chia cho 3 cùng dư 2 thì hiệu của chúng chia hết cho 3, còn tổng của chúng chia cho 3 dư 1; nên tổng của chúng không chia hết cho hiện của chúng.
Trong các số tự nhiên từ 1 đến 2012, sẽ có 671 số chia cho 3 dư 2 là các số có dạng $3k + 2$ ($k = 0, 1, 2, ..., 670$). Khi đó hai số bất kỳ trong 671 số này có tổng chia 3 dư 1, hiệu chia hết cho 3, nên tổng không chia hết cho hiệu của chúng. Ta sẽ chứng minh rằng chọn được nhiều nhất là 671 số thỏa mãn điều kiện bài toán.
Thật vậy, nếu chọn 672 ( = 671 + 1) số trong các số từ 1 đến 2012, thì trong 672 số này luôn tìm được a, b (a > b) sao cho a - b $\leqslant$ 2 (Thật vậy, giả sử ngược lại thì hiệu giữa số nhỏ nhất và số lớn nhất trong các số đã chọn sẽ không nhỏ hơn 3.671 = 2013. Điều này mâu thuẫn với hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá 2012 - 1 = 2011), nghĩa là a - b bằng 1 hoặc 2.
- Nếu a - b = 1 thì hiển nhiên a + b chia hết cho a - b ( = 1).
- Nếu a - b = 2 thì a + b là số chẵn nên a + b chia hết cho a - b ( = 2).
Như vậy từ 2012 số đã cho không thể chọn được hơn 671 số thỏa mãn điều kiện bài toán. Suy ra số lượng lớn nhất các số phải tìm là 671.
Mình thắc mắc đoạn đầu tiên là có nhất thiết phải đặt 2 số chia cho 3 cùng dư 2 hay không? Tại sao đề bài lại không đặt con số khác, ví dụ như chia cho 3 cùng dư 1 cũng được !?
Mình nghĩ là nếu chọn chia 2 dư 0 hoặc 1 thì hiển nhiên không được, nếu chọn chia 4 dư x hoặc chia 5 dư x ... thì khoảng cách giữa 2 số liên tiếp sẽ lớn, dẫn tới số lượng các số phải tìm ít đi, nên chọn chia 3 dư x sẽ là lựa chọn tốt nhất, phải không nhỉ?
Xin cảm ơn trước.