NGUYÊN LÝ DIRICLE VÀ BÀI TOÁN CHIA HẾT

NGUYÊN LÝ DIRICLE VÀ BÀI TOÁN CHIA HẾT

I/ LÝ THUYẾT:

- Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý  “chuồng chim bồ câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim.

- Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau:

Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng.

 - Việc chứng minh nguyên lý này có thể tiến hành bằng lập luận phản chứng rất đơn giản: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n.

Ví dụ 1:

         Một năm có nhiều nhất là 365 ngày. Do vậy trong số 366 người bất kỳ bao giờ cũng có ít nhất 2 người có cùng ngày sinh nhật ( không xét năm nhuận ).

Ví dụ 2:

        Thang điểm bài kiểm tra là từ 0 đến 10, tức là có 11 thang điểm khác nhau. Do vậy trong số 12 sinh viên bất kỳ của một lớp sẽ có ít nhất 2 người có kết quả bài kiểm tra giống nhau.

Ví dụ 3:

         Cấp bậc quân hàm của sĩ quan có 8 cấp bậc từ thiếu úy đến đại tá. Do vậy trong một đơn vị có 9 sĩ quan thì sẽ có ít nhất 2 người cùng cấp bậc.

·      Nguyên lý Dirichlet cơ bản:

Nếu nhốt n thỏ vào m lồng, với n > m, nghĩa là số thỏ nhiều hơn số lồng, thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ.·   

ĐỂ GIẢI CÁC BÀI TOÁN ÁP DỤNG NGUYÊN TẮC ĐIRICLÊ CHÚNG TA CẦN LƯU Ý MỘT SỐ ĐIỂM SAU ĐÂY:

1. Các bài toán áp dụng nguyên tắc Điriclê thường là các bài toán chứng minh sự tồn tại của sự vật, sự việc mà không cần phải chỉ ra một cách tường minh sự vật, sự việc đó.

2. Nhiều bài toán, nguyên tắc Điriclê chỉ xuất hiện sau khi biến đổi qua một bước trung gian, hoặc thành lập các dãy số mới.

3. Để giải bài toán áp dụng nguyên tắc Điriclê, nhiều khi ta phải kết hợp với phương pháp chứng minh phản chứng.

4. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên tắc Điriclê hoặc dự đoán sẽ phải dùng nguyên tắc này, chúng ta cần suy nghĩ hoặc biến đổi bài toán để làm xuất hiện khái niệm "thỏ" và "lồng", khái niệm "nhốt thỏ vào lồng".

5. Cũng có thể có những bài toán phải áp dụng 2, 3 lần nguyên tắc Điriclê.

6. Trong suy nghĩ khi giải toán ta cố gắng làm xuất hiện các khái niệm "thỏ" và "lồng", nhưng trong trình bày phần lời giải ta cố gắng diễn đạt theo ngôn ngữ toán học thông thường

7. Khi giải xong các bài toán áp dụng nguyên tắc Điriclê, chúng ta cố gắng suy nghĩ để sáng tạo ra được các bài toán tổng quát hơn hoặc cụ thể hơn. Vì chỉ có như thế ta mới thật nắm chắc bài toán mà mình đã làm.

II / BÀI TẬP:

Bài tập 1:

      Người ta viết 5 số tự nhiên vào một hàng duy nhất a₁, a₂, a₃, a₄, a₅. Chứng minh rằng hoặc một trong các số đó chia hết cho 5, hoặc tổng một số số tự nhiên kề nhau chia hết cho 5.

Bài giải:

           Xét 5 tổng: S₁ = a₁

                              S₂ = a₁ + a₂

                              S₃ = a₁ + a_{2 ­}+ a₃

                              S₄ = a₁ + a_{2 ­}+ a₃ + a₄

                              S₅ = a₁ + a_{2 ­}+ a₃ + a₄ + a₅

      Nếu một trong các số đó chia hết cho 5 thì bài toán đã giải xong. Trong trường hợp trái lại, khi chia cho 5 thì mỗi số sẽ có một số dư nào đó trong 4 số: 1, 2, 3, 4. Theo lý Dirichlet ít nhất 2 trong 5 số đó có cùng số dư. Vậy hiệu của hai tổng đó chia hết cho 20. Chẳng hạn hai tổng đó là S_m và Sn  thì:

                          S_m - Sn (a_1­+a₂+…+an+…+a_m)- (a_1­+a₂+…+an)                     

                                      = a_n+1 + a_n+2 +…+a_m

             Mà (S_m - Sn)5 (chứng minh trên)

             Và a_n+1 + a_n+2 +…+a_m là tổng một số số tự nhiên kề nhau.

             Vậy tổng một số số tự nhiên kề nhau chia hết cho 5.

