Cho n+1 số tự nhiên khác nhau nhỏ hơn 2n. CMR: Luôn chọn được ba số mà tổng hai số này bằng số kia.
Nguyên lý Dirichlet
#1
Đã gửi 23-11-2017 - 09:53
#2
Đã gửi 05-01-2018 - 20:03
Gọi tập hợp A gồm các phần tử a1,a2,a3,...,an+1.(giả sử 2n>an+1>an>an-1>...>a1), tập hợp A có n+1 phần tử khác nhau
Gọi tập hợp B gồm các phần tử a2-a1,a3-a1,...,an+1-a1
Theo điều giả sử trên thì tập hợp B có n phần tử khác nhau, mỗi phần tử bé hơn 2n.
Từ đó suy ra tập hợp A và tập hợp B có tất cả n+1+n=2n+1 phần tử khác nhau mà từ 1 đến 2n chỉ có 2n số
nên theo nguyên lý dirichlet tồn tại ít nhất 2 số bằng nhau.
Giả sử nếu cả 2 số bằng nhau trên đều thuộc A thì vô lý theo điều giả sử, đều thuộc B thì vô lý vì B gồm tất cả n phần tử khác nhau.
Vậy 1 trong 2 số trên phải thuộc A, số còn lại thuộc B.
Giả sử 2 số đó là ax thuộc A (x chạy từ 1 đến n+1), ay-a1 thuộc B (y chạy từ 2 đến n+1)
Ta có:ax = ay-a1 => ax + a1 = ay
Vậy ta luôn chọn được ba số mà tổng hai số này bằng số kia (đpcm)
- eLcouQTai, ha1024, maihoctoan123 và 1 người khác yêu thích
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh