Tài liệu dạy ôn của câu lạc bộ Toán THCS - Buổi 16: Nguyên lý dirile, bài toán chi hết

GV: Dương Tiến Mạnh Ngày dạy: Buổi 16 nguyên lý dirile. bài toán chi hết a/ Mục tiêu HS nắm được kiến thức cơ bản về nguyên lý dirichle Biết vận dụng để giải bài toán chi hết B/ Nội dung I/ Kiến thức cơ bản * Nguyên lý: Nếu đem n + 1 con thỏ nhốt vào n lồng thì có ít nhất 1 lồng chứa từ 2 con trở lên II/ Bài tập: Ví dụ 1: CMR: Trong n + 1 số nguyên bất kỳ có 2 số có hiệu chia hết cho n. Giải Lấy n + 1 số nguyên đã cho chia cho n thì được n + 1 số dư nhận 1 trong các số sau: 0; 1; 2; …; n - 1 ị có ít nhất 2 số dư có cùng số dư khi chia cho n. Giả sử ai = nq1 + r 0 Ê r < n aj = nq2 + r a1; q2 ẻ N ị aj - aj = n(q1 - q2) M n Vậy trong n +1 số nguyên bất kỳ có 2 số có hiệu chia hết cho n. Nếu không có 1 tổng nào trong các tổng trên chia hết cho n như vậy số dư khi chia mỗi tổng trên cho n ta được n số dư là 1; 2; …; n - 1 Vậy theo nguyên lý Đirichlet sẽ tồn tại ít nhất 2 tổng mà chi cho n có cùng số dư ị (theo VD1) hiệu cùadr tổng này chia hết cho n (ĐPCM). Bài tập tương tự Bài 1: CMR: Tồn tại n ẻ N sao cho 17n - 1 M 25 Bài 2: CMR: Tồn tại 1 bội của số 1993 chỉ chứa toàn số 1. Bài 3: CMR: Với 17 số nguyên bất kỳ bao giờ cũng tồn tại 1 tổng 5 số chia hết cho 5. Bài 4: Có hay không 1 số có dạng. 19931993 … 1993000 … 00 M 1994 Hướng dẫn - Đáp số Bài 1: Xét dãy số 17, 172, …, 1725 (tương tự VD2) Bài 2: Ta có 1994 số nguyên chứa toàn bộ số 1 là: 1 11 111 … Khi chia cho 1993 thì có 1993 số dư ị theo nguyên lý Đirichlet có ít nhất 2 số có cùng số dư. Giả sử đó là ai = 1993q + r 0 Ê r < 1993 aj = 1993k + r i > j; q, k ẻ N ị aj - aj = 1993(q - k) mà (10j, 1993) = 1 M 1993 (ĐPCM) Bài 3: Xét dãy số gồm 17 số nguyên bất kỳ là a1, a2, …, a17 Chia các số cho 5 ta được 17 số dư ắt phải có 5 số dư thuộc tập hợp{0; 1; 2; 3; 4} Nếu trong 17 số trên có 5 số khi chia cho 5 có cùng số dư thì tổng của chúng sẽ chia hết cho 5. Nếu trong 17 số trên không có số nào có cùng số dư khi chia cho 5 ị tồn tại 5 số có số dư khác nhau ị tổng các số dư là: 0 + 1 + 2 + 3 + 4 = 10 M 10 Vậy tổng của 5 số này chia hết cho 5. Bài 4: Xét dãy số a1 = 1993, a2 = 19931993, … a1994 = đem chia cho 1994 ị có 1994 số dư thuộc tập {1; 2; …; 1993} theo nguyên lý Đirichlet có ít nhất 2 số hạng có cùng số dư. Giả sử: ai = 1993 … 1993 (i số 1993) aj = 1993 … 1993 (j số 1993) ị aj - aj M 1994 1 Ê i < j Ê 1994 ị