Bài tập 2:

       Chứng minh rằng trong số 12 số tự nhiên bất kỳ có thể chọn hai số có hiệu chia hết cho 11.

Bài giải:

           Khi chia 12 số bất kỳ cho 11 ta sẽ có mỗi số có một số dư trong 11 số dư: 0, 1, 2,…, 10. Do đó theo nguyên lý Dirichlet phải tồn tại ít nhất hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 11.

Bài tập 3: Trong 45 học sinh làm bài kiểm tra, không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10. Chứng minh rẳng ít nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau(điểm kiểm tra là một số tự nhiên).

Bài giải:

Có 45 – 2 = 43 hoc sinh phân chia vào 8 loại điểm (từ 2 đến 9). Giả sử mỗi loại trong 8 loại điểm đều là điểm của không quá 5 học sinh thì lớp học có không quá: 5.8 = 40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học sinh có điểm kiểm tra bằng nhau.

Trong bài toán này “thỏ” là 43 điểm kiểm tra từ 2 đến 9, “lồng” là 8 loại điểm nói trên. Tồn tại  học sinh có điểm kiểm tra bằng nhau.

Bài tập 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.

Bà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ố có cùng số dư trong phép chia cho 11. Hiệu của chúng là một số chia hết cho 11, đó là số có hai chữ số như nhau.

Bài tập 5: Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.

Bài giải:

       Gọi 5 lồng 0, 1, 2, 3, 4 thứ tự chứa các đấu thủ đã đấu 0, 1, 2, 3, 4 trận. Cũng chú ý rằng hai lông 0 và 4 không thể cùng chứa người. Như vậy chỉ có 4 lồng, mà có 5 người, tồn tại 2 người trong cùng một lồng tức là tồn tại hai đấu thủ có số trận đấu bằng nhau.

Bài tập 6:

      Cho một bảng vuông 4 x 4. Trên 16 ô của bảng, ta đặt 16 số tự nhiên từ 1 đến 16. Chứng minh rằng tồn tại hai ô kề nhau (tức là hai ô có một cạnh chung ) sao cho hiệu các số ở hai ô đó lớn hơn hoặc bằng 3.

Bài giải:

       Chuyển từ một ô bất kì sang ô kề nó gọi là một bước. Xét hai ô ghi số 1 và số 16 chuyển từ ô ghi số 1 đến ô ghi số 16 chỉ cần không quá 6 bước chuyển (nhiều nhất là 3 bước theo hàng ngang, 3 bước theo hàng dọc). Tồn tại một bước chuyển có hiệu lớn hơn hoặc bằng 3. Thật vậy giả sử tất cả các bước chuyển đều nhỏ hơn hoặc bằng 2 thì từ số 1, qua không quá 6 bước chuyển tăng thêm không quá 12, không đạt được đến số 16.

     Vậy tồn tại hai ô kề nhau có hiệu các số của hai ô đó lớn hơn hoặc bằng 3.

Bài tập 7:

       Viết 16 số, mỗi số có giá trị bất kỳ là 1, 2, 3, 4. Ghép thành từng cặp 2 số được 8 cặp số. Chứng minh rằng tồn tại hai cặp số mà tồng các số trong hai cặp đó bằng nhau.

Bài giải:

        Tổng hai số của mỗi cặp trong 8 cặp số có giá trị nhỏ nhất là: 1 + 1 = 2, có giá trị lớn nhất là: 4 + 4 = 8. Như vậy 8 tổng đó nhận 7 giá tri: (2, 3, 4, 5, 6, 7, 8). Theo nguyên lý Dirichlet, tồn tại hai tổng bằng nhau, tức là tồn tại hai cặp có tổng bằng nhau. 

