Bài 1

Chứng minh rằng từ một tập hợp gồm mười số có hai chữ số khác nhau (trong hệ thập phân), luôn có thể chọn ra hai tập con rời nhau sao cho tổng các phần tử của chúng bằng nhau.

Bước 1 trên 4: Đếm số tập con so với số giá trị tổng có thể

Bước trước Bước tiếp

Hiểu nôm na

Số cách chọn một tập con từ mười số này nhiều hơn hẳn số tổng có thể có, nên chắc chắn có những tổng bị lặp lại — đó chính là mầm mống của lập luận Dirichlet.

2^{10}=1024\text{ subsets, sums lie in }[0,945]

Phân tích chi tiết

Gọi $S=\{a_1,\dots,a_{10}\}$ là mười số có hai chữ số khác nhau ( $10\le a_i\le 99$ ). Tập $S$ có đúng $2^{10}=1024$ tập con (kể cả tập rỗng). Tổng của mỗi tập con là một số nguyên không âm, và tổng lớn nhất có thể có nhiều nhất là $90+91+\cdots+99=945$ (tổng của mười số có hai chữ số lớn nhất), nên mọi tổng tập con đều nằm trong $\{0,1,\dots,945\}$ , một tập chỉ có $946$ giá trị có thể.