Nguyên lí Đi-rích-lê – Bồi dưỡng HSG lớp 6

Nguyên lí Đi-rích-lê phát biểu như sau:  “Nếu có m vật đặt vào n cái ngăn kéo và m > n thì có ít nhất một ngăn kéo chứa ít nhất hai vật”.

Nguyên lí Đi-rích-lê chỉ giúp ta chứng minh được sự tồn tại “ngăn kéo” chứa ít nhất hai vật mà không chỉ ra được đó là “ngăn kéo” nào. Các bạn hãy làm quen việc vận dụng nguyên lí qua các bài toán sau đây.

Bài toán 1:  Chứng minh rằng trong 11 số tự nhiên bất kì bao giờ cũng tồn tại ít nhất 2 số có hiệu chia hết cho 10.

Lời giải:

Với 11 số tự nhiên khi chia cho 10 ta được 11 số dư, mà một số tự nhiên bất kì khi chia cho 10 có 10 khả năng dư là 0 ; 1 ; 2 ; 3 ; … ; 9.

Vì có 11 số dư mà chỉ có 10 khả năng dư, theo nguyên lí Đi-rích-lê, tồn tại ít nhất 2 số khi chia cho 10 có cùng số dư do đó hiệu của chúng chia hết cho 10 (đpcm).

Bài toán 2:  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:

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ó đpcm.

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ả năng dư, theo nguyên lí Đi-rích-lê tồn tại ít nhất 2 số khi chia cho 1995 có cùng số dư, hiệu của chúng chia hết cho 1995. Giả sử hai số đó là:

Khi đó:  = 1994…199400…0 chia hết cho 1995 (đpcm).

Bài toán 3:  Chứng minh rằng tồn tại số tự nhiên k sao cho (1999^k – 1) chia hết cho104.

Lời giải:  Xét 104 + 1 số có dạng:

19991 ; 19992 ; … ; 1999104 + 1.

Lập luận tương tự bài toán 2 ta được:

(1999m – 1999n) chia hết cho 104 (m > n)

hay 1999n (1999m-n – 1) chia hết cho 104

Vì 1999n và 104 nguyên tố cùng nhau, do đó (1999m-n – 1) chia hết cho 104.

Đặt m – n = k => 1999^k – 1 chia hết cho 104 (đpcm).

Bài toán 4:  Chứng minh rằng tồn tại một số chỉ viết bởi hai chữ số chia hết cho 2003.

Lời giải:  Xét 2004 số có dạng 1 ; 11 ; 111 ; … ;

Lập luận tương tự bài toán 2 ta được:

hay 11…100…0 chia hết cho 2003 (đpcm).

Một số bài toán tự giải:

Bài toán 5:  Chứng minh rằng mọi số nguyên tố p ta có thể tìm được một số được viết bởi hai chữ số chia hết cho p.

Bài toán 6:  Chứng minh rằng nếu một số tự nhiên không chia hết cho 2 và 5 thì tồn tại bội của nó có dạng:  111…1.

Bài toán 7:  Chứng minh rằng tồn tại số có dạng 1997k (k thuộc N) có tận cùng là 0001.

Bài toán 8:  Chứng minh rằng nếu các số nguyên m và n nguyên tố cùng nhau thì tìm được số tự nhiên k sao cho mk – 1 chia hết cho n.