Bài tập 8: Một học sinh có 40 học sinh. Chứng minh rằng có ít nhất 4 học sinh có tháng sinh giống nhau.

Giải:

Một năm có 12 tháng. Ta phân chia 40 học sinh vào 12 tháng ấy. Nếu mỗi tháng có không quá 3 học sinh được sinh ra thì số hoc sinh không quá 3.12 = 36 mà 36 < 40, vô lý.

Vậy tồn tại một tháng có ít nhất 4 học sinh trùng tháng sinh (trong bài này 40 thỏ là 40 học sinh, 12 lồng là 12 tên tháng).

Bài tập 9: Chứng minh rằng tồn tại số tự nhiên k sao \({3^k}\) tận cùng bằng 001.

Giải:

Trước hết ta chứng tỏ rằng tồn tại hai lũy thừa của 3 có cùng số dư khi chia cho 1000. Trong phép chia cho 1000, có 1000 số dư là 0, 1, 2, ..., 999.

Ta xét 1001 số là \({3,3^2}{,3^3}{,...,3^{1001}}\) thì tồn tại hai số có cùng số dư trong phép chia cho 1000. Gọi hai số đó là \({3^m}\)và \({3^n}\) (\(1 \le n < m \le 1001\)). Như vậy \({3^m} - {3^n} \vdots 100\), \({3^n}.({3^{m - n}} - 1) \vdots 1000\), \( =  > {3^{m - n}} - 1 \vdots 1000\), tức là số \({3^{m - n}}\) tận cùng bằng 001.

Bài tập 10. Một đồi thông có 800 000 cây thông. Trên mỗi cây thông có không quá 500 000 chiếc lá. Chứng minh rằng ít nhất cũng có 2 cây thông có cùng số lá như nhau ở trên cây.

Bài giải:

Ta hãy tưởng tượng mỗi cây thông là một "thỏ", như vậy có 800.000 "thỏ" được nhốt vào không quá 500.000 "chiếc lồng". Lồng 1 ứng với cây thông có 1 chiếc lá trên cây, lồng 2 ứng với cây thông có 2 chiếc lá trên cây v.v... Số thỏ lớn hơn số lồng, theo nguyên tắc Điriclê ít nhất có 1 lồng nhốt không ít hơn 2 thỏ nghĩa là có ít nhất 2 cây thông có cùng số lá.

Bài tập 11. Một lớp học có 40 học sinh. Chứng minh rằng có ít nhất 4 học sinh có tháng sinh giống nhau.

Bài giải: Một năm có 12 tháng. Ta phân chia 40 học sinh vào 12 tháng đó. Nếu mỗi tháng có không quá 3 học sinh được sinh ra thì số học sinh không quá: 3.12 = 36 mà 36 < 40: vô lý

Vậy tồn tại một tháng có ít nhất 4 học sinh trùng tháng sinh ( trong bài này 40 thỏ là 40 học sinh, 12 lồng là 12 tên tháng).

Bài tập 12. Cho dãy số gồm 5 số tự nhiên bất kì a1, a2, a3, a4, a5. 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.

Ta sẽ thành lập dãy số mới gồm 5 số sau đây:

S1 = a1

S2 = a1 + a2

S3 = a1 + a2 + a3

S4 = a1 + a2 + a3 + a4

S5 = a1 + a2 + a3 + a4 + a5

