Title Chuyên đề 13. Nguyên lý Dirichlet.pdf ✅

Trang 1/9 CĐ13: NGUYÊN LÝ DIRICHLET Dạng 1: Sử dụng trong bài toán chia hết Dạng 2: Sử dụng trong bài toán về tính chất các phần tử trong tập hợp Dạng 3: Sử dụng trong một số bài toán thực tế Dạng 4: Sử dụng trong một số bài toán về hình học Dạng 1. Sử dụng trong bài toán chia hết Câu 1. (HSG 7 TRƯỜNG THCS VÕ THỊ SÁU 2022 - 2023) Chứng minh rằng nếu 2 1 n  là số nguyên tố n  2 thì 2 1 n  là hợp số. Lời giải Ta có: 2 1 n  ; 2 n ; 2 1 n  là ba số tự nhiên liên tiếp theo Dirichlet có một trong ba số sẽ chia hết cho 3 Mà 2 1 n  là số nguyên tố n  2 nên 2 1 n  không chia hết cho 3 . Mặt khác: với n  2 thì 2 n không là bội của 3 , nên 2 n không chia hết cho 3 . Suy ra: 2 1 n  chia hết cho 3 và 2 1 3 n   với mọi n  2 . Vậy 2 1 n  là hợp số (đpcm). Câu 2. (HSG 7 LIÊN TRƯỜNG 2022 - 2023) 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 2007 . Lời giải Xét 2008 số sau: 2008 1; 11; 111; ;111 11   Theo Dirichle tồn tại ít nhất 2 số chia cho 2007 có cùng số dư Giả sử hai số đó là   111 11 n A    111 11 ( ) k B n k   A B     111 11 111 11 n k 10 .111 11 2007    k n k Mà 10 ; 2007 1  k  111 11 2007 n k    Câu 3. (HSG 7 TP Sầm Sơn, tỉnh Thanh Hóa 2022 - 2023) Chứng minh rằng luôn tồn tại số tự nhiên có dạng 20232023...2023 chia hết cho 23 . Lời giải Xét 23 số tự nhiên trong đó mỗi số được viết liên tiếp từ n số 2023 lại với nhau ( n 1;2;3;...;23 ) Ta được các số: 2023;20232023;202320232023;...;20232023...2023. + Nếu trong dãy có một số chia hết cho 23 thì ta có điều cần chứng minh.
Trang 2/9 + Nếu trong dãy trên không có số nào chia hết cho 23 , thì đem các số đó chia cho 23 có ít nhất 2 số có cùng số dư. + Giả sử hai số đó là: 2023 2023...2023 m so a và 2023 2023...2023 n so b với m n Khi đó a b chia hết cho 23 2023...202300...0 chia hết cho 23 ( có m n số 2023 và 4n chữ số 0 ) 4 2023...2023.10 n chia hết cho 23 . Do 23 là số nguyên tố và 4 10 n không chia hết cho 23 20232023...2023 chia hết cho 23 . Câu 4. (HSG 7 huyện, tỉnh, trường Nông Cống 2022 - 2023) Viết 6 số tự nhiên vào 6 mặt của một con xúc xắc. Chứng tỏ rằng khi ta gieo xúc xắc xuống mặt bàn thì trong 5 mặt có thể nhìn thấy bao giờ cũng tìm được một hay nhiều mặt để tổng các số trên các mặt đó chia hết cho 5 . Lời giải Gọi các số trên 5 mặt là 1 a ; 2 a ; 3 a ; 4 a ; 5 a . Xét 5 tổng: 1 1 S a  ; 2 1 2 S a a   ; 3 1 2 3 S a a a    ; 4 1 2 3 4 S a a a a     ; 5 1 2 3 4 5 S a a a a a      - + Nếu một trong 5 tổng đó chia hết cho 5 thì bài toán đã giải xong. + Nếu không có tổng nào chia hết cho 5 thì tồn tại hai tổng có cùng số dư khi chia cho 5 (vì có 5 tổng mà có 4 số dư khác 0 là 1; 2; 3; 4 ). Nên hiệu của hai tổng đó chia hết cho 5 . + Gọi 2 tổng đó là m S và n S ( 1 5    m n ) thì  –  5 m n S S hay  1 2 1 2 1 2  –     5 m n n n m a a a a a a a a a             . Từ đó suy ra điều phải chứng minh. Câu 5. (HSG 7 tp Vũng Tàu 2021 - 2022) Chứng tỏ rằng tồn tại một số tự nhiên tận cùng là 2022 và chia hết cho 2021 . Lời giải Xét 2022 số có dạng 2022 , 20222022 , ..., 2022...2022 Theo nguyên tắc Dirichlet thì có ít nhất hai số có cùng số dư khi chia cho 2021 Giả sử hai số đó là A  2022...2022 ( n số 2022 ) và B  2022...2022 ( k số 2022 ); n k  2022 2022...2022.10n k n B A    soá chia hết 2021 Mà (2021,10 ) 1 n  Suy ra 2022 2022...2022 k n B A    soá chia hết cho 2021 Vậy luôn tồn tại một số tự nhiên tận cùng là 2022 và chia hết cho 2021. Câu 6. (HSG 7 huyện Tam Dương, tỉnh Vĩnh Phúc, năm học 2022 - 2023) Mỗi ô vuông đơn vị của bảng kích thước 10x10 ( 10 dòng, 10 cột) được ghi một số nguyên dương không vượt quá 10 sao cho bất kỳ hai số nào ghi trong hai ô chung một cạnh hoặc hai ô chung một đỉnh của bảng là hai số nguyên tố cùng nhau. Chứng minh rằng có số được ghi ít nhất 17 lần. Lời giải
Trang 3/9 Trên mỗi hình vuông con, kích thước 2x2 chỉ có không quá 1 số chia hết cho 2 . Cũng vậy, có không quá 1 số chia hết cho 3 . Lát kín bảng bởi 25 hình vuông, kích thước 2x2 , ta thấy có nhiều nhất 25 số chia hết cho 2 và có nhiều nhất 25 số chia hết cho 3 . Do đó, có ít nhất 50 số còn lại không chia hết cho 2 , cũng không chia hết cho 3 . Vì vậy, chúng phải là một trong các số 1; 5; 7 . Từ đó, theo nguyên lý Dirichlet, có ít nhất một số trong các số 1; 5; 7 xuất hiện ít nhấ 17 lần. Câu 7. (HSG 7 huyện Vĩnh Tường 2015 - 2016) Chứng minh rằng: Trong 45 số tự nhiên liên tiếp tồn tại 9 số có tổng chia hết cho 45 . Lời giải Ta có 45 số tự nhiên liên tiếp chia cho 45 ta được các số dư là 0,1,2,3,...,44 Do 1 2 3 ... 9 45      Suy ra các số chia cho 45 theo thứ tự dư: 1,2,3,...,9 thì tổng của 9 số này chia hết cho 45 . Câu 8. Cho dãy số gồm 5 số tự nhiên bất kì 1 2 3 4 5 a a a a a , , , , . Chứng minh rằng tồn tại một số chia hết cho 5 hoặc tổng của một số số liên tiếp trong dãy đã cho chia hết cho 5 . Lời giải: Ta sẽ thành lập dãy số mới gồm 5 số sau đây: 1 1 S a  . 2 1 2 S a a   . 3 1 2 3 S a a a    . 4 1 2 3 4 S a a a a     . 5 1 2 3 4 5 S a a a a a      . Nếu một trong các số S i i  1;2;3;4;5 chia hết cho 5 thì bài toán đã được chứng minh. Nếu không có số nào chia hết cho 5 thì khi đem chia các số i S cho 5 sẽ được số dư có giá trị từ 1 đến 4 . Có 5 số dư mà chỉ có 4 giá trị ( 5 thỏ, 4 lồng). Theo nguyên tắc Điriclê ít nhất phải có 2 số dư có cùng giá trị. Hiệu của chúng chia hết cho 5 . Hiệu này chính là tổng các i a liên tiếp nhau hoặc là i a nào đó. Câu 9. 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 2016 . Lời giải: Xét 2017 số có dạng 1;11;...;11...111; 11...11 . Theo nguyên tắc Đirichlê thì tồn tại hai số có cùng số dư khi chia cho 2016 . Giả sử hai số đó là: A 11...1 ( n chữ số 1 ); B ... 11 1 ( k chữ số 1 ) (với k n  ) Khi đó 11...1.10k A B  ( n k  chữ số 1 ) A B chia hết cho 2016 . Do ( ) 2016;10 1 k  Nên C  11...1 ( n k  chữ số 1 ) chia hết cho 2016 . Câu 10. Cho các số tự nhiên từ 1 đến 2012 . Hỏi có thể chọn ra được nhiều nhất bao nhiêu số sao cho tổng của hai số bất kỳ trong chúng không chia hết cho hiệu của nó. Lời giải
Trang 4/9 + Ta thấy, nếu hai số chia cho 3 cùng dư 2 thì hiệu của chúng chia hết cho 3 và tổng của chúng chia 3 dư 1 nên tổng của chúng không chia hết cho hiệu của chúng. + Trong các số tự nhiên từ 1 đến 2012 sẽ có 671 số chia cho 3 dư 2 là các số có dạng 3 2 k  ( 0,1,2,...,670) k  Khi đó hai số bất kỳ trong 671 số này có tổng chia 3 dư 1 , hiệu chia hết cho 3 nên tổng không chia hết cho hiệu của chúng. Ta chứng minh rằng chọn được nhiều nhất 672 số trong các số từ 1 đến 2012 , thì trong 672 số này luôn tìm được hai số ab, ( ) a b  sao cho a b   2 . Thật vậy, giả sử ngược lại thì hiệu giữa số nhỏ nhất và số lớn nhất trong các số đã cho sẽ không nhỏ hơn 3.671 2013  (trái với giả thiết hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá 2012 1 2011   ). Do đó a b  1 hoặc. + Nếu a b  1 thì a b a b      + Nếu a b   2 thì a b  là số chẵn, nên a b   2 hay a b a b      Như vậy các số tự nhiên từ 1 đến 2012 không thể chọn được hơn 671 số thỏa mãn điều kiện bài toán. Suy ra số lượng lớn nhất các số phải tìm là 671 . Dạng 2. Sử dụng trong bài toán về tính chất các phần tử trong tập hợp Câu 1. (HSG 7 Thành Phố Ninh Bình 2022 - 2023) Cho 5 số dương đôi một khác nhau sao cho mỗi số không có ước nguyên tố nào khác 2 và 3 . Chứng minh rằng trong 5 số đó tồn tại hai số mà tích của chúng là một số chính phương. Lời giải Mỗi số trong 5 số có dạng 2 3 x y  trong đó x y, là số tự nhiên khác 0 . ( ; ) x y chỉ có thể (Chẵn, Chẵn); (Lẻ, Lẻ); (Chẵn, Lẻ); (Lẻ, Chẵn) vì có 5 số mà chỉ có 4 dạng nên tồn tại 2 số cùng một dạng nên tích 2 số này là số chính phương. Câu 2. (HSG 7 huyện Gia Viễn, tỉnh Ninh Bình 2022 - 2023) Một cái hộp đựng 60 quả bóng giống nhau, gồm ba màu: màu đỏ, màu xanh và màu vàng. Trong đó có 18 quả bóng màu đỏ và 25 quả bóng màu vàng. Hỏi cần phải lấy ra ngẫu nhiên ít nhất bao nhiêu quả bóng để chắc chắn rằng lấy ra được 2 quả bóng xanh? Lời giải Số quả bóng màu xanh là: 60 18 25 17    (quả). Trường hợp xấu nhất: Ta lấy ra được 25 quả bóng màu vàng, 18 bóng màu đỏ và 1 quả bóng màu xanh. Khi đó, ta cần lấy thêm 1 quả bóng nữa thì chắc chắn có được 2 quả bóng màu xanh. Vậy cần lấy ít nhất là: 25 18 1 1 45     quả bóng để thỏa mãn yêu cầu bài toán. Câu 3. (HSG 7 , Trường THCS Lý Tự Trọng 2018-2019 ) Trong một bảng ô vuông gồm có 5 5  ô vuông, người ta viết vào mỗi ô vuông chỉ một trong 3 số 1; 0 ; 1 . Chứng minh rằng trong các tổng của 5 số theo mỗi cột, mỗi hàng, mỗi đường chéo phải có ít nhất hai tổng số bằng nhau. Lời giải Ta có 5 cột, 5 hàng và 2 đường chéo nên sẽ có 12 tổng Mỗi ô vuông chỉ nhận một trong 3 số 1; 0 hoặc 1 nên mỗi tổng chỉ nhận các giá trị từ  5 đến 5 . Ta có 11 số nguyên từ  5 đến 5 là –5; 4; 3; 2; 1;0;1;2;3;4;5     . Vậy theo nguyên lý Dirichle phải có ít nhất hai tổng bằng nhau (đpcm).