Bài 4
Cho và là các số nguyên dương. Gọi là -phân biệt nếu tồn tại một tập gồm số nguyên dương khác nhau nhỏ hơn , không có hai tập con khác nhau và có tổng các phần tử trong bằng tổng các phần tử trong . (a) Chứng minh là -phân biệt. (b) Chứng minh không là -phân biệt.
Bước 3 trên 4: Áp dụng nguyên lý Dirichlet lần thứ nhất
Phân tích chi tiết
Giả sử tồn tại chín phần tử và sắp xếp s_1<...<s_9<100. Các tập con có kích thước từ ba đến sáu có tổng đôi một khác nhau và nằm giữa tổng ba phần tử nhỏ nhất và tổng sáu phần tử lớn nhất. Vì có 420 tập, hiệu hai tổng biên ít nhất là 419.