[Bài toán] Tổ hợp

Bài toán (Đề nghị Olympic 30-4 toán 10 năm 2011 THPT Chuyên Lê Hồng Phong TpHCM) Chứng minh rằng trong $17$ số nguyên tùy ý ta luôn chọn được $9$ số có tổng chia hết cho $9$.

Lời giải :

Bổ đề : Trong $5$ số nguyên tùy ý thì luôn tồn tại $3$ số có tổng chia hết cho $3$

Chứng minh bổ đề :

Nếu như trong $5$ số đã cho có nhiều hơn $3$ số có cùng số dư khi chia cho $3$ thì hiển nhiên ta có điều phải chứng minh.

Nếu như trong $5$ số đã cho có ít hơn $3$ số có cùng số dư khi chia cho $3$ thì sẽ tồn tại ba số chia $3$ dư $0,1,2$. Suy ra tổng của ba số này chia hết cho $3$.

Bổ đề được chứng minh.

Trở lại bài toán :

– Chọn ra $5$ số nguyên bất kì trong $17$ số đã cho thì theo bổ đề luôn tồn tại $3$ số có tổng chia hết cho $3$. Gọi tổng đó là $A_1=a_1+a_2+a_3$

– Trong $14$ số nguyên còn lại thì chọn ra $5$ số, sẽ có $3$ số có tổng chia hết cho $3$. Gọi tổng đó là $A_2=a_4+a_5+a_6$

– Trong $11$ số nguyên còn lại tiếp tục chọn ra $5$ số thì sẽ có $3$ số có tổng chia hết cho $3$. Gọi tổng đó là $A_3=a_7+a_8+a_9$.

– Trong $8$ số nguyên còn lại thì lại chọn ra $5$ số, tồn tại $3$ số trong chúng có tổng chia hết cho $3$. Gọi tổng đó là $A_4=a_{10}+a_{11}+a_{12}$.

– Trong $5$ số nguyên còn lại thì tồn tại $3$ số có tổng chia hết cho $3$. Gọi tổng đó là $A_5=a_{13}+a_{14}+a_{15}$

Do $A_1,A_2,A_3,A_4,A_5$ đều chia hết cho $3$ nên $A_i\equiv 0,3,6(mod9)$ với $i=1,2,3,4,5$

Nếu có nhiều hơn $3$ số trong $5$ số $A_i$ có cùng số dư khi chia cho $9$ thì hiển nhiên tổng ba số trong chúng chia hết cho $9$. Gỉa sử $9\mid A_1+A_2+A_3\Rightarrow 9\mid (a_1+a_2+...+a_9)$.

Nếu có ít hơn $3$ số trong $5$ số $A_i$ có cùng số dư khi chia cho $9$ thì sẽ tồn tại $3$ số khi chia cho $9$ và dư $0,3,9$. Khi đó tổng của ba số này sẽ chia hết cho $9$. Gỉa sử $9\mid A_1+A_2+A_3\Rightarrow 9\mid (a_1+a_2+...+a_9)$.

Từ đây ta có điều phải chứng minh.