CHƯƠNG 1 NGUYÊN LÝ DIRICHLET Chương này trình bày các dạng khác nhau của nguyên lý Dirichlet. Phần cuối chương nhắc lại một số tính chất số học để làm cơ sở cho chương sau. Nội dung chương này được tham khảo từ các tài liệu [4], [5] 1. Nguyên lý Dirichlet cơ bản Nếu có m vật, được đặt vào n cái ngăn kéo và m > n thì có ít nhất một cái ngăn kéo chứa ít nhất hai vật.
Nguyên lý Dirichlet dạng tập hợp Cho A và B là hai tập hợp hữu hạn và khác rỗng, mà số phần tử của A lớn hơn số 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 tại ít nhất hai phần tử khác nhau của A mà cùng tương ứng với một phần tử của B. Theo ngôn ngữ của ánh xạ, nếu quy tắc nói trên xác định một ánh xạ f : A → B thì f không phải là một đơn ánh. Nguyên lý Dirichlet tổng quát N Nếu có N đồ vật đặt vào k cái hộp thì tồn tại một hộp chứa ít nhất đồ k vật.
Ở đây, d xe là số nguyên nhỏ nhất ≥ x. Chứng minh: N Giả sử mỗi hộp đều chứa ít hơn vật. Khi đó, tổng số đồ vật là: k 4 N N k. k k Điều này mâu thuẫn với giả thiết là có N đồ vật cần sắp xếp.
Nguyên lý Dirichlet mở rộng Cho A là tập hữu hạn những phần tử, kí hiệu |A| là số lượng các phần tử của A. Nguyên lý Dirichlet mở rộng như sau: Nếu A và B là những tập hữu hạn, |A| > k.|B|, với k là một số nguyên dương, và nếu mỗi phần tử của A cho tương ứng với một phần tử nào đó của B ( f : A → B ) thì tồn tại ít nhất k + 1 phần tử của A mà tương ứng với cùng một phần tử của B. Chứng minh: Giả sử mỗi phần tử của B chỉ tương ứng với nhiều nhất k phần tử của A. [ Khi đó, |A| = | b∈B b∈B b∈B Suy ra |A| ≤ k.|B|, điều này mâu thuẫn với giả thiết |A| > k.
Vậy tồn tại ít nhất k + 1 phần tử của A tương ứng với cùng một phần tử của B. Nguyên lý đã được chứng minh. Nguyên lý Dirichlet cho dãy số vô hạn Nếu có hữu hạn những ngăn kéo mà chúng ta đặt vô hạn những vật vào đó, thì có ít nhất một ngăn kéo chứa vô hạn những vật đã có. Chứng minh: Gọi số ngăn kéo là k, ta có k < ∞.
Giả sử tất cả các ngăn kéo đều chứa hữu hạn vật. Gọi Ni là số vật ở ngăn kéo thứ i, suy ra Ni < ∞, i = 1, 2,. k Tổng số vật là: ∑ Ni = N1 + N2 +. Vậy tồn tại ít nhất một ngăn kéo chứa vô hạn vật.
Nguyên lý này được áp dụng để giải các bài toán liên quan đến dãy số, chẳng hạn dãy cấp số cộng, dãy cấp số nhân, dãy số nguyên tố, dãy Fibonaxi, dãy tuần hoàn. Một số dạng của nguyên lý Dirichlet trong hình học a. Nguyên lý Dirichlet về diện tích Cho một mặt A trong không gian. Kí hiệu S(A) là diện tích của A., An là các mặt sao cho Ai ⊂ A, (i = 1, 2,.
+ S(An ), thì ít nhất có hai mặt trong số các mặt A1 , A2 , ., An có một điểm trong chung. Chứng minh: Giả sử không có hai mặt nào trong số các mặt đã cho có điểm chung. + S(An ) (1) Mặt khác, Ai ⊂ A(i = 1, 2, 3,. Vậy có ít nhất hai mặt trong số các mặt đã cho có một điểm chung.
Nguyên lý Dirichlet về thể tích Những đa diện P1 , P2 , ., Pn nằm trong đa diện P và tổng thể tích P1 , P2 , ., Pn lớn hơn thể tích của P. Khi đó, ít nhất có hai trong số những đa diện P1 , P2 , ., Pn có điểm chung. Nguyên lý Dirichlet về độ dài 6 i) Cho những cung C1 ,C2 , .,Cn nằm trên đường tròn C và có tổng độ dài của C1 ,C2 , .,Cn lớn hơn độ dài đường tròn C. Khi đó có ít nhất hai trong số các cung C1 ,C2 , .,Cn có điểm chung.
ii) Cho những đoạn thẳng ∆1 , ∆2 , ., ∆n nằm trong đoạn thẳng ∆ và tổng độ dài của ∆1 , ∆2 , ., ∆n lớn hơn độ dài của ∆. Khi đó, có ít nhất hai trong số những đoạn thẳng ∆1 , ∆2 ,. Nguyên lý Dirichlet đối ngẫu Nguyên lý Dirichlet đối ngẫu được phát biểu như sau: Cho tập hợp hữu hạn S 6= ∅ và S1 , S2 , ., Sn là các tập con của S sao cho |S1 | + |S2 | +. Khi đó, tồn tại một phần tử x ∈ S sao cho x là phần tử chung của ít nhất k + 1 tập Si (i = 1, 2, 3.
Ta sẽ chứng minh nguyên lý này tương đương với nguyên lý Dirichlet mở rộng.1 (Định lý tương đương) Nguyên lý Dirichlet mở rộng và Nguyên lý Dirichlet đối ngẫu tương đương nhau. Chứng minh: • Nguyên lý Dirichlet mở rộng suy ra nguyên lý Dirichlet đối ngẫu: Giả sử S có m phần tử x1 , x2 ,. Xét tập X = (xi , S j )| xi ∈ S j , i = 1, m; j = 1, n. Ta phân bố các phần tử của tập X vào m hộp 1, 2, ., m như sau: Với xi ∈ S j thì (xi , S j ) được phân vào hộp i, với mọi i = 1, m và j = 1, n.
Khi đó, theo nguyên lý Dirichlet mở rộng, tồn tại hộp i có ít nhất k + 1 phần tử. Từ đó, 7 suy ra tồn tại phần tử xi là phần tử chung của k + 1 tập S j , j = 1, 2,. • Nguyên lý Dirichlet đối ngẫu suy ra nguyên lý Dirichlet mở rộng Kí hiệu n phần tử là j = 1, 2,. Ta phân bố các phần tử j = 1, 2, 3, ., n vào m hộp Hi = 1, 2, ., m}, và S j = {Hi | j ∈ Hi } ∀ j = 1, n.
Hiển nhiên, |S j | = 1, ∀ j = 1, n và |S| = m. Theo nguyên lý Dirichlet đối ngẫu tồn tại phần tử Hi chung của k + 1 tập S j ( j = 1, n), tức là tồn tại hộp Hi chứa ít nhất k + 1 phần tử.2 Cho A là một khoảng giới nội, A1 , A2 , ., An là các khoảng sao cho Ai ⊂ A, i = 1, 2,. Khi đó, có ít nhất hai khoảng trong số các khoảng trên có một điểm trong chung (d(I) là độ dài của khoảng I ⊂ R). Chứng minh: Thật vậy, giả sử không có cặp nào trong những khoảng đã cho có điểm trong chung.
Mặt khác, từ Ai ⊂ A, i = 1, 2, 3. Các bất đẳng thức trên mâu thuẩn với nhau. Vậy có ít nhất hai khoảng trong số các khoảng trên có điểm trong chung.3 Cho A là một khoảng giới nội, A1 , A2 , ., An là các khoảng con của A, k là số tự nhiên thỏa: k. + d(An ) Khi đó, tồn tại ít nhất k + 1 khoảng Ai , i = 1, 2, 3, ., n có điểm trong chung.4 Nếu A là một bề mặt giới hạn bởi đường cong phẳng khép kín, còn A1 , A2 , ., An là các bề mặt sao cho Ai ⊂ A, i = 1, 2, 3,.5 Cho A là một bề mặt giới hạn bởi đường cong phẳng khép kín, còn A1 , A2 , ., An là những bề mặt và thỏa mãn Ai ⊂ A (i = 1, 2, 3,.,n), còn k là số tự nhiên thỏa: k.
+ S(An ) Khi đó, ít nhất k + 1 trong số những bề mặt trên có điểm chung.6 Nếu A là một khối giới hạn bởi các mặt cong phẳng, còn A1 , A2 , ., An là các khối sao cho Ai ⊂ A (i = 1, 2, 3,.7 Cho A là một khối giới hạn bởi các đường cong phẳng, A1 , A2 , ., An là các khối sao cho Ai ⊂ A (i = 1, 2, 3,.,n), còn k là số tự nhiên thỏa: k. +V (An ) Khi đó, ít nhất k + 1 trong số những khối trên có điểm trong chung. Nguyên lý bù trừ Cho n tập hữu hạn X1 , X2 , ., Xn và khác rỗng.∪ Xn | = ∑ (−1)k−1 X(n, k) k=1 Trong đó 9 X(n, k) = ∑ | Xi1 ∩ Xi2 ∩ .<ik ≤n Trong tổng X(n, k), bộ (i1 , i2 , ., ik ) lấy tất cả các tổ hợp chập k của n và như vậy X(, k) là tổng của C(n, k) số hạng. ∩ Xn | Khi n = 2, ta có công thức quen thuộc như sau: |X1 ∪ X2 | = |X1 | + |X2 | − |X1 ∩ X2 | 1.
Phép chia trên tập các số nguyên Cho hai số nguyên a, b. Nếu tồn tại số nguyên q sao cho a = b. rằng a chia hết cho b (kí hiệu a. b) , hay b chia hết a (ký hiệu b | a).
Khi đó người ta cũng gọi a là bội của b, còn b là ước a.1 Với hai số nguyên bất kì a và b sao cho b 6= 0, tồn tại duy nhất cặp số nguyên q và r thỏa mãn a = bq + r, với 0 ≤ r < |b|. i) Với mọi số nguyên a 6= 0, ta có a. iv) Nếu a, b, m, n là những số nguyên, a .3 Mọi số nguyên lớn hơn 1 đều có thể phân tích ra các thừa số nguyên tố và phân tích đó là duy nhất nếu không kể đến thứ tự của các thừa số. Đồng dư thức Định nghĩa Cho số nguyên dương n, hai số nguyên a, b được gọi là đồng dư theo mô- đun n nếu chúng có cùng số dư khi chia cho n.
Điều này tương đương với hiệu a − b chia hết cho n. kí hiệu: a ≡ b (mod n) Tính chất Ngoài các tính chất của một quan hệ tương đương (phản xạ, đối xứng, bắc cầu), phép đồng dư còn có thêm các tính chất sau: có thể cộng, trừ, nhân và nâng lên lũy thừa các đồng dư thức có cùng một mô-đun, cụ thể. Nếu ta có: a1 ≡ a2 (mod n) b1 ≡ b2 (mod n) Thì ta có: (a1 + b1 ) ≡ (a2 + b2 ) (mod n) (a1 − b1 ) ≡ (a2 − b2 ) (mod n) (a1 b1 ) ≡ (a2 b2 ) (mod n) ak1 ≡ ak2 (mod n) với k là số nguyên dương.