Khóa luận tốt nghiệp đại học: Ứng dụng nguyên lý Dirichlet giải một số dạng toán sơ cấp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

2
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khóa luận tốt nghiệp đại học "Ứng dụng nguyên lý dirichlet giải một số dạng toán sơ cấp" trình bày các nội dung chính sau: Giới thiệu các dạng phát biểu của Dirichlet; Trình bày ứng dụng của nguyên lý Dirichlet giải các bài toán sơ cấp.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khóa luận tốt nghiệp đại học: Ứng dụng nguyên lý Dirichlet giải một số dạng toán sơ cấp

UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA TOÁN ---------- KHÓA LUẬN TỐT NGHIỆP Tên đề tài: ỨNG DỤNG NGUYÊN LÝ DIRICHLET GIẢI MỘT SỐ DẠNG TOÁN SƠ CẤP Sinh viên thực hiện NGUYỄN THỊ BÍCH HƯƠNG MSSV: 2113010110 CHUYÊN NGÀNH: TOÁN HỌC KHÓA 2013 – 2017 Cán bộ hướng dẫn ThS. DƯƠNG THỊ THU THÚY MSCB: T34-15111.26647 Quảng Nam, tháng 05 năm 2017 1
PHẦN 1. MỞ ĐẦU 1. Lý do chọn đề tài Nguyên lý Dirichlet do nhà toán học Johann Peter Gustav Lejeune Dirichlet (1805 – 1859) đề xuất, tuy đơn giản nhưng có nhiều ứng dụng trong lập luận giải toán. Nguyên lý Dirichet được phát biểu dưới dạng cơ bản như sau: “Nếu nhốt n  1 con thỏ vào n cái chuồng thì luôn tồn tại một chuồng chứa ít nhất hai con thỏ”. Ngoài việc phát biểu dưới dạng cơ bản trên nguyên lý này còn được phát biểu dưới nhiều dạng như dạng tập hợp, dạng mở rộng… Trong toán học, có một số bài toán mà ta dùng rất nhiều phương pháp khác nhau để giải mà chưa có kết quả, nhưng nhờ nguyên lý Dirichlet mà bài toán trở nên đơn giản hơn và trực quan hơn rất nhiều. Với nguyên lý này giúp ta dễ dàng chứng minh được sự tồn tại của một đối tượng với tính chất xác định. Đặc biệt nó là công cụ hữu ích để giải các bài toán tổ hợp, hình học tổ hợp, bài toán bất đẳng thức, bài toán số học… và trong đề thi của các kỳ thi học sinh giỏi cũng như Olympic toán quốc tế, nguyên lý này được áp dụng rất nhiều để giải các bài toán khó. Và với việc sắp trở thành một giáo viên giảng dạy bộ môn toán, tôi mong muốn bản thân mình có một tài liệu riêng để làm hành trang cho công việc giảng dạy, tôi chọn đề tài: “Ứng dụng nguyên lý dirichlet giải một số dạng toán sơ cấp” để làm đề tài nghiên cứu. 2. Mục tiêu nghiên cứu Khóa luận được hoàn thành với mục tiêu nghiên cứu ứng dụng của nguyên lý Dirichlet để giải quyết một số bài toán sơ cấp. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Đối tượng nghiên cứu của đề tài: ứng dụng nguyên lý Dirichlet để giải một số dạng toán sơ cấp. 3.2. Phạm vi nghiên cứu Đề tài tập trung nghiên cứu trong phạm vi ứng dụng của nguyên lý Dirichlet để giải bài toán tổ hợp, bài toán hình học tổ hợp, bài toán bất đẳng thức và bài toán số học. 2
4. Phương pháp nghiên cứu - Đọc tài liệu. - Phân tích, tổng hợp tài liệu - Trao đổi với giáo viên hướng dẫn. 5. Đóng góp của đề tài Đề tài được nghiên cứu nhằm mục đích cung cấp hệ thống một số bài tập từ khó đến dễ ở các dạng bài tập tổ hợp, hình học tổ hợp, bất đẳng thức và bài toán số học được giải bằng nguyên lý Dirichlet. 6. Cấu trúc đề tài Ngoài phần mở đầu, kết luận, tài liệu tham khảo khóa luận được chia làm hai chương. Chương 1. Giới thiệu các dạng phát biểu của Dirichlet. Chương 2. Trình bày ứng dụng của nguyên lý Dirichlet giải các bài toán sơ cấp. 3
PHẦN 2. NỘI DUNG Chương 1. KIẾN THỨC CHUẨN BỊ 1.1. Một số kiến thức liên quan 1.1.1. Một số kiến thức về tổ hợp. Định nghĩa 1.1. Chỉnh hợp Cho tập hợp A gồm n phần tử và số nguyên k với 1  k  n . Khi lấy ra k phần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A. Định lý 1.1. Số các chỉnh hợp chập k của một tập hợp có n phần tử 1  k  n : An  n  n  1 n  2  ...  n  k  1 k Chứng minh: Việc lập một chỉnh hợp chập k của tập hợp có n phần tử được coi như một công việc gồm k công đoạn. Công đoạn một là chọn phần tử xếp vào vị trí thứ nhất. Công đoạn hai là chọn phần tử xếp vào vị trí thứ hai,… Công đoạn k là chọn phần tử xếp vào vị trí thứ k . Vì tập hợp có n phần tử nên công đoạn một có n cách chọn. Sang công đoạn hai chỉ còn n  1 phần tử nên có n  1 cách chọn. Tương tự công đoạn ba có n  2 phần tử nên có n  2 cách chọn… ở công đoạn cuối (công đoạn thứ k ) có n  k  1 cách thực hiện. Theo quy tắc nhân, ta có n  n  1 n  2  ...  n  k  1 cách lập ra một chỉnh hợp chập k của một tập hợp gồm n phần tử. Định nghĩa 1.2. Tổ hợp Một tổ hợp chập k của n phần tử cho trước là một bộ không có thứ tự gồm k phần tử khác nhau lấy từ n phần tử đã cho  k  n  . Định lý 1.2. Số các tổ hợp chập k của một tập hợp có n phần tử 1  k  n là: An n  n 1 n  2 ... n  k 1 k C  k n  k! k! 4
Chứng minh: Mỗi cách sắp xếp thứ tự các phần tử của một tổ hợp chập k của A cho ta một chỉnh hợp chập k của A. Nói cách khác, mỗi hoán vị của một tổ hợp chập k của A cho ta một chỉnh hợp chập k của A. Vậy từ một tổ hợp chập k của A ta lập được k ! chỉnh hợp chập k của A. Vậy ta có: An n  1n  2...n  k  1 k A  C k! hay C  k n k n  k n k! k! 1.1.2. Nguyên lý bù trừ Cho tập X và n tập con X 1 , X 2 , ..., X n . Ta có : n X 1  X 2  ...  X n   (1) X ( n, k ) k 1 k 1 Trong đó: X (n, 0)  X X (n, k )   1 i1 ...ik  n X i1  X i2  ...  X ik Chứng minh. Với n=2, ta có : X1  X 2  X1  X 2  X1  X 2 . Giả sử đúng đến n, tức là: n X  X  ...  X   X k  (1) 2  1  X i  X j  ... 1 2 n k 1 1i  j  n  (1) k  1  X i1  X i2  ...  X ik  ...  X  X 2  ...  X 1i1 ...ik  n 1 n Ta chứng minh đúng với n+1, ta có : X 1  X 2  ...  X n  X n 1  ( X 1  X 2  ...  X n )  X n 1  X 1  X 2  ...  X n  X n 1  ( X 1  X 2  ...  X n )  X n 1 Ta có : X 1  X 2  ...  X n n   X k  ...  (1) k  1  X i1  X i2  ...  X ik  ...  (1) n 1 X  X  ...  X k 1 1i1 ...ik  n 1 2 n 5
Và ( X 1  X 2  ...  X n )  X n 1  ( X 1  X n 1 )  ( X 2  X n 1 )  ...  ( X n  X n 1 )  ( X 1  X n 1 )  ( X 2  X n 1 )  ...  ( X n  X n 1 ) n   X k  X n 1  ...  (1) .  k 1 X i1  X i2  ...  X ik  X n 1  ...  k 1 1 i1 ... ik  n  (1) n 1 X 1  X 2  ...  X n  X n 1 Khi đó : n n 1 X k 1 k  X n 1   X k ; k 1 n   1i  j  n X i  X j   X k  X n 1   k 1  1i  j  n 1 Xi  X j ; (1) k  1   k X i1  X i2  ...  X ik  X n 1  (1) X i1  X i2  ...  X ik ; 1i1 ...ik  n 1i1 ...ik  n 1 ( 1) n  1 X  X  ... X  X  (1) n X  X  ... X  X 1 2 n n 1 1 2 n n 1 . n Vậy ta có: X  X  ...  X   (1) X (n, k ) , k 1 1 2 n k 1 với: X (n, k )   1 i1 ... ik  n X i1  X i2  ...  X ik . 1.1.3. Một số kiến thức liên quan đến bất đẳng thức. 1.1.3.1. Bất đẳng thức trung bình cộng – trung bình nhân Cho n số thực dương không âm a1 , a2 ,..., an thì trung bình cộng của n số đó lớn hơn hoặc bằng trung bình nhân của chúng, nghĩa là: a1  a 2  ...  a n  n a1 a 2 ... a n n Dấu “=” xảy ra khi và chỉ khi a1  a2  ...  an Chứng minh: Ta dùng phương pháp quy nạp theo n: Với n = 2, ta có chứng minh: a1  a2  a1a2 2  a1  a2  2 a1a2  0   2  a1  a2 0 6
Bất đẳng thức trên luôn đúng. Để chứng minh bất đẳng thức tổng quát ta xét bất đẳng thức phụ:  Nếu x1, x2  thì: x1  x2  x1n 1  x2 1 n  Vậy x1, x2  thì ta luôn có: x n 1 1  x 2 1   x1  x2   0 n  x1n  x2  x1 x2 1  x1n 1 x2 n n  Lấy n số thực không âm x1, x2 ,..., xn  , viết các bất đẳng thức tương ứng rồi cộng lại ta được: x n 1  x2    x1n  x3   ...   x1n  xn    x2  x3   ...   x2  xn   ...   xn 1  xn  n n n n n n n n n   x1 x2 1  x2 x1n 1    x1 x3 1  x3 x1n 1   ...   x1 xn 1  xn x1n 1   ...   xn 1 xn 1  xn xn 1  n n n n n 1  x1  x2 1  x3 1  ...  xn 1   x2  x1n 1  x3 1  ...  xn 1   ...  xn  x1n 1  x2 1  ...  xn 1  n n n n n n n 1 Từ đó:  n  1  x1n  x2n  ...  xnn   x1  x2n 1  x3n 1  ...  xnn 1   x2  x1n 1  x3n 1  ...  xnn 1    xn  x1n 1  x2 1  ...  xn 1  n n 1 * Theo giả thiết quy nạp, ta thừa nhận rằng đối với n  1 số thực không âm bất kỳ, trung bình cộng không nhỏ hơn trung bình nhân của chúng. Ta có: x2 1  x3 1  ...  xn 1   n  1 x2 x3 ...xn n n n x1n 1  x3 1  ...  xn 1   n  1 x1 x3 ...xn n n ... x1n 1  x2 1  ...  xn 1   n  1 x1 x2 ...xn 1 n n 1 Sử dụng các bất đẳng thức này, (*) tương đương:  n  1  x1n  x2nn  ...  xnn   n  n  1 x1 x2 ...xn x1n  x2 n  ...  xn n n   x1 x2 ...xn n Ta đặt: x1n  a1 , x2  a2 ,..., xn  an n n ta được: a1  a 2  ...  a n n  a1 a 2 ...a n n 7
1.1.3.2. Bất đẳng thức Bunhiacopski Cho n số thực bất kỳ, ai , bi  ,  i  1, n  ta có:  a1b1  a2b2  ...  anbn    a12  a2  ...  an  b12  b22  ...  bn2  2 2 2 Dấu “=” xảy ra khi và chỉ khi tồn tại số k  sao cho: b1  ka1 , b2  ka2 ,..., bn  kan Chứng minh: Với x  ta có: a1 x  b1 2  0 a2 x  b2 2  0 ... an x  bn 2  0 Từ đó suy ra: a12 x 2  2a1b1 x  b12  0 a2 x 2  2a2b2 x  b2  0 2 2 ... an x 2  2anbn x  bn  0 2 2 Cộng vế theo vế ta được: a2 1    a2  ...  an x 2  2a1b1  a2b2  ...  an bn x  b12  b22  ...  bn2  0 2 2  Ta thấy vế trái là một tam thức bậc hai. Đặt:    f x   a12  a2  ...  an x 2  2a1b1  a2b2  ...  an bn x  b12  b22  ...  bn2 2 2  với a12  a2  ...  an  0 và f  x   0, x  2 2 nên nếu a12  a2  ...  an  0 thì: 2 2 2 2  2 2    a1b1  a2b2  ...  anbn   a12  a2  ...  an b12  b2  ...  bn  0 2  và thu được bất đẳng thức cần chứng minh. Nếu a12  a2  ...  an  0 thì a1  a2  ...  an  0 khi đó bất đẳng thức cần chứng 2 2 minh luôn đúng. Cuối cùng ta thấy dấu “=” của bất đẳng thức xảy ra khi và chi khi :   0  a1 x  b1  a2 x  b2  ...  an x  bn  0  b1  ka1  b2  ka2  ...  bn  kan , k 8
1.1.4. Một số tính chất của đồng dư thức Định nghĩa 1.3. Đồng dư thức Cho m là một số nguyên dương, ta nói hai số nguyên a và b đồng dư với nhau theo môđun m nếu trong các phép chia a và b cho m ta được cùng một số dư, nghĩa là có các số q1 , q2 , r  với 0  r  m , sao cho: a  mq1  r b  mq2  r Khi a và b đồng dư với nhau theo môđun m ta viết a  b  mod m  . Hệ thức a  b  mod m  được gọi là đồng dư thức. Một số tính chất: i) a  b  mod m   a  b m. a  b  mod m    a  c  b  d  mod m  ii) Nếu  thì:   c  d  mod m    ac  bd  mod m   1.1.5. Một số tính chất của phép chia hết Định nghĩa 1.4. Phép chia hết Giả sử a, b là hai số nguyên và b  0, ta nói b chia hết a hay a chia hết cho b nếu như có một số nguyên q sao cho a  bq . Khi ấy ta còn nói b là ước của a hay a là bội của b và viết a  b. Một số tính chất: i) Nếu ab và b c thì a  c . ii) Nếu ab, a c và  b, c   1 thì abc . iii) Nếu ab c và  b, c   1 thì a c . 1.2. Nguyên lý Dirichlet 1.2.1. Nội dung nguyên lý Dirichlet [4] Nếu nhốt n  1 con thỏ vào n cái chuồng thì luôn tồn tại một chuồng chứa ít nhất hai con thỏ. 1.2.2. Nguyên lý Dirichlet mở rộng [1] Nếu nhốt n con thỏ vào m,  m  2  chuồng thì tồn tại một chuồng có ít nhất  n  m  1  m  con thỏ.   9
Chứng minh: n  m  1 Giả sử ngược lại không tồn tại chuồng nào nhốt được   .  m   n  m  1    n  1  m   n  1  Mà      1 con thỏ thì số thỏ trong mỗi chuồng  m    m   m  n  1 luôn nhỏ hơn hoặc bằng    con.  m  n  1 Suy ra tổng số thỏ không thể vượt quá m.   m   n  1 con thỏ. (mâu thuẫn)   Vậy nguyên lý Dirichlet đã được chứng minh. 1.2.3. Nguyên lý Dirichlet dạng tập hợp [1] Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, trong đó số lượng phần tử A lớn hơn số lượng phần tử 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 tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần tử của B. Nguyên lý Dirichlet dạng tập hợp được minh họa dưới dạng hình vẽ như sau: 1.2.4. Nguyên lý Dirichlet dạng tập hợp mở rộng [1] 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 với mỗi phần tử của A cho tương ứng 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 A mà chúng ứng với cùng một phần tử của B. 10
1.2.5. Nguyên lý Dirichlet cho diện tích [1] Nếu K là một hình phẳng, còn K1 , K2 ,..., Kn là các hình phẳng sao cho Ki  K với i  1, n và K  K1  K 2  ...  K n (với K là diện tích hình phẳng K, còn Ki là diện tích của hình phẳng Ki , i  1, n ) thì tồn tại ít nhất hai hình phẳng K i , K j với 1  i  j  n  sao cho K i , K j có điểm trong chung. 11
Chương 2. ỨNG DỤNG NGUYÊN LÝ DIRICHLET GIẢI CÁC BÀI TOÁN SƠ CẤP 2.1. Ứng dụng nguyên lý Dirichlet vào giải bài toán tổ hợp 2.1.1. Dấu hiệu nhận biết Các bài toán tổ hợp thường có nhiều cách giải. Trong đó có một số bài ta có thể sử dụng nguyên lý Dirichlet giải quyết rất đơn giản, trực quan và dễ hiểu. Đối với những bài toán này thường xuất hiện hai đối tượng cụ thể là “thỏ” và “chuồng”, trong đó số “thỏ” thường lớn hơn số “chuồng”. Yêu cầu bài toán là chứng minh có bất kì một “chuồng” nào đó chứa a “con thỏ” trở lên. Đối với một số bài toán số “chuồng” không cho dưới dạng cụ thể mà ta cần lí luận để có số “chuồng” cần tìm. 2.1.2. Một số bài toán Bài toán 1. 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). Giải. Có 45 – 2 = 43 học sinh phân chia vào 8 loại điểm (từ 2 đến 9). Khi đó ta có 43 học sinh là 43 “con thỏ”, số điểm từ 2 đến 9 sẽ tương ứng là 8 “cái chuồng”. Chia 43 “con thỏ” vào 8 “cái chuồng” ta được thương là 5 dư 3. Vậy theo nguyên lý Dirichlet tồn tại ít nhất 6 “con thỏ” nhốt chung 1 “chuồng”. Nghĩa là tồn tại ít nhất 6 học sinh có số điểm bằng nhau. Bài toán 2. Trong một kỳ thi học sinh giỏi có 6 học sinh được vào chung khảo. Tỉ lệ của cuộc thi như sau: Mỗi thí sinh phải giải 5 bài toán. Mỗi bài giải đúng được 4 điểm, mỗi bài giải sai bị trừ 2 điểm. Hãy chứng tỏ trong 6 học sinh có 2 học sinh bằng điểm nhau. Biết rằng điểm thấp nhất là 0. Giải. Ta xem 6 học sinh là 6 “con thỏ”, số điểm đạt được là các “chuồng” tương ứng. Mỗi học sinh giải 5 bài toán, mỗi bài toán đúng được 4 điểm, sai bị trừ 2 điểm, ta có các trường hợp sau: Nếu đúng 5 bài thì số điểm đạt được là 20 điểm. Nếu đúng 4 bài thì số điểm đạt được là 14 điểm. 12
Nếu đúng 3 bài thì số điểm đạt được là 8 điểm. Nếu đúng 2 bài thì số điểm đạt được là 2 điểm. Nếu đúng 1 bài thì số điểm đạt được là 0 điểm. Như vậy ta có 5 “cái chuồng” ứng với các số điểm khác nhau mà có tới 6 “con thỏ” nên theo nguyên lý Dirichlet sẽ có 2 “con thỏ” nhốt chung 1 “chuồng” nghĩa là có 2 học sinh bằng điểm nhau. Bài toán 3. Trong một lớp học có 50 học sinh. Chứng minh rằng có ít nhất 5 học sinh có tháng sinh giống nhau. Giải. Ta xem 50 học sinh là “50 con thỏ”, một năm có 12 tháng tương ứng với 12 “cái chuồng”. Khi đó chia 50 con thỏ vào 12 cái chuồng ta được thương là 4 và số dư là 2. Vậy theo nguyên lí Dirichlet có ít nhất 5 “con thỏ” nhốt chung 1 “chuồng” nghĩa là có ít nhất 5 học sinh có tháng sinh giống nhau. Bài toán 4. Chứng minh rằng trong một nhóm gồm n người có ít nhất hai người có cùng số người quen giữa những người trong nhóm. Giải. Ta xét n nhóm kí hiệu từ "0", "1", "2",..., " n  1" , trong nhóm i bất kỳ là nhóm mà mỗi người trong đó đều có cùng số người quen bằng nhau và bằng   . Ta xét hai trường hợp sau: i, i  0, n  1 Trường hợp 1: Nếu tồn một người không quen ai cả nghĩa là người đó thuộc nhóm "0" , số người còn lại là " n  1" người, khi đó nhóm " n  1" trống. Như vậy mỗi người trong số " n  1" người còn lại được đặt vào các nhóm mang số 0,1,..., n  2 (có n  1 nhóm). Vì vậy, nên theo nguyên lý Dirichlet tồn tại ít nhất hai người ở trong một nhóm hay họ có chung số lượng người quen. Trường hợp 2: Nếu mỗi người đều có ít nhất một người quen, khi đó sẽ không tồn tại nhóm "0" , mỗi người sẽ được đặt vào một trong các nhóm mang số "1","2",...," n  1" . Với số lượng  n  1 nhóm cho n người, theo nguyên lý Dirichlet 13
ta suy ra được có ít nhất hai người ở trong một nhóm hay họ có cùng số lượng người quen. Bài toán 5. Có 10 đội bóng đá thi đấu với nhau, mỗi đội phải đấu một trận với đội khác. Chứng minh rằng bất kỳ lúc nào cũng có hai đội đã đấu số trận như nhau (kể cả số trận đấu là không) Giải. Ta xem 10 đội bóng là 10 “con thỏ”. Ta có thể tạo ra các “chuồng” như sau: Gọi A0 là phòng chứa các đội có số trận đấu là 0. Gọi A1 là phòng chứa các đội có số trận đấu là 1. … Gọi A9 là phòng chứa các đội có số trận đấu là 9. Ta thấy nếu phòng A0 có ít nhất 1 đội thì phòng A9 không chứa đội nào và ngược lại nếu phòng A9 chứa ít nhất một đội thì phòng A0 không chứa đội nào. Vậy ta thấy có 9 phòng được sử dụng mà có tới 10 đội bóng nên theo nguyên lý Dirichlet sẽ có hai đội vào chung một phòng hay có ít nhất hai đội có cùng số trận đấu như nhau. Bài toán 6. Trên trái đất sống hơn 7 tỉ người, biết rằng không quá 1% sống trên 100 tuổi. Chứng minh rằng có ít nhất 3 người sinh cùng một giây đồng hồ. Giải. Theo lịch thì 100 năm có ít hơn 3700 ngày. Mỗi ngày có 24 giờ. Mỗi giờ có 3600 giây. Khi đó 100 năm có ít hơn 3,33 tỉ giây. Ta xem 3,33 tỉ giây là 3,33 tỉ “cái chuồng”. Từ giả thiết ta có số người sống dưới 100 tuổi là 6,93 tỉ người và ta xem 6,93 tỉ người là 6,93 tỉ “con thỏ”. Ta chia 6,93 tỉ “con thỏ” vào 3,33 tỉ “cái chuồng” thì theo nguyên lý Dirichlet thì sẽ có ít nhất 2 “con thỏ” nhốt chung 1 “cái chuồng” hay có ít nhất 3 người sinh Nhận xét: Với việc sử dụng nguyên lý Dirichlet việc giải bài toán tổ hợp trở nên đơn giản và dễ hiểu hơn rất nhiều. Tuy nhiên, nguyên lý Dirichlet không chỉ hỗ trợ 14
cho những bài toán tổ hợp với yêu cầu tính toán và phân chia “số thỏ” tương ứng với “số chuồng” mà còn được sử dụng để giải những bài toán tổ hợp khó hơn nữa. Bài toán 7. Mỗi nhà bác học trong số 17 nhà bác học, đều viết thư cho các nhà bác học còn lại. Họ chỉ trao đổi với nhau về 3 vấn đề. Mỗi cặp hai nhà bác học chỉ trao đổi với nhau cùng một vấn đề. Chứng minh rằng có ít nhất ba nhà bác học trao đổi với nhau về cùng một vấn đề. Giải. Giả sử trong 17 nhà bác học ta lấy ra một người và đặt người đó là A. Vì nhà bác học A viết thư cho 16 nhà bác học còn lại về 3 vấn đề (gọi tắt là vấn đề I, vấn đề II và vấn đề III) nên theo nguyên lý Dirichlet mở rộng thì A phải trao đổi ít nhất 16  3  1  với     6 nhà bác học về cùng một vấn đề. Giả sử đó là vấn đề thứ I, và 6  3  nhà bác học còn lại ta giả sử là B, C, D, E, F, G. Sáu nhà bác học này cùng trao đổi với nhau các vấn đề I, II, III. Nếu có một cặp nào đó, chẳng hạn là cặp B, C trao đổi với nhau về vấn đề I, thì bài toán được chứng minh. Khi đó, các nhà bác học A, B, C cùng trao đổi về vấn đề I. Xét trường hợp B, C, D, E, F, G chỉ trao đổi với nhau về các vấn đề II, III. Vì B trao đổi với 5 người kia về 2 vấn đề, nên B phải trao đổi ít nhất với 3 người về cùng một vấn đề, giả sử đó là vấn đề II và ba nhà bác học đó là C, D, E. Theo trên thì ta có C, D, E chỉ trao đổi với nhau về các vấn đề II và III. Nếu có 2 người nào đó, chẳng hạn C, D trao đổi với nhau về vấn đề II, thì bài toán được chứng minh, các nhà bác học B, C, D cùng trao đổi với nhau về vấn đề II. Khả năng còn lại là các nhà bác học C, D, E chỉ trao đổi với nhau về vấn đề III, trong trường hợp này bài toán được chứng minh. Vậy luôn có ít nhất ba nhà bác học cùng trao đổi với nhau về một vấn đề. Bài tập tương tự Bài toán 1. Bố n lớp 11A,11B,11C,11D có tấ t cả 44 ho ̣c sinh giỏi, trong đó số ho ̣c sinh giỏi của lớp 11D không quá 10 người. Chứng minh rằ ng ıt nhấ t mô ̣t ́ trong 3 lớp 11A,11B,11C có số ho ̣c sinh giỏi từ 12 em trở lên. Bài toán 2. Trường Đại học Quảng Nam tổ chức buổi lễ phát bằng cho sinh viên cuối khóa. Toàn trường có 400 sinh viên tốt nghiệp loại giỏi. Chứng minh rằng trong 400 sinh viên đó có ít nhất 2 sinh viên có cùng ngày sinh. 15
Bài toán 3. Có 7 học sinh lên thư viện mượn sách, họ mượn được tất cả 100 quyển, biết rằng 7 người đó đều mượn số sách khác nhau. Chứng minh rằng có 3 người trong 7 người đó mượn được ít nhất 50 quyển sách. 2.2. Ứng dụng nguyên lý Dirichlet vào giải bài toán hình học tổ hợp 2.1.3. Dấu hiệu nhận biết Ta thường gặp một số bài toán có dạng cụ thể như sau: - Có n điểm không thẳng hàng, mỗi đoạn thẳng nối từng cặp điểm được tô một trong hai màu. Bài toán yêu cầu chứng minh tồn tại m điểm (m bé hơn n) sao cho chúng là các đỉnh của một đa giác mà các cạnh của chúng được tô cùng màu. - Cho n điểm nằm trên một mặt phẳng hoặc nằm trong đa giác nào đó (thường là đa giác đều). Bài toán yêu cầu chứng minh có m điểm (m bé hơn n) được bao phủ bởi một hình tròn có bán kính R cho trước. Ngoài hai dạng trên, ta còn có những bài toán hình học tổ hợp không mẫu mực dựa trên giả thiết bài toán vẫn sử dụng nguyên lý Dirichlet để giải quyết. 2.1.4. Một số bài toán Bài toán 1. Trên mặt phẳng cho 25 điểm. Biết rằng trong 3 điểm bất kì trong số đó luôn luôn tồn tại 2 điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại hình tròn bán kính 1 chứa không ít hơn 13 điểm đã cho. Phân tích: Trong bài toán này ta thấy sẽ xuất hiện 2 đối tượng là “thỏ” và “chuồng”. Ta có 25 điểm sẽ tương ứng là 25 “con thỏ”. Mà theo đề bài trong 3 điểm bất kì trong số đó luôn luôn tồn tại 2 điểm cách nhau nhỏ hơn 1. Bài toán yêu cầu chứng minh tồn tại hình tròn bán kính 1 chứa không ít hơn 13 điểm đã cho. Như vậy số “chuồng” tương ứng ở đây sẽ là 2 “chuồng” có bán kính 1. Ta cần chứng minh tồn tại 13 “con thỏ” được nhốt chung 1 “chuồng”. Giải. 16
Lấy điểm A là 1 trong 25 điểm đã cho. Xét hình tròn C1(A; 1) tâm A bán kính 1. Khi đó có 2 khả năng xảy ra: 1. Nếu 25 điểm đã cho luôn nằm trong hình tròn C1(A; 1) thì bài toán luôn đúng. 2. Nếu tồn tại B không trùng với A (B thuộc trong 25 điểm đã cho) sao cho B C1. Xét hình tròn C2(B; 1). Vì B C1 nên AB > 1. Lấy C là 1 điểm bất kì trong 25 điểm đã cho sao cho C không trùng với A và C không trùng với B. Dựa theo giả thiết: Trong 3 điểm bất kì trong số đó luôn luôn tồn tại 2 điểm cách nhau nhỏ hơn 1và hơn nữa AB > 1 nên min{CA; CB} < 1 Suy ra C thuộc C1 hoặc C thuộc C2. Vậy hình tròn C1(A; 1) và C2(B; 1) chứa tất cả 25 điểm đã cho. Do đó theo nguyên lý Dirichlet có ít nhất 1 trong 2 hình tròn C1, C2 chứa không ít hơn 13 điểm trong 25 điểm đã cho. Bài toán 2. Trong hình vuông đơn vị (cạnh bằng 1) có 401 điểm. Chứng minh rằng có 5 điểm trong các điểm đã chọn được phủ bởi đường tròn bán kính 1 . 10 2 Phân tích: Trong bài toán này ta xem 401 điểm là 401 “con thỏ”. Để chứng minh 5 “con thỏ” được nhốt chung 1 1 “chuồng” có bán kính , thì ta cần 10 2 tạo ra số “chuồng” tương ứng là  401   5  1   100   “chuồng”. Giải. 17
Chia hình vuông ra làm  401     100 hình vuông nhỏ có cạnh 0.01.  5  1 Ta có: 401chia cho 100 được thương là 4 và số dư là 1. Theo nguyên lý Dirichlet sẽ tồn tại 1 hình vuông nhỏ chứa ít nhất 5 điểm trong 401 điểm đã cho. Giả sử hình vuông nhỏ nội tiếp trong 1 đường tròn. Khi đó ta có bán kính đường tròn của hình vuông đơn vị là: 11 2 R  2 2 Vậy ta có bán kính của các đường tròn nhỏ là: R 2 R'   100 200 Nghĩa là sẽ có ít nhất trong 5 điểm trong 401 điểm nằm trong hình vuông nội 2 tiếp đường tròn bán kính . 200 2 1 1 Mà  nên sẽ có 5 điểm được phủ bởi đường tròn bán kính . 200 10 2 10 2 Bài toán 3. Trong hình vuông có diện tích bằng 12, đặt ba đa giác có diện tích bằng 6. Chứng minh rằng luôn tìm được hai đa giác mà diện tích phần chung của nó không nhỏ hơn 2. Phân tích: Trong bài toán này chúng ta rất khó để xác định được số “thỏ” và số “chuồng”. Ta xem 3 đa giác là 3 “cái chuồng” có diện tích bằng 6. 18
Đặt 3 “cái chuồng” vào 1 “cái chuồng” có diện tích bằng 12. Khi đó 3 “cái chuồng” sẽ có những phần diện tích chung với nhau. Ta cần chứng minh 2 trong 3 “chuồng” có diện tích phần chung không nhỏ hơn 2. Và để giải quyết bài toán này ngoài việc sử dụng nguyên lý Dirichlet ta cần phải sử dụng nguyên lý bù trừ để tìm ra diện tích chung của các “chuồng”. Giải. Gọi ba đa giác là M1 , M 2 , M 3 . Kí hiệu M là diện tích của hình vuông M . Khi đó theo nguyên lý bù trừ ta có: M1  M 2  M 3  M1  M 2  M 3   M1  M 2  M 2  M 3  M1  M 3   M1  M 2  M 3 1 Theo giả thiết ta có: 19
M1  M 2  M 3  6  2  Mà M1  M 2  M 3 nằm trong hình vuông có diện tích bằng 12 nên từ (1), (2) suy ra bất đẳng thức sau: 12  18   M M1 2  M2  M3  M1  M3   M1  M2  M3 hay  M M 1 2  M2  M3  M1  M3   6  M1  M2  M3  3 Vì: M1  M 2  M 3  0 nên từ (3) ta có: M1  M 2  M 2  M3  M1  M3  6  4 Từ (4) và theo nguyên lý Dirichlet suy ra tồn tại ít nhất một trong ba số M1  M 2 , M 2  M 3 , M1  M 3 lớn hơn hoặc bằng 2. Giả sử: M1  M 2  2 . Khi đó hai đa giác M1 , M 2 có diện phần chung không nhỏ hơn 2. (đpcm). Bài toán 4. Trong mặt phẳng cho 6 điểm, trong đó không có 3 điểm nào thẳng hàng. Mỗi đoạn thẳng nối từng cặp điểm được tô màu đỏ hoặc xanh. Chứng minh rằng tồn tại 3 điểm trong 6 điểm đã cho sao cho chúng có 3 đỉnh của một tam giác mà các cạnh của nó được tô cùng màu. Phân tích: Trong 6 điểm đã cho ta chọn ra 1 điểm làm gốc, với mỗi đoạn thẳng đều đi qua điểm gốc thì qua 6 điểm đã cho ta vẽ được 5 đoạn thẳng. Khi đó 5 đoạn thẳng tương ứng là 5 “con thỏ”, 2 màu đỏ hoặc xanh ta xem là 2 “cái chuồng”. Theo nguyên lý Dirichlet nhốt 5 “con thỏ” vào 2 “cái chuồng” thì tồn tại 1 “chuồng” chứa 3 “con thỏ” tức là 3 trong 5 đoạn thẳng được tô cùng màu. Ta cần chứng minh 3 điểm trong 6 điểm đã cho sao cho chúng có 3 đỉnh của một tam giác mà các cạnh của nó được tô cùng màu. 20