Blog này tổng hợp các bài toán hay, các bài giảng chọn lọc về nhiều chủ đề: đại số, hình học, giải tích, số học và tổ hợp liên quan đến Toán Olympic và Toán thi ĐH.
Thứ Ba, 22 tháng 3, 2016
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
Đăng ký:
Bài đăng (Atom)
Bất đẳng thức tuyển sinh lớp 10 chọn lọc
Trong bài viết này, tác giả giới thiệu một số bài BĐT nhẹ nhàng nhưng ý tưởng tương đối mới, mức độ phù hợp với đề thi tuyển sinh vào lớp...
-
I) Hàm phần nguyên: 1) Định nghĩa Phần nguyên của một số thực x là số nguyên lớn nhất không vượt quá x. Kí hiệu là [x]. 2) Tính chất...
-
Trong thế giới bất đẳng thức , ngoài những bất đẳng thức kinh điển và được áp dụng rất nhiều như bất đẳng thức AM – GM, bất đẳng thức Cauc...
-
1) $(F_n,F_{n+1})=1$ 2) Nếu $n |m $ thì $F_n |F_m$ Ta chỉ cần chứng minh tính chất sau: $F_{m+n}=F_{m-1}F_{n+1}+F_{m}.F_{n}$ Quy nạp th...