Tài liệu Bồi dưỡng học sinh giỏi môn Toán 6 - Chuyên đề 8: Nguyên lí dirichlet

S6-CHUYÊN ĐỀ 8. NGUYÊN LÍ DIRICHLET
PHẦN I. TÓM TẮT LÝ THUYẾT
1. Nội dung nguyên lí
Nếu nhốt (trong đó ) con thỏ vào cái chuồng thì phải có ít nhất một chuồng chứa không ít hơn con thỏ.
Chứng minh
Giả sử ngược lại mỗi chuồng chứa không quá con thỏ thì tổng số thỏ nhốt trong chuồng sẽ không quá con thỏ :Mâu thuẫn với giả thiết là số thỏ bằng .Vậy phải có ít nhất một chuồng chứa không ít hơn con thỏ.
2. Nhận xét
Bản thân nguyên li Dirichlet khá đơn giản và dễ hiểu, tuy nhiên việc ứng dụng n...ùng số dư.Giả sử hai số bị chia trong hai phép chia đó là và (với ). Ta có (.
Bài 1:
Chứng minh rằng có thể tìm được một số có dạng chia hết cho 2012.
Lời giải
Xét dãy số : . Khi chia các số hạng của dãy này cho 2012 sẽ có hai phép chia có cùng số dư. Giả sử hai số hạng của dãy trong hai phép chia đó là và ( với .
ÞHiệu của và chia hết cho 2012 hay (đpcm)
Nhận xét: Phương pháp để giải dạng toán này là tạo ra dãy số (theo cấu tạo số) từ yêu cầu của bài toán (“tạo thỏ”) . Sau đó áp dụng nguy... , chẳng hạn là 
chia cho ( vơi )
 , ta có điều phải chứng minh .
Nhận xét: Phương pháp “tạo thỏ “ trong ví dụ này là dựa vào phép toán cộng và yêu cầu về tính liên tiếp của các số hạng trong dãy ban đầu của đề bài .
Bài 3:
Cho bốn số tự nhiên phân biệt . Chứng minh rằng: 
Lời giải
Chia bốn số phân biệt cho 3 luôn có hai phép chia có cùng số dư
Þhiệu hai số bị chia đó chia hết cho 3 Þtồn tại hiệu hai số trong bốn số chia hết cho 3. Do vậy P chia hết cho 3 (1)
Trong bốn số nếu có hai số ...u chữ số hàng chục đó là (các chữ số hàng trăm, hàng nghìn, .(nếu có ) cũng giống nhau), còn các chữ số hàng đơn vị là dãy 0;1;2;3;;9.
Do đó tổng các chữ số của mỗi số cũng là một dãy 10 số tự nhiên liên tiếp, vì thế tồn tại số có tổng các chữ số chia hết cho 10.
Bài 4:
Cho 12 số tự nhiên khác nhau có hai chữ số. Chứng minh rằng không tồn tại hai số có hiệu là một số có hai chữ số như nhau.
Lời giải
Có 12 số tự nhiên khác nhau, mà chỉ có 11 số dư trong phép chia cho 11, do đó tồn tại hai s...o đó hiệu của chúng chia hết cho 10 (đpcm).
Bài 6:
Chứng minh rằng tồn tại số có dạng 19941994...199400...0 chia hết cho 1995.
Lời giải
Ta có 19941994...199400...0 = 19941994...1994 100...0
Xét 1995 số có dạng: 1994 ; 19941994 ; ... ; .
+) Nếu một trong các số trên chia hết cho 1995 thì dễ dàng có điều phải chứng minh.
+) Nếu các số trên đều không chia hết cho 1995 thì khi chia từng số cho 1995 sẽ chỉ có 1994 khả năng dư là 1 ; 2 ; 3 ; ... ; 1994.
Vì có 1995 số dư mà chỉ có 1994 khả ... nhau nên 1999 mũ bao nhiêu cũng không chia hết cho 104)
Mà dãy số trên có 104 số nên sẽ có ít nhất hai số khi chia cho 104 có cùng số dư.
Gọi hai số có cùng số dư khi chia cho 104 là 1999^a và 1999^b (với a > b)
Ta có: 1999^a - 1999^b ⋮ 104 => 1999^b[1999^(a-b) – 1] ⋮ 104
Mà UCLN(1999^b, 104) là 1 (vì là hai số nguyên tố cùng nhau) nên 1999^(a-b) – 1 ⋮ 104
Đặt k = a – b, ta có 1999^k – 1 ⋮ 104 (đpcm)
Bài 8:
Chứng minh rằng tồn tại một số chỉ viết b...y luận
Bài 1:
Có 10 đội bóng thi đấu với nhau vòng tròn một lượt , mỗi đội phải đấu đúng một trận với mỗi đội khác .Chứng minh rằng vào bất cứ lúc nào cũng có hai đội đã đấu số trận như nhau.
Lời giải
Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội nào đã thi đấu 9 trận . Như vậy mỗi đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9 .Vậy theo nguyên lí Dirichlet phải có ít nhất hai đội có số trận đã đấu như nhau.
Bài 2:
Trong 45 học ...án học viết thư cho nhau trao đổi về 3 vấn đề khoa học , mỗi người đều trao đổi với 16 người còn lại và mỗi cặp 2 người chỉ trao đổi với nhau một vấn đề .Chứng minh rằng có ít nhất 3 nhà Toán học trao đổi với nhau về cùng một vấn đề.
Lời giải
Gọi A là một nhà Toán học nào đó trong 17 nhà Toán học thì A phải trao đổi với 16 người còn lại về 3 vấn đề khoa học ( kí hiệu là vấn đề I,II,III).
Vì 16 = 3.5 + 1 nên A phải trao đổi với ít nhất 5 + 1 = 6 nhà Toán học khác về cùng một vấn đề ( theo nguy... nhà Toán học cùng trao đổi với nhau về một vấn đề ( II hoặc III).
Vậy luôn có ít nhất 3 nhà Toán học trao đổi với nhau về cùng một vấn đề .
Nhận xét: Trong ví dụ trên ta đã phải phân chia bài toán thành hai lớp và sử dụng hai lần nguyên lí Dirichlet : Lần thứ nhất với 16 thỏ và 3 chuồng ; lần thứ hai với 6 thỏ và 2 chuồng.
Bài 4:
Chứng minh rằng tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2013.
Lời giải
Xét 2014 có dạng 1,11,111,., . Theo nguyên lý Dirichlet thì tồn tại hai số ...
Khi đó: 
Trong đó 3 số có 2 số cùng tính chẵn lẻ, chẳng hạn và , thì . Vậy 
Nếu có 3 số lẻ, 2 số chẵn thì chứng minh tương tự ta cũng có 
Vậy trong mọi trường hợp ta đều có (2)
Từ (1), (2) và (9,32)=1 suy ra hay (đpcm).
Bài 6:
Chứng minh rằng trong số bất kì thuộc tập hợp luôn tìm được hai số mà số này là bội của số kia.
Lời giải
Viết n+1 số lấy ra dưới dạng
 trong đó là các số lẻ,
Ta có: . Mặt khác trong khoảng từ 1 đến 2n-1 có đúng n số lẻ nên tồn tại hai số m, n sao cho . Khi đó, t