- Nếu một trong cách Si (i = 1, ... 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ố Si cho 5 sẽ được 5 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 ai liên tiếp nhau hoặc là ai nào đó

Bài tập 13.

Với 39 số tự nhiên liên tiếp, hỏi rằng ta có thể tìm được một số mà tổng các chữ số của nó chia hết cho 11 hay không?

Bài giải:

Từ 20 số đầu tiên của dãy bao giờ ta cũng có thể tìm được 2 số mà chữ số hàng đơn vị là 0, và trong hai số đó ít nhất phải có một số có chữ số hàng chục khác 9. Giả sử N là số đó, và ta gọi S là tổng các chữ số của N.

Ta có dãy số mới N, N + 1, N + 2,... N + 9, N + 19 là 11 số vẫn nằm trong 39 số cho trước mà tổng các chữ số của chúng là S, S + 1, S + 2, ... S + 9, S + 10. Đó là 11 số tự nhiên liên tiếp, ắt phải có một số chia hết cho 11.

Bài tập 14. Chứng minh rằng trong 52 số tự nhiên tùy ý, chí ít cũng có một cặp gồm hai số sao cho hoặc tổng hoặc hiệu của chúng chia hết cho 100.

Bài giải: Để làm xuất hiện số "thỏ" và số "lồng ta làm như sau:

Trong tập hợp các số dư trong phép chia cho 100 ta lấy ra từng cặp số sao cho tổng các cặp đó bằng 100 và thành lập thành các nhóm sau: (0 ; 0), (1 ; 99), (2 ; 98), (3 ; 97), (4 ; 96), (5 ; 95), (6 ; 94)... (49 ; 51), (50 ; 50).

Chú ý rằng sẽ có 50 cặp như vậy, ta thêm vào cặp (0, 0) sẽ có 51 cặp (51 lồng).

- Đem chia 52 số tự nhiên cho 100 sẽ có 52 số dư (52 thỏ).

- Có 52 số dư mà chỉ có 51 nhóm, theo nguyên tắc Điriclê ít nhất cũng phải có 2 số dư cùng rơi vào một nhóm.

Rõ ràng là cặp số tự nhiên ứng với cặp số dư này chính là hai số tự nhiên có tổng hoặc hiệu chia hết cho 100. (đpcm)

Bài tập 15. Chứng minh rằng trong 19 số tự nhiên bất kì ta luôn luôn tìm được một số mà tổng các chữ số của nó chia hết cho 10.

Bài giải:

Trước hết ta chứng minh rằng trong n số tự nhiên liên tiếp bao giờ cũng tồn tại một số chia hết cho n. (Các bạn tự chứng minh điều này).

Với 19 số tự nhiên liên tiếp bất kì luôn luôn tồn tại 10 số liên tiếp có chữ số hàng chục như nhau, còn các chữ số hàng đơn vị có giá trị từ 0 đến 9.

Vì thế tổng các chữ số của mỗi số trong 10 số này cũng làm thành dãy số gồm có 10 số tự nhiên liên tiếp, do đó tồn tại một số chia hết cho 10 (đpcm).

Bài 16:

Có 17 nhà toán học viết thư cho nhau trao đổi về 3 vấn đề khoa học, mỗi người viết thư cho một người về một vấn đề. Chứng minh rằng ít nhất cũng có 3 nhà toán học trao đổi với nhau về cùng một vấn đề.

Bài giải: Gọi A là nhà toán học nào đó trong số 17 nhà toán học, thì nhà toán học A phải trao đổi với 16 nhà toán học còn lại về 3 vấn đề.

Như vậy nhà toán học A phải trao đổi ít nhất với 6 nhà toán học về một vấn đề nào đó. Vì nếu chỉ trao đổi với số ít hơn 6 nhà toán học về một vấn đề thì số nhà toán học được trao đổi với A ít hơn 16. (Các bạn có thể diễn tả theo khái niệm "thỏ" và "lồng" để thấy ở đây đã áp dụng nguyên tắc Điriclê lần thứ nhất.)

- Gọi các nhà toán học trao đổi với nhà toán học A về một vấn đề nào đó (giả sử vấn đề I) là A1, A2, A3, A4, A5, A6 . Như vậy có 6 nhà toán học trao đổi với nhau về 3 vấn đề (không kể trao đổi với A). Như vậy có 6 nhà toán học A1, A2, A3, A4, A5, A6 trao đổi với nhau về 3 vấn đề, I, II, III.

Có hai khả năng xảy ra:

a. Nếu có 2 nhà toán học nào đó cùng trao đổi với nhau về vấn đề I thế thì có 3 nhà toán học (kể cả A) trao đổi với nhau về vấn đề I. Bài toán được chứng minh.

b. Nếu không có nhà toán học nào trong 6 nhà toán học A1, A2 ... A6 trao đổi về vấn đề I thì ta có 6 nhà toán học chỉ trao đổi với nhau về 2 vấn đề II và III.

Theo nguyên tắc Điriclê có ít nhất 3 nhà toán học cùng trao đổi với nhau về một vấn đề II hoặc III. Bài toán cũng được chứng minh