Nguyên lí Dirichlet và cách giải bằng tổng quát bài toán

Giải. Ta giải bài toán tổng quát sau

Cho hai dãy hữu hạn các số nguyên dương như sau:
$x_1 \le x_2 \le ..\le x_m\le n$; $y_1 \le y_2\ le...\le y_n \le m$ Khi đó tồn tại các chỉ số
$1 \le i_1 \le i_2 \le m; 1\le j_1 \le j_2 \le n$ sao cho:

$\sum_{i=i_1}^{i_2}x_i=\sum_{i=j_1}^{j_2}y_j$

Đặt: $a_p=\sum_{i=1}^{p}x_i (p \in Z, 1\le p \le m), b_q=\sum_{j=1}^{q}y_j(q \in Z, 1 \le q\le n)$

Vai trò của các số trên là như nhau nên ta có thể giả sử: $a_m \le b_n$

Lúc đó với mỗi p nhận giá trị từ 1 đến m tồn tại f(p) là chỉ số bé nhất mà $a_p \le b_{f(p)}$. Xét m hiệu:

$b_{f(1)}-a_1; b_{f(2)}-a_2;.... b_{f(m)}-a_m.$

Ta chứng minh mọi hiệu đều bé hơn m. Thật vậy nếu có chỉ số p nào đó sao cho $m \le b_{f(p)}-a_p$ thì $m<b_{f(p)}$ suy ra f(p)>1 và
$m \le b_{f(p)-1}+y_{f(p)}-a_p$ nên $0 \le m-y_{f(p)} \le b_{f(p)-1}-a_p$ nên $a_p\le b_{f(p)-1}$ (mâu thuẫn)

Bây giờ nếu có 1 trong các $b_{f(i)}-a_i=0$ thì ta có cách chọn $i_1=j_1=1; i_2=i, j_2=f(i)$ thoả mãn đề bài

Nếu không có hiệu nào bằng không thì theo nguyên lí dirichlet tồn tại 2 hiệu bằng nhau tức là có r,s thoả mãn:

$b_{f(s)}-a_s=b_{f(r)}-a_r$ hay $b_{f(s)}-b_{f(r)}=a_s-a_r$

Chọn $i_1=r+1; i_2=s j_1=f(r)+1, j_2=f(s)$ ta cũng có đẳng thức đề bài.

Vậy ta có điều phải chứng minh.

Nhận xét: -Đôi khi tổng quát hoá bài toán lại là cách hữu hiệu để giải một bài toán rườm rà nào đó.
-Ta có thể thấy rằng mấu chốt của bài toán là giả sử $a_m \le b_n$ nếu như $b_n \le a_m$ thì sao ? do ta đã nói không mất tính tổng quát có nghĩa là nếu $b_n \le a_m$ thì chỉ việc thay x,z,m,i,p bởi y,b,n,j,q ta vẫn thu được lời giải chính xác.
- Chỉ số bé nhất f(p) chính là điều kiện chặt để giải bài toán ở đây ta đã dùng nguyên lí cực hạn
- Còn chứng minh mọi hiệu bé hơn m là để dùng dirichle