Gốc > Mục:TRAO ĐỔI TOÁN HỌC THCS > Mục:TOÁN 6 >
title:Nguyên lý Dirichlet (Đi-rích lê)
date:17-09-2012
sender:Lê Hà Linh
 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.
vVí 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 ).
vVí 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.
vVí 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+1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất 2 con thỏ.
·      Nguyên lý Dirichlet mở rộng:
      Nếu nhốt n con thỏ vào cái chuồng thì tồn tại một chuồng có ít nhất  con thỏ .
     Ở đây kí hiệu  để chỉ phần nguyên của .
      Ta có thể chứng minh nguyên lý Dirichlet mở rộng như sau: Giả sử mọi chuồng thỏ không có đến  ==(con)
                thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng  con. Từ đó suy ra tổng số con thỏ không vượt quá  con. Điều này vô lý vì có n con thỏ. Vậy giả thiết phản chứng là sai. Nguyên lý Dirichlet mở rộng được chứng minh.
·      Nguyên lý Dirichlet dạng tập hợp:
         Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn và số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B thì tồn tai ít nhất hai phần tử của A (hai phần tử khác nhau) tương ứng với một phần tử của B.

·      Nguyên lý Dirichlet dạng tập hợp mở rộng:
           Giả sử A, B là hai tập hợp hữu hạn và S(A), S(B) tương ứng kí hiệu là các số lượng phần tử của A và B. Giả sử có một số tự nhiên k nào đó mà S(A) > k S(B) và ta có quy tắc cho tương ứng với mỗi phần tử của A với một phần tử của B. Khi đó tồn tại ít nhất k/1 phần tử của B.
        Chú ý: Khi k = 1 ta có ngay lại nguyên lý Dirichlet.
·      Nguyên lý Dirichlet vô hạn:
        Nếu chia một tập hợp vô hạn các quả táo vào hữu hạn các ngăn kéo thì phải có ít nhất một ngăn kéo chứa vô hạn quả táo.
               II / BÀI TẬP:
vBài tập 1:
      Người ta viết 5 số tự nhiên vào một hàng duy nhất a1, a2, a3, a4, a5. 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: S1 = a1
                              S= a1 + a2
                                      S3 = a1 + a2 ­+ a3
                              S4 = a1 + a2 ­+ a3 + a4
                              S5 = a1 + a2 ­+ a3 + a4 + a5
      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à Sm và Sn  thì:
                          Sm - Sn (a+a2+…+an+…+am)- (a+a2+…+an)                     
                                      = an+1 + an+2 +…+am
             Mà (Sm - Sn)5 (chứng minh trên)
             Và an+1 + an+2 +…+am 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.
vBà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.
vBài tập 3:
       Nguyên tắc ngăn kéo(nguyên tắc Dirichlet) “n quả cam vào n ngăn kéo sao cho không ngăn kéo nào chứa quá một quả cam thì mỗi ngăn kéo chứa đúng một quả cam”, hoặc “n +1 quả cam vào n ngăn kéo một cách tùy ý, thì có ít nhất hai quả cam nằm trong cùng một ngăn kéo”, …
       Dựa vào nguyên tắc ngăn kéo, chứng minh:
     a. Trong n (n >1) số tự nhiên liên tiếp có đúng một số chia hết cho n;
     b. Trong n +1 số tự nhiên tùy ý có ít nhất 2 số có hiệu chia hết cho n.
Bài giải:
     a. Giả sử có n số tự nhiên liên tiếp a1, a2, a3, …, an. Ta chứng tỏ rằng trong phép chia cho n, các số dư của n số này đôi một khác nhau.
         Giả sử ngược lại, có i ≠ j sao cho:
                                 
                            
             Khi đó:
                         (trái giả thiết )
    Do n số dư khác nhau chỉ nhận giá trị trong n giá trị: 0, 1,2,…, n-1 nên có đung một số dư bằng 0
   b.  Giả sử đã cho n+1 số tự nhiên a1, a2, a3, …, an, an+1trong phép chia cho n, ta được:
                           ,     , 
     Do n +1 số dư ri chỉ nhận được các giá trị trong số n giá trị  nên phải có ít nhất hai số dư bằng nhau. Chẳng hạn , khi đó hiệu
           Sự vận dụng của nguyên lý Dirichlet:
     Ta hãy xét sự vận dụng đa dạng của nguyên lý này trong các ví dụ dưới đây:
      Sự trùng lặp:
Ví dụ: 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.
      Sự chia hết:
Ví dụ:
        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.
      Sự tương hỗ:
Ví dụ:
    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.
      Sự sắp xếp:
Ví dụ 1:
      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.
Ví dụ 2:
       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.