Ai giúp mình với......help....

[xtl.vt91]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho hai tập hợp các số nguyên dương phân biệt mà mỗi số đều bé hơn số tự nhiên n đã cho. Chứng minh rằng nếu tổng số phần tử của hai tập hợp không bé hơn n thì có thể chọn trong mỗi tập hợp một phần tử sao cho tổng của chúng bằng n.

 

[nerversaynever]

Giả sử hai tập hợp đó là A có a phần tử x1,x2,..xa, B có b phần tử z1,z2,..zb với a+b>=n, ta xét tập hợp A' cũng có a phần tử y1,y2,..,ya sao cho xi+yi=n. Do a+b>=n và các phần tử của B và A' có giá trị tử 1 đến n-1 nên theo nguyên lý dirichle thì A' và B sẽ có ít nhất một phần tử chung, giả sử đó là yk=zk', khi đó chọn phần tử xk từ tập A và zk' từ tập B ta sẽ có xk+zk'=n,đpcm