Chứng minh rằng trong 2n−1 số nguyên dương bất kỳ, luôn tồn tại n số có tổng chia hết cho n.

Để chứng minh rằng trong 2n−1 số nguyên dương bất kỳ, luôn tồn tại n số có tổng chia hết cho n, chúng ta sẽ sử dụng nguyên lý Dirichlet, hay còn gọi là nguyên lý ngăn kéo.

Trước tiên, hãy ký hiệu 2n−1 số nguyên dương mà chúng ta đang xem xét là a1, a2, a3, ..., a(2n−1). Chúng ta sẽ xét các số này theo modulo n. Điều này có nghĩa là chúng ta sẽ tính phần dư của mỗi số khi chia cho n. Các phần dư này sẽ có giá trị từ 0 đến n−1 (tức là có n giá trị khác nhau).

Khi chúng ta lấy phần dư của mỗi số a_i mod n, chúng ta sẽ nhận được các giá trị trong tập {0, 1, 2, ..., n−1}. Tổng cộng có n giá trị khác nhau. Tuy nhiên, chúng ta lại có 2n−1 số để xem xét. Do đó, theo nguyên lý Dirichlet, nếu chúng ta có 2n−1 số và chỉ có n giá trị để phân loại chúng (trong trường hợp này là các phần dư), thì ít nhất một trong các giá trị phần dư đó sẽ phải xuất hiện ít nhất hai lần.

Giả sử rằng một giá trị phần dư r (0 ≤ r < n) xuất hiện k lần trong số a1, a2, ..., a(2n−1). Do có ít nhất một giá trị phần dư xuất hiện ít nhất hai lần, ta có ít nhất k = 2. Giả sử rằng các giá trị có phần dư bằng r là a_{i1}, a_{i2}, ..., a_{ik}, với 2 ≤ k ≤ n.

Chúng ta có thể tạo ra một nhóm các số từ a1, a2, ..., a(2n−1) mà có tổng là chia hết cho n. Cụ thể, chúng ta sẽ chọn k số trong nhóm và một số thêm vào từ các số còn lại để đảm bảo tổng của chúng có phần dư bằng 0 mod n. Chúng ta có thể thực hiện điều này vì tổng của các số với cùng một phần dư sẽ cho một phần dư nhất định trong việc cộng tổng, và với số lượng số lượng lớn như vậy, ta có thể dễ dàng tìm ra n số có tổng chia hết cho n từ tập hợp các phần dư.

Cuối cùng, từ tính chất này, ta có thể kết luận rằng trong 2n−1 số nguyên dương bất kỳ, luôn tồn tại n số mà tổng của chúng chia hết cho n. Điều này hoàn thành chứng minh đề bài.