Luận văn Nguyên lí dirichlet và ứng dụng giải toán sơ cấp

u 100 cạnh nội tiếp trong đường tròn (C). Mỗi đỉnh được gán một trong các số 1, 2, 3, . . . , 49. Chứng minh rằng trên (C) tồn tại hai cung AB và CD với các tính chất sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 21 1. Các điểm A,B,C,D là các đỉnh của đa giác đều đã cho. 2. Các dây cung AB và CD song song với nhau. 3. Nếu A,B,C,D được gắn tương ứng với các số a, b, c, d thì a + b = c+ d. Lời giải: A B C D Hình 2.14 Vì đa giác đều 100 cạnh nội tiếp trong (C), nên có đúng 50 đường kính khác nhau mà các đầu mút của các đường kính này đều là các đỉnh của đa giác đều 100 cạnh cho trước. Giả sử AB là một trong các đường kính ấy và giả sử A tương ứng với số a,B tương ứng với số b. Bây giờ ta gán cho đường kính AB số |a− b|. Do a, b ∈ {1, 2, 3, . . . , 49} nên dễ thấy: 0 ≤ |a− b| ≤ 48. Như vậy mỗi một trong 50 đường kính vừa xét tương ứng với một trong các số 1, 2, . . . , 48. Theo nguyên lí Dirichlet có ít nhất hai đường kính (trong số 50 đường kính) được đặt tương ứng với cùng một số. Không giảm tổng quát có thể cho đó là đường kính AC và BD. Cũng không giảm tổng quát có thể cho là các đỉnh A,B,C,D tương ứng với các số a, b, c, d, trong đó c ≤ a và b ≤ d (Nếu không phải như thế thì chỉ việc đổi tên các đầu mút của đường kính). Theo giả thiết thì đường kính AC ứng với số a− c, còn đường kính BD ứng với số d− b. Từ: a− c = d− b ⇒ a+ b = c + d. Rõ ràng ABCD là hình chữ nhật, do đó AB//CD. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 22 Ví dụ 2.23 Cho dãy vô hạn các số tự nhiên u1, u2, . . . được xác định theo công thức truy hồi sau: { u1 = 3 un+1 = (n+ 1)un − n + 1, n = 1, 2, . . . Giả sử n là số tự nhiên bất kì và tập M gồm un điểm sao cho không có ba điểm nào thẳng hàng. Mỗi đoạn thẳng nối hai điểm khác nhau trong M được tô bằng một trong n màu cho trước. Chứng minh rằng tồn tại ba điểm trong M là đỉnh của một tam giác cùng màu. Lời giải: Ta chứng minh bằng quy nạp theo n. • Với n = 1, ta có u1 = 3 và kết luận của bài toán hiển nhiên đúng (vì ở đây chỉ có 1 màu do n = 1). Với n = 2, ta có u2 = 2u1 − 1 + 1 = 6. Ta có bài toán với 6 điểm và dùng 2 màu. Bài toán này đã được giải (xem ví dụ 2.1). Vậy kết luận cũng đúng khi n = 2. • Giả sử kết luận của bài toán đúng với n, tức là nếu tập M gồm un điểm sao cho không có ba điểm nào thẳng hàng và dùng n màu để tô các đoạn thẳng. Khi đó tồn tại tam giác cùng màu. • Xét với n + 1, tức là tập M gồm un+1 điểm bất kì (không có ba điểm nào thẳng hàng), và dùng n+ 1 màu để tô các đoạn thẳng. Lấy A là một trong các điểm của tập M . Điểm này có thể nối với un+1 − 1 điểm còn lại của tập M bằng un+1 − 1 đoạn thẳng bôi màu. Theo công thức xác định dãy ta có: un+1 − 1 = (n+ 1)un − n + 1− 1 = (n + 1)(un − 1) + 1. (2.6) Từ (2.6) theo nguyên lí Dirichlet có ít nhất un đoạn thẳng có chung đỉnh A được bôi màu.Giả sử AB1, AB2, . . . , ABun được bôi cùng màu và giả sử đó là màu α, thì tam giác ABiBj cùng màu α, (α thuộc vào một trong n + 1 màu đã cho ). Có các khả năng sau xảy ra: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 23 1. Nếu một trong các đoạn thẳng BiBj(i 6= j, 1 ≤ i < j ≤ un) được bôi màu α, thì tam giác ABiBj cùng màu α. Bài toán đã được giải xong trong trường hợp n + 1. 2. Các đoạn thẳng BiBj , 1 ≤ i < j ≤ un có màu khác với α. Xét un điểm B1, B2, . . . , Bun. Rõ ràng không có ba điểm nào trong chúng thẳng hàng. Chúng dùng tối đa (n + 1)− 1 = n màu để tô (do không dùng màu α). Theo giả thiết quy nạp tồn tại tam giác cùng màu. Vậy kết luận của bài toán cũng đúng với n + 1. Ví dụ 2.24 Trong mặt phẳng, cho tập A gồm n điểm (n ≥ 2). Một số cặp điểm được nối với nhau bằng đoạn thẳng. Chứng minh rằng trong tập A đã cho, có ít nhất hai điểm được nối với cùng số lượng các điểm khác thuộc A. Lời giải: Giả sử a ∈ A. Ta kí hiệu S(a) là số lượng các điểm của A nối với a thành đoạn thẳng. Thí dụ trong hình vẽ bên thì: S(a = 2), S(b) = 3, S(c) = 1, S(d) = 2, S(e) = 2 a b c d e Hình 2.15 Bài toán trở thành: Chứng minh rằng tồn tại a1, a2 ∈ A(a1 6= a2), mà S(a1) = S(a2). Rõ ràng với mọi a ∈ A ta có: 0 ≤ S(a) ≤ n− 1. (2.7) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 24 Mặt khác dễ thấy không tồn tại hai điểm a ∈ A, b ∈ A mà: S(a) = n− 1 và S(b) = 0. (2.8) Thật vậy, nếu có (2.8), thì từ S(a) = n− 1, suy ra a nối với tất cả n− 1 điểm còn lại, nói riêng a phải nối với b. Điều đó có nghĩa là S(b) ≥ 1 và dẫn đến mâu thuẫn với (2.8) (vì S(b) = 0.) Gọi S là tập hợp các giá trị mà các đại lượng S(a) nhận, a ∈ A tức là: S = { m|m = S(a), a ∈ A} . Như vậy từ (2.7) suy ra tập S có tối đa n giá trị. Tuy nhiên từ (2.8) suy ra n−1 và 0 không đồng thời thuộc S, vì thế tập S tối đa nhận n− 1 giá trị. Theo nguyên lí Dirichlet suy ra tồn tại ít nhất a1 ∈ A, a2 ∈ A(a1 6= a2), mà S(a1) = S(a2). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 3 Ứng dụng nguyên lí Dirichlet vào số học Các bài toán số học thường rất khó khăn trong việc tìm lời giải. Tuy nhiên có một số lượng bài tập không nhỏ ta có thể sử dụng nguyên lí Dirichlet để giải quyết rất hiệu quả, mà trình bày tương đối đơn giản và dễ hiểu. Sau đây là các ví dụ điển hình. Ví dụ 3.1 Biết rằng 3 số a, a = k, a+2k đều là các số nguyên tố lớn hơn 3. Chứng minh rằng khi đó k chia hết cho 6. Lời giải: Do a, a+ k, a+2k đều là các số nguyên tố lớn hơn 3, nên chúng đều là các số lẻ và không chia hết cho 3. Do a và a+ k cùng lẻ nên k = (a+ k)− a sẽ chia hết cho 2. (3.1) Do a, a = k, a + 2k đều không chia hết cho 3, nên khi chia cho 3 ít nhất hai số có cùng số dư (theo nguyên Dirichlet). Chỉ có các khả năng sau xảy ra: 1. Nếu a+ k ≡ a(mod3) thì (a + k)− a ≡ 0(mod3), suy ra k...3. 2. Nếu a+ 2k ≡ a = k(mod3) thì (a+ 2k)− (a + k) ≡ 0(mod3), suy ra k...3. 3. Nếu a + 2k ≡ a(mod3) thì (a + 2k) − a ≡ 0(mod3), suy ra 2k...3. Do (2, 3) = 1 suy ra: k ≡ 3. (3.2) 25 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 26 Tóm lại trong mọi trường hợp ta đều thấy k ≡ 3. Lại do (2, 3) = 1 nên từ (3.1) và (3.2) ta có k ≡ 6. Ví dụ 3.2 Cho 10 số nguyên dương u1, u2, . . . , u10. Chứng minh rằng tồn tại các số ci ∈ {−1, 0, 1}, i = 1, 10, không đồng thời bằng không sao cho số 10∑ i=1 ciui chia hết cho 1023. Lời giải:Xét tất cả các số có dạng Aj = 10∑ i=1 biui, trong đó bi ∈ {0, 1} , i = 1, 10, j = 1, 1024. Rõ ràng có tất cả 210 = 1024 số Aj, j = 1, 1024, như vậy. Khi chia 1024 số Aj này cho 1023 thì theo nguyên lí Dirichlet có ít nhất hai số Ak, Ah, k 6= h sao cho Ak ≡ Ah(mod1023). Giả sử Ak và Ahcó dạng sau: Ak = 10∑ i=1 bkiui ở đây bki ∈ {0, 1}, Ah = 10∑ i=1 bhiui ở đây bhi ∈ {0, 1} Ta có Ak −Ah...1023 ⇔ 10∑ i=1 (bki − bhi)ui...1023. Đặt ci = bki − bhi,i = 1, 10. Vì bki ∈ {0, 1}, bhi ∈ {0, 1} nên ci ∈ {−1, 0, 1}, mặt khác do Ak 6= Ah nên ci không thể đồng thời bằng không, ∀i = 1, 10. Như thế ta đã chứng minh được sự tồn tại của 10 số ci ∈ {−1, 0, 1} không đồng thời bằng không, sao cho: 10∑ i=1 ciui ...1023. Ví dụ 3.3 Cho 5 số nguyên phân biệt tuỳ ý a1, a2, a3, a4, a5. Xét tích: P = (a1−a2)(a1−a3)(a1−a4)(a1−a5)(a2−a3)(a2−a4)(a2−a5)(a3−a4)(a3−a5)(a4−a5) Chứng minh rằng P ...288 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 27 Lời giải: Ta có phân tích sau : 288 = 25.32 và do (2, 3) = 1 nên để chứng minh P ...288 ta chỉ cần chứng minh đồng thời P ...25 và P ...32. Theo nguyên lí Dirichlet thì trong n+1 số nguyên tuỳ ý, luôn tồn tại hai số có hiệu chia hết cho n. Trong 4 số a1, a2, a3, a4 có hai số có hiệu chia hết cho 3, không giảm tổng quát, có thể cho là: a1 − a2...3. Bây giờ xét bốn số a2, a3, a4, a5 ta lại được hai số có hiệu cũng chia hết cho 3. Như thế trong tích P có ít nhất hai hiệu khác nhau cùng chia hết cho 3. Do đó P ...32. (3.3) Lại theo nguyên lí Dirichlet trong 5 số đã cho có ít nhất ba số có cùng tính chẵn, lẻ. Chỉ có hai trường hợp sau xảy ra: 1. Nếu ít nhất có 4 số có cùng tính chẵn lẻ, thì từ 4 số này có thể lập nên 6 hiệu khác nhau cùng chia hết cho 2, do đó tích của chúng chia hết cho 26, nói riêng P ...25. 2. Nếu có đúng 3 số có cùng tính chẵn lẻ. Không giảm tổng quát, có thể cho đó là a1, a2, a3. Khi đó hai số còn lại a4, a5 cũng có tính chẵn lẻ giống nhau nhưng khác với tính chẵn lẻ của a1, a2, a3. Vậy bốn hiệu sau đây cũng chia hết cho 2: a1 − a2, a1 − a3, a1 − a4, a2 − a3, a4 − a5. Mặt khác, trong 5 số đã cho có ít nhất hai hiệu chia hết cho 4, vì thế trong bốn số a1 − a2, a1 − a3, a2 − a3, a4 − a5 có ít nhất một hiệu chia hết cho 4. Do đó : (a1 − a2)(a1 − a3)(a2 − a3)(a4 − a5)...25 tức là P ...25. Tóm lại trong mọi trường hợp ta luôn có P ...25. (3.4) Từ (3.3) và (3.4) ta suy ra P ...288. Ví dụ 3.4 Cho a và m là hai số nguyên dương tuỳ ý. Chứng minh rằng các số dư của phép chia a, a2, a3, . . . cho m lặp lại một cách tuần hoàn (có thể không bắt đầu từ đầu). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 28 Lời giải: Xét m+ 1 luỹ thừa đầu tiên: a, a2, a3, . . . , am, am+1. Khi chia một số nguyên dương bất kì cho m, thì các số dư phải thuộc tập hợp {0, 1, 2, 3, . . . , m− 1} . Vì thế theo nguyên lí Dirichlet, phải tồn tại hai trong số m+1 số trên chia cho m có cùng số dư. Nói cách khác, giả sử hai số đó là: ak và ak+1, (k > 0), ta có: ak ≡ ak+1(modm) (3.5) Xét một số tự nhiên bất kì n ≥ k. Từ (3.5) ta có: ak.ak+1 ≡ ak+1.an−k(modm) hay với mọi n ≥ k,ta luôn có: an ≡ an+1(modm). (3.6) Đẳng thức (3.6) chứng tỏ rằng bắt đầu từ vị trí ak các số dư lặp lại tuần hoàn. Số l thường được gọi là chu kì tuần hoàn của các số dư khi chia các luỹ thừa của a cho m.  Ví dụ 3.5 Chứng minh rằng có vô số số chia hết cho 19111987 mà trong biểu diễn thập phân của các số đó không có các chữ số 0, 1, 2, 3. Lời giải: Gọi a là số tự nhiên mà trong biểu diễn thập phân của nó không chứa các chữ số 0, 1, 2, 3. Rõ ràng các chữ số a như vậy là vô hạn. Ta xét dãy số sau đây: a, aa, aaa, . . . , aaaa . . . a︸ ︷︷ ︸ 19111987+1 . Đem chia 1911 1987 +1 số khác nhau này cho 1911 1987 . Theo nguyên lí Dirichlet sẽ có ít nhất hai số khi chia cho 1911 1987 cho cùng số dư. Giả sử hai số đó là: aaa . . . a︸ ︷︷ ︸ n số , aaa . . . a︸ ︷︷ ︸ m số , (n > m). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 29 Như vậy: aaa . . . a︸ ︷︷ ︸ n số − aaa . . . a︸ ︷︷ ︸ m số ...1911 1987 hay: aa . . . a︸ ︷︷ ︸ (n−m) số 000 . . .0︸ ︷︷ ︸ m số ...1911 1987 . (3.7) Vì (10, 19) = 1 nên (10mk, 1911 1987 ) = 1, suy ra aaa . . . a︸ ︷︷ ︸ (n−m) số ...1911 1987 . (3.8) Do a là vô số, nên từ (3.8) suy ra tồn tại vô số số chia hết cho 1911 1987 mà trong biểu diễn thập phân của chúng không có các số 0, 1, 2, 3. Ví dụ 3.6 Chứng minh rằng trong 12 số nguyên tố phân biệt luôn luôn chọn ra được 6 số, gọi là a1, a2, a3, a4, a5, a6 sao cho (a1 − a2)(a3 − a4)(a5 + a6)...1800. Lời giải: Vì ba số nguyên tố đầu tiên là 2, 3, 5, do đó trong 12 số nguyên tố phân biệt đã cho luôn có ít nhất 9 số lớn hơn 5. Vì là số nguyên tố lớn hơn 5 nên: 1. Chín số trên khi chia cho 3 có dư 1 hoặc 2. Theo nguyên lí Dirichlet phải tồn tại ít nhất 5 số đồng dư với nhau theo mod 3. Năm số này lại không chia hết cho 5. Vì thế trong năm số ấy lại có ít nhất hai số mà ta có thể giả sử là a1, a2 sao cho a1 ≡ a2( mod 5). Ngoài ra dĩ nhiên ta có a1 ≡ a2( mod 3). Từ đó ta có a1 − a2...15. Mặt khác, a1, a2 cùng lẻ nên a1 − a2...2. Do (2, 15) = 1 nên suy ra a1 − a2...30. 2. Xét 7 số còn lại : Theo nguyên lí Dirichlet tồn tại bốn số đồng dư với nhau theo mod 3. Đem 4 số này chia cho 5 có hai khả năng xảy ra: (a) Nếu có hai số chẳng hạn ( gọi là a3, a4) mà a3 ≡ a4(mod5). Từ đó suy ra a3 − a4...5. Rõ ràng a3 − a4...3 và a3 − a4...2. Vì (5, 3, 2) = 1 nên ta có a3 − a4...30. Lấy hai số a5, a6 bất kì (ngoài a1, a2, a3, a4 đã chọn) thì do a5, a6 lẻ (do nguyên tố), nên a5 + a6 ...2. Từ đó suy ra: (a1 − a2)(a3 − a4)(a5 + a6)...30.30.2 = 1800 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 30 (b) Nếu 4 số này khi chia cho 5 các số dư khác nhau là {1, 2, 3, 4}. Giả sử a5 ≡ 1(mod5), a6 ≡ 4(mod5) thì ta có: a5 + a6 ≡ 5(mod5), suy ra a5 + a6...5 Với hai số còn lại a3, a4 thì rõ ràng a3 − a4...3 (theo cách chọn 4 số trên). Do a3, a4, a5, a6 lẻ nên a5 + a6 ...2,a3 − a4...2. Từ đó suy ra a5 + a6...10 và a3 − a4...6.Vậy: (a1 − a2)(a3 − a4)(a5 + a6)...30.10.6 = 1800. Tóm lại, luôn tồn tại a1, a2, . . . , a6 phân biệt sao cho: (a1 − a2)(a3 − a4)(a5 + a6)...1800. Ví dụ 3.7 Từ một số nguyên dương, ta tác động hai phép toán sau đây: 1. Nhân nó với một số nguyên dương tuỳ ý. 2. Xoá bỏ các chữ số không trong biểu diễn thập phân của nó. Chứng minh rằng với mọi số nguyên dương n , ta có thể thực hiện một dãy những phép toán như trên để biến n thành một số có một chữ số. Lời giải: Ta có nhận xét sau: "Với mọi số nguyên dương k, đều có ít nhất một bội số có dạng: 111 . . .100 . . . 0". Nhận xét được chứng minh như sau: Xét k + 1 số sau: 1, 11, 111, . . . , 11 . . .11︸ ︷︷ ︸ k+1 Theo nguyên lí Dirichlet có ít nhất hai số trong chúng khi chia cho k có cùng phần dư. Hiệu hai số này sẽ chia hết cho k và rõ ràng hiệu đó có dạng: 111 . . .100 . . .0. Nhận xét được chứng minh.Trở lại bài toán ta đang xét,ta có bổ đề sau: Bổ đề 3.1 Với mọi số nguyên n cho trước,bằng một số hữu hạn lần thực hiện hai phép toán như trên ta có thể đưa n về số có dạng: 111 . . . 1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 31 Chứng minh: Vì n là số nguyên dương, nên theo nhận xét trên tồn tại số α = 111 . . .10 . . . 0 mà α ...n. Đặt α = k.n ⇒ k nguyên dương. Ta tiến hành các phép toán như sau: 1. Nhân số n với số k, khi đó n biến thành số α = 111 . . .10 . . . 0. 2. Xoá bỏ các số 0, khi đó n biến thành 111 . . .1. Bổ đề được chứng minh. Như vậy cho trước số n,bằng phép toán trên ta đưa n về số có dạng 111 . . .1. 1. Ta nhân số 111 . . . 1 với 82 và được số 911 . . .102. 2. Thực hiện phép xoá số 0 ta được số: 911 . . .12. 3. Thực hiện phép nhân số này với 9 ta được số:820 . . .008. 4. Thực hiện phép xoá số 0 ta được số: 828. 5. Thực hiện phép nhân số này với 25 ta được số: 20700. 6. Thực hiện phép xoá số 0 ta được số: 27. 7. Thực hiện phép nhân số này với 4 ta được số: 108. 8. Thực hiện phép xoá số 0 ta được số: 18. 9. Thực hiện phép nhân số này với ta được số: 90. 10. Thực hiện phép xoá số 0 ta được số: 9. Vì số 9 là số có một chữ số và phép toán dừng lại ở đây. Như vậy với một số nguyên dương tuỳ ý ta luôn có thể thực hiện một dãy hữu hạn những phép toán đã cho để biến n thành số có một chữ số. Ví dụ 3.8 Xét tập M gồm 2003 số nguyên dương phân biệt sao cho không có số nào trong chúng có ước nguyên tố lớn hơn 23. Chứng minh rằng M chứa một tập hợp con gồm 4 phần tử mà tích của 4 phần tử này là luỹ thừa bậc 4 của một số nguyên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 32 Lời giải: Vì chỉ có 9 số nguyên tố không lớn hơn 23 là: p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, p8 = 19, p9 = 23. Vì thế trong mỗi phần tử k của tập hợp M (từ giả thiết) đều có dạng: k = pk11 .p k2 2 . . . . .p k9 9 . (3.9) Ở đây ki là các số nguyên không âm với mọi i = 1, 9.Với mỗi phần tử k của tập hợp M ta gán tương ứng với một dãy (x1, x2, . . . , x9), trong đó xi = 0 nếu số mũ ki của pi trong (3.9) là chẵn và xi = 1 nếu ki lẻ. Tập hợp các dãy (x1, x2, . . . , x9) trong đó xi = 1, i = 1, 9 gồm 29 phần tử. Theo nguyên lí Dirichlet mọi tập hợp con chứa không ít hơn 29 +1 phần tử của M chứa ít nhất hai số nguyên phân biệt (ta gọi chúng là a1, b1), trong đó a1, b1 cùng ứng với một dãy x1, x2, . . . , x9 nào đó, tức là: a1 = p k1 1 .p k2 2 . . . p k9 9 , b1 = p k1, 1 .p k2, 2 . . . p k9, 9 . Do a1, b1 cùng ứng với một dãy chung x1, x2, . . . , x9 nào đó nên ki, k,i có cùng tính chẵn lẻ ∀i = 1, 9. Từ đó ta có: a1b1 = p k1+k1, 1 p k2+k2, 2 . . . p k9+k9, 9 = c 2. Nói cách khác đi ta lấy đi một cặp như thế từ tập M , thì còn lại 2003−2 > 29+1 số. Áp dụng lần nữa nguyên lí Dirichlet và tiếp tục lấy đi những cặp như thế cho đến khi còn lại 29 + 1 số trong M . Để ý rằng 2003 > 3(29 + 1), vì 3(269 + 1) = 1539, nên ta có thể lấy đi 269 + 1 cặp (a, b), lúc đó số còn lại của M vẫn là : 2003− 2(29 + 1) = 977 > 513 = 29 + 1. Xét 29+1 cặp lấy đi (ứng với mỗi cặp ai, bi) ta có aibi = c2i . Ta có: ci = √ aibi. Số ci không thể chứa các thừa số nguyên tố khác p1, p2, . . . , p9 (do các ai, bi cũng như vậy). Vì vậy lại theo nguyên lí Dirichlet thì tồn tại ít nhất một cặp (ci, cj) sao cho ci.cj = d2, với d là các số nguyên, suy ra: d4 = c2i .c 2 j = ai.bi.aj .bj . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 33 Ví dụ 3.9 Cho trước 20 số tự nhiên a1 < a2 < a3 < · · · < a20 không vượt quá 70. Chứng minh rằng giữa các hiệu aj − ak(j > k) luôn tìm được ít nhất 4 hiệu bằng nhau. Lời giải: Giả sử kết luận của bài toán không đúng, khi đó nói riêng trong 19 hiệu sau: a20 − a19, a19 − a18, . . . , a3 − a2, a2 − a1 không có bốn số nào bằng nhau. Do đó lại nói riêng trong 19 dãy số đó, mỗi số 1, 2, 3, 4, 5, 6 có mặt không quá 3 lần. Từ đó trong 19 số ấy phải lớn hơn 6 (thật vậy, nếu mọi số đều nhỏ hơn hoặc bằng 6, thì theo nguyên lí Dirichlet phải có ít nhất 4 số bằng nhau). Một cách hoàn toàn tương tự, ta thấy ngay có 3 trong 18 số còn lại phải lớn hơn 5, 3 trong số 15 số còn lại phải lớn hơn 4, . . . . Vì thế: (a20 − a19) + (a19 − a18) + · · ·+ (a2 − a1) ≥ 7 + 3(6 + 5 + 4 + 3 + 2 + 1) = 70 Suy ra: a20 − a1 > 70. Mặt khác: 1 ≤ ai ≤ 70∀i = 1, 20. nên: a20 − a1 ≥ 70− 1 = 69. Ta nhận được mâu thuẫn. Vậy giả thiết phản chứng là sai. Ví dụ 3.10 Tập hợp các số 1, 2, 3, , . . . , 100 được chia thành 7 tập hợp con. Chứng minh rằng ít nhất ở một trong các tập con ấy tìm được 4 số a, b, c, d sao cho a+ b = c + d hoặc ba số e, f, g sao cho e+ f = 2g. Lời giải: Theo nguyên lí Dirichlet suy ra có ít nhất một tập hợp con chứa không ít hơn 15 phần tử (vì nếu trái lại tất cả các tập con chứa không nhiều hơn 7.14 = 98 phần tử. Do 98 b của tập hợp này. Ứng với mỗi cặp (a, b) này ta xét hiệu a − b (rõ ràng a − b > 0). Vì tập này có không ít hơn 15 phần tử, nên ta nhận được không ít hơn C215 hiệu, (tức là không ít hơn 105 hiệu). Do các số của tập con đều thuộc tập hợp {1, 2, . . . , 100} nên các hiệu nói trên thuộc tập hợp {1, 2, . . . , 99}. Vì thế lại theo nguyên lí Dirichlet suy ra các hiệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 34 trên phải có ít nhất hai hiệu bằng nhau. Giả sử hai hiệu đó tương ứng với hai cặp (a, b), (c, d), (a 6= c, (b 6= d)), sao cho b− a = d − c. Từ đó ta có: a + d = b + c . Nếu a = d (hoặc b = c; chú ý những sự bằng nhau khác không thể xảy ra do a 6= c, b 6= d), thì b + c = 2a hoặc d + a = 2b.  Ví dụ 3.11 Chứng minh rằng từ 52 số nguyên bất kì luôn có thể chọn ra được hai số mà tổng hoặc hiệu của chúng chia hết cho 100. Lời giải: Tất cả các số dư trong phép chia cho 100, được chia thành từng nhóm như sau: {0} , {1, 99} , {2, 98} , . . . , {49, 51} , {50} . Vì có tất cả 51 nhóm, mà lại có 52 số, nên theo nguyên lí Dirichlet giữa chúng phải có hai số mà các số dư trong phép chia cho 100 rơi vào một nhóm. Hai số này là hai số cần tìm vì nếu số dư của chúng bằng nhau thì hiệu của chúng chia hết cho 100, còn nếu số dư của chúng khác nhau thì tổng của chúng chia hết cho 100.  Ví dụ 3.12 Chứng minh rằng từ tập hợp tuỳ ý gồm n số tự nhiên luôn tách ra được một tập hợp con (khác rỗng) chứa các số mà tổng của chúng chia hết cho n. Lời giải: Giả sử với một tập hợp nào đó chứa các số a1, a2, . . . , an mà không thoả mãn khẳng định của bài toán.Khi đó không có số nào trong các số : S1 = a1, S2 = a1 + a2, . . . , Sn = a1 + · · ·+ an chia hết cho n. Vì số các số dư khác không trong phép chia cho n là n−1, nên theo nguyên lí Dirichlet ta tìm được hai số Si và Sj(1 ≤ i ≤ j ≤ n) có cùng số dư. Suy ra hiệu Si − Sj = ai−1 + · · ·+ aj chia hết cho n. Điều này mâu thuẫn với giả sử nói trên và khẳng định của bài toán được chứng minh. Ví dụ 3.13 Cho a1, a2, . . . , an là những số nguyên khác nhau trong khoảng [100, 200], mà chúng thoả mãn: a1 + a2 + · · ·+ an ≥ 11100 Chứng minh rằng giữa các số này có ít nhất một số, mà viết nó ở dạng thập phân có ít nhất hai chữ số giống nhau. Lời giải: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 35 Chúng ta lập danh sách các số trong khoảng [100, 200],mà chúng viết ở hệ thập phân ít nhất có hai chữ số trùng nhau: 100, 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 131, 141, 151, 161, 171, 181, 191, 199, 200. Tổng của tất cả các số nói trên là 4050. Mặt khác tổng của tất cả các số nguyên trong khoảng [100, 200] là: 15150.Nếu trong những số đã cho là: a1, . . . , an không có số nào trong danh sách trên, thì a1 + a2 + . . . an < 15150− 4050 = 11100, điều này vô lí. Nghĩa là trong các số a1, . . . , an có ít nhất một số viết ở cơ số 10 có ít nhất hai chữ số trùng nhau. Ví dụ 3.14 Cho M là tập hợp bất kì gồm 10 số tự nhiên, mỗi số không lớn hơn 100. Chứng minh rằng tồn tại hai tập hợp con của M mà tổng của các phần tử trong chúng bằng nhau. Lời giải: Có thể chứng minh nếu tồn tại thoả mãn kết luận của bài toán, thì ta có thể chọn được hai tập con cùng tính chất ấy nhưng không giao nhau. Thật vậy, cho X, Y là hai tập con của M có tổng các phần tử bằng nhau. Chúng ta kí hiệu X1 gồm các phần tử của X mà không thuộc Y . Tương tự như vậy Y1 gồm các phần tử của Y mà không thuộc X. Rõ ràng X1 và Y1 có tổng các phần tử bằng nhau mà không giao nhau. Gọi A là tập hợp mọi tập hợp con khác rỗng của M . Số lượng phần tử của A là: 210 − 1 = 1023. Chúng ta xét tổng S các phần tử của một tập hợp con như vậy, rõ ràng : S ≤ 91 + 92 + · · ·+ 100 < 10.100 = 1000. Như vậy tồn tại không quá 1000 tổng khác nhau. Kí hiệu B là tập hợp tất cá các tổng như vậy. Do đó số lượng phần tử của B nhỏ hơn 1000 và nhỏ hơn số lượng phần tử của A. Đặt tương ứng mỗi phần tử của A với tổng các phần tử của nó. Ta thấy rằng có thể áp dụng nguyên lí Dirichlet ở đây. Suy ra tồn tại ít nhất hai tập con khác nhau có cùng một tổng các phần tử. Ví dụ 3.15 Chứng minh rằng tồn tại những số nguyên a, b và c không đồng thời bằng không và giá trị tuyệt đối của mỗi số không vượt quá 1000000, thoả mãn∣∣∣a+ b√2 + c√3∣∣∣ < 10−11. Lời giải: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 36 Đặt S là tập hợp của 1018 số thực r + s √ 2 + √ 3 , ∀r, s, t ∈ {0, 1, 2, . . . , 106 − 1} và đặt d = (1 + √ 2 + d √ 3).106. Khi đó mỗi x ∈ S thì 0 ≤ x < d.Chia đoạn này thành 108 − 1 phần bằng nhau, mỗi đoạn nhỏ có độ dài e = d 108 − 1 . Theo nguyên lí Dirichlet tồn tại hai số trong 108 số của S nằm trong cùng một đoạn nhỏ. Hiệu của hai số này là a+ b √ 2 + c √ 3 đó chính là các số a, b và c vì e < 107 1018 = 10−11. Ví dụ 3.16 Chứng minh rằng với một số tự nhiên bất kì ,tồn tại một số có dạng 111 . . .000︸ ︷︷ ︸ n mà chia hết cho n. Lời giải: Chúng ta xét những số 1, 11, 111 . . . , 111 . . .111︸ ︷︷ ︸ n số và những số dư khi chia dãy số trên cho n. Vì dãy số đã cho gồm n phần tử, nên số dư dương khác nhau khi chia chúng cho n có n− 1 phần tử. Có thể giả thiết không có một số nào trong dãy trên chia hết cho n vì nếu ngược lại thì bài toán đã được giải. Khi đó sẽ có hai số trong chúng, ví dụ: 111 . . .111︸ ︷︷ ︸ k số và 111 . . .111︸ ︷︷ ︸ l số , (l > k) mà khi chia chúng cho n sẽ cho cùng một số dư. Do đó: l − k = 111 . . .1︸ ︷︷ ︸ l−k số 000 . . .0︸ ︷︷ ︸ k số sẽ chia hết cho n. Ví dụ 3.17 Cho p là số nguyên tố lớn hơn 5. Chứng minh rằng tồn tại một số có dạng 111 . . .11 mà chia hết cho p. Lời giải: Ta xét dãy số : 1, 11, 111, . . . , 111 . . .1︸ ︷︷ ︸ p số . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 37 Nếu trong dãy trên không có số nào chia hết cho p, thì ta cho tương ứng mỗi số với số dư của phép chia. Tập hợp các số dư chỉ có 1, 2, 3, . . . , p− 1 gồm p− 1 phần tử (vì 0 không thể có trong tập này). Nhưng vì chúng ta có p số ở dạng trên, nên theo nguyên lí Dirichlet tồn tại hai số có cùng số dư. Giả sử các số đó là: 111 . . .1︸ ︷︷ ︸ m số và 111 . . . 1︸ ︷︷ ︸ n số , (m > n). Khi đó: 1 ≤ n < m ≤ p. Vậy: 111 . . .1︸ ︷︷ ︸ m số − 111 . . .1︸ ︷︷ ︸ n số = 111 . . .1︸ ︷︷ ︸ m−n số 000 . . .0︸ ︷︷ ︸ n số = 111 . . . 1︸ ︷︷ ︸ m−n số .10n. tích này chia hết cho p vì (p, 10) = 1, suy ra 111 . . . 1︸ ︷︷ ︸ m−n số chi hết cho p và nó cũng nằm trong dãy trên. Mà 1 ≤ m− n ≤ p mâu thuẫn với giả thiết không có số nào trong dãy chia hết cho p. Ví dụ 3.18 Từ tập M chọn một cách bất kì 2n + 1 số .Chứng minh rằng tồn tại hai số trong tập vừa chọn mà tích của chúng là một số chính phương. Lời giải: Nhận xét rằng mọi số tự nhiên x = pα11 p α2 2 . . . p αn n là số chính phương khi và chỉ khi tất cả các số mũ đều chẵn.Chúng ta biểu diễn mọi số đã chọn với dạng ở trên và cho tương ứng với bộ n -số: (α1, α2, . . . , αn). Ở đây α1, α2, . . . , αn là các số dư của các số mũ tương ứng α1, α2, . . . , αn khi chia cho 2. Rõ ràng αi = 0 hoặc αi = 1, ∀1 = 1, 2, . . . , n.. Vậy (α1, α2, . . . , αn) là bộ sắp thứ tự gồm n số 0 và 1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 38 Theo lý thuyết tổ hợp ,tất cả n -bộ như vậy có số lượng là 2n, còn các số ta đang xét có số lượng là: 2n+1. Như vậy ít nhất có hai số trong chúng có cùng bộ sắp xếp gồm số 0 và 1 giống nhau. Giả sử các số đó là: x = pα11 p α2 2 . . . p αn n và y = p β1 1 p β2 2 . . . p βn n với chúng có: (α1, α2, . . . , αn) = (β1, β2, . . . , βn). Đẳng thức sau cùng có nghĩa là : αi = βi, i = 1, n. Do đó các số mũ αi và βi có cùng tính chẵn lẻ như nhau với bất kì i = 1, n. Khi đó: α1 + β1, α2 + β2, . . . , αn + βn là các số chẵn và theo nhận xét ban đầu tích: x.y = (pα11 p α2 2 . . . p αn n )(p β1 1 p β2 2 . . . p βn n ) = p α1+β1 1 p α2+β2 2 . . . p αn+βn n đúng là số chính phương. Ví dụ 3.19 Chứng minh rằng giữa n + 1 số trong tập hợp M có thể chọn được một vài số mà tích của chúng là một số chính phương. Cho x1, x2, . . . , xn là những số bất kì của M . Với mỗi tập con khác rỗng {i1, i2, . . . ik} của tập hợp {1, 2, . . . , n+ 1}, chúng ta xét các xi1, xi2, . . . , xik, tất nhiên số này cũng thuộc M. Biểu diễn các số này theo dạng chuẩn và mỗi tập con {i1, i2, . . . ik} cho tương ứng với n -bộ (α1, α2, . . . , αn). Ở đây α1, α2, . . . , αn là số dư của các số mũ tương ứng α1, α2, . . . , αn khi chia cho 2. Nhưng số lượng những tập con khác rỗng của {1, 2, . . . , n+ 1} là 2n+1 − 1, còn số lượng các n -bộ sắp gồm những số 0, 1 và 2n . Suy ra tồn tại những tập con khác rỗng khác nhau {i1, i2, . . . ik} và {j1, j2, . . . jk} của {1, 2, . . . , n+ 1}, mà chúng tương ứng với cùng một n -bộ sắp của những số dư. Điều này có nghĩa là nếu : xi1xi2 . . . xik = p α1 1 p α2 2 . . . p αn n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 39 và xj1xj2 . . . xjk = p β1 1 p β2 2 . . . p βn n thì số mũ αi và βi có cùng tính chẵn lẻ với i = 1, k. Điều này có nghĩa là tích của những số xi1xi2 . . . xik vàxj1xj2 . . . xjk là chính phương. Nếu {i1, i2, . . . ik} và {j1, j2, . . . jk} không có phần tử chung, thì bài toán đã được giải. Trường hợp ngược lại, trong P = xi1, xi2, . . . , xik và xj1, xj2, . . . , xjk lặp lại đúng những số xs mà s thuộc {i1, i2, . . . ik} và {j1, j2, . . . jk}. Chúng ta loại trừ trong P tất cả những xs như vậy và nhận được tích của vài số trong số x1, x2, . . . , xn+1 mà nó đúng là số chính phương. Ví dụ 3.20 Cho k ≥ 1 và n ≥ 1 là những số tự nhiên và A là tập hợp gồm (k − 1)n+ 1 số nguyên dương, mỗi số này đều nhỏ hơn hoặc bằng kn. Chứng minh rằng ít nhất có một phần tử của A có thể biểu diễn như tổng của k phần tử trong A. Lời giải: Với k = 1 bài toán hiển nhiên đúng, chúng ta giả thiết k ≥ 2. Kí hiệu m là số nhỏ nhất thuộc A. Dễ thấy rằng m ≤ n và tồn tại đúng n−m số thuộc A mà chúng lớn hơn m nhưng không vượt quá kn. Để chứng minh bài toán chúng ta tìm hai số x và y thuộc A sao chox = y+(k− 1)m, nghĩa là biểu diễn một số nào đó thuộc A thành tổng k số hạng thuộc A trong đó k−1 số hạng bằng m. Chỉ cần tìm số x thuộc A mà x > (k−1)m và x− (k−1)m thuộc A. Thật vậy, trong khoảng ∆ = ((k − 1)m, kn) có kn− (k − 1)m = k(n−m) +m số nguyên. Vì k ≥ 2, nên(k − 1)m ≥ m, theo nhận xét ban đầu suy ra có nhiều nhất n-m số trong ∆ không thuộc A. Điều này nghĩa là A chứa ít nhất s = k(n −m) + m − (n − m) = (k − 1)(n − m) + m số. Nhưng s ≥ n ,vì (k − 2)(n − m) ≥ 0. Gọi a1, a2, . . . , as thuộc A, với (k − 1)m < ai ≤ kn, i = 1, s. Khi đó những hiệu a1 − (k − 1)m, a2 − (k − 1)m, . . . , as − (k − 1)m là những số nguyên khác nhau trong khoảng [1, kn]. Nếu một số nào đó trong chúng không thuộc A, thì theo nguyên lí Dirichlet chúng ta nhận được s ≤ n−1 , vì ngoài A còn đúng n − 1 số trong khoảng này. Như vậy trái với bất đẳng thức đã chứng minh s ≥ n. Suy ra tồn tại một hiệu ai − (k − 1)m thuộc A. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 40 Ví dụ 3.21 Cho x1, x2, x3, . . . , xn là những số thực và x21 +x22+ · · ·+x2n = 1. Chứng minh rằng với mỗi số nguyên k, k ≥ 2, tồn tại những số nguyên a1, a2, . . . , an không đồng thời bằng không sao cho |ai| ≤ k − 1, i = 1, n và thoả mãn bất phương trình sau: |a1x1 + a2x2 + · · ·+ anxn| ≤ (k − 1) √ n kn − 1 . Lời giải: Chúng ta sử dụng bất đẳng thức Cosi-Buniakovski-Svars: |α1β1 + α2β2 + · · ·+ αnβn| ≤ √ α21 + · · ·+ α2n √ β21 + · · ·+ β2n đúng với mọi số thực α1, α2, . . . , αn, β1, β2, . . . , βn, dấu bằng xảy ra khi và chỉ khi tồn tại một số λ sao cho α1 = λβ1, α2 = λβ2, . . . , αn = λβn. Bây giờ chúng ta xét các số : y0 = −k − 12 , y1 = − k − 1 2 + 1, . . . , yk−1 = −k − 12 + (k − 1) = k − 1 2 Số lượng của chúng là k và hiệu từng cặp trong chúng là các số nguyên, mà giá trị tuyệt đối của nó không vượt quá k − 1. Mỗi bộ sắp xếp n -thành phần: β = (b1, b2, . . . , bn), ở đây bi là một số nào đó trong y1, y2, . . . , yn, (i = 1, n), chúng ta đặt tương ứng với mỗi số Sβ = b1x1 + b2x2 + · · ·+ bnxn. Từ bất đẳng thức Cosi: Sβ = b1x1 + b2x2 + · · ·+ bnxn ≤ √ b21 + b 2 2 + · · ·+ b2n √ x21 + x 2 2 + · · ·+ x2n = √ b21 + b 2 2 + · · ·+ b2n Nhưng ∣∣∣∣bi ≤ k − 12 ∣∣∣∣ , i = 1, n sao cho: ∣∣Sβ∣∣ ≤√b21 + b22 + · · ·+ b2n ≤ k − 12 √n hoặc là: −k − 1 2 . √ n ≤ Sβ ≤ k − 12 . √ n. Theo phương pháp này n-bộ β = (b1, b2, . . . , bn), ở đây bi là một trong các số y0, y1, . . . , yk−1, i = 1, n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 41 được đặt tương ứng với bộ số Sβ = b1x1 + b2x2 + · · ·+ bnxn trong đoạn ∆ = [ −k − 1 2 √ n, k − 1 2 √ n ] . Số lượng n - bộ được sắp xếp là kn. Chia ∆ ra kn − 1 đoạn nhỏ với độ dài k − 1 kn − 1 √ n Từ nguyên lí Dirichlet suy ra tồn tại hai n - bộ β = (b1, b2, . . . , bn) và γ = (c1, c2, . . . , cn), mà những số: Sβ = b1x1 + b2x2 + · · ·+ bnxn và Sγ = c1x1 + c2x2 + · · ·+ cnxn tương ứng với chúng nằm trong cùng một đoạn nhỏ. Đặt a1 = b1 − c1, a2 = b2 − c2, . . . , an = bn − cn. Dễ kiểm tra được a1, a2, . . . , an thoả mãn điều kiện đã cho. Thật vậy, với mọi i = 1, n số ai = bi−ci là hiệu của hai số nào đó trong y0, y1, . . . , yk−1 như đã nói ở trên và là số nguyên không vượt quá k − 1 .Vì hai n - bộ trên khác nhau hoàn toàn thì ít nhất một trong các số ai = bi − ci khác không . Ngoài ra: |b1x1 + b2x2 + · · ·+ bnxn| = ∣∣x1(b1 − c1) + x2(b2 − c2) + · · ·+ xn(bn − cn))∣∣ = ∣∣Sβ − Sγ∣∣ ≤ k − 1 kn − 1 . √ n. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 4 Ứng dụng nguyên lí Dirichlet vào các bài toán khác Ở chương II và chương III chung ta đã thấy điều thú vị của việc áp dụng nguyên lí Dirichlet để giải các bài toán hình học tổ hợp và số học. Chúng ta còn sẽ thấy điều thú vị đó qua một số bài toán khác sau đây, để thấy được ứng dụng to lớn của nguyên lí Dirichlet. Ví dụ 4.1 Giả sử trong tập hợp hữu hạn X chọn ra 50 tập hợp con A1, A2, . . . , A50 sao cho mỗi tập con chứa hơn một nửa phần tử của tập X.Chứng minh rằng có thể tìm được tập con B ⊂ X không chứa nhiều hơn 5 phần tử và có ít nhất một phần chung cho các tập hợp A1, A2, . . . , A50. Lời giải: Giả sử số các phần trong tập X bằng n. Mỗi tập hợp con được chọn A1, A2, . . . , A50 chứa không ít hơn n 2 phần tử, có nghĩa là tổng số các phần tử của tất cả các tập này vượt quá 50. n 2 = 25.n. Theo nguyên lí Dirichlet thì tồn tại một phần tử của X thuộc không ít hơn 26 tập con đã chọn. Tương tự ta chứng minh với giá trị bất kì k < 50 giữa các tập Ai1, Ai2, . . . , Aik có thể chọn ra không ít hơn [ k 2 ] + 1 tập hợp chứa cùng một phần tử. Ta lấy phần tử của tập hợp X mà nó thuộc không ít hơn 26 tập (phần tử này sẽ là một trong 5 phần tử của tập hợp B). Ta loại ra 26 tập mà chứa phần tử đang xét. Khi đó tìm được một phần tử thuộc ít nhất 13 từ 24 tập còn lại. Ta loại 13 tập này ra, khi đó giữa 11 tập còn lại tìm được một phần tử thuộc không ít hơn 5 trong số các tập hợp. Đối với 5 tập còn lại tìm được một phần tử thuộc không ít hơn 3 trong số 42 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 43 chúng . Và cuối cùng tồn tại một phần tử thuộc hai tập cuối cùng. Như vậy ta tìm được không nhiều hơn 5 phần tử của tập X (có thể ít hơn vì một vài phần tử sẽ trùng nhau), chúng sẽ tạo thành tập B. Ngoài ra một tập bất kì từ A1, A2, . . . , A50 chứa ít nhất 1 trong các phần tử đó. Ví dụ 4.2 Đối với mỗi giá trị n ∈ N , hãy tìm số k lớn nhất k ∈ N thoả mãn tính chất sau: Trong tập hợp gồm n phần tử có thể chọn ra k tập hợp con khác nhau, sao cho hai tập con bất kì đều có giao khác ∅. Lời giải: Cố định phần tử ai của tập X = {a1, a2, . . . , an} và chỉ xét các tập con chứa phần tử a1. Số các tập hợp như vậy bằng số các tập con của tập X = {a1, a2, . . . , an}, nghĩa là bằng 2n−1. Suy ra k ≥ 2n−1. Mặt khác giả sử đã chọn được hơn 2n−1 tập con của X Ta chia tất cả các tập con của X thành 2n−1 cặp được tạo bởi từ một tập con của X và phần bù của nó. Theo nguyên lí Dirichlet có ít nhất 2 tập con đã chọn tạo thành 1 cặp, suy ra chúng không giao nhau. Vậy k = 2n−1. Ví dụ 4.3 Các hàm số f, g, h : N → N thoả mãn ba điều kiện sau: 1. Hàm h(n) không nhận giá trị nào tại nhiều hơn một điểm n ∈ N. 2. Tập hợp giá trị hàm số g(n) là N. 3. f(n) ≡ g(n)− h(n) + 1, n ∈ N. Chứng minh rằng đồng nhất thức f(n) ≡ 1, n ∈ N là đúng. Lời giải: Ta chứng minh đồng nhất thức g(n) ≡ h(n), n ∈ N.Từ đó và điều kiện (2) sẽ dẫn đến: f(n) ≡ g(n)− h(n) + 1 ≡ 1, n ∈ N. Với bất kì n ∈ N ta có: h(n) = g(n) + 1− f(n) ≤ g(n);vìf(n) ≥ 1 Giả sử rằng, với giá trị nào đó n ∈ N đẳng thức g(n) = h(n) không đúng, khi đó h(n) < g(n) = k. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 44 Theo điều kiện (2) ta tìm các số n1, n2, . . . , nk−1 ∈ N, để sao cho g(ni) = i, i = 1, k − 1. Bởi vậy mỗi số trong k số h(n1), h(n2), . . . , h(nk−1), h(n) thuộc vào tập hợp {1, 2, . . . , k − 1}, do đó theo nguyên lí Dirichlet hàm số h(n) nhận giá trị nào đó nhiều hơn một lần, điều này trái với điều kiện (1). Khẳng định được chứng minh. Ví dụ 4.4 Cho dãy số nguyên u1, u2, . . . , un,với n ≥ 2. Chứng minh rằng tồn tại dãy con uk1, uk2, . . . , ukm trong đó 1 ≤ k1 < k2 < · · · < km ≤ n sao cho: u2k1 + u 2 k2 + · · ·+ u2km. Lời giải: Xét n+1 số: 0, u21, u 2 1 + u 2 2, u 2 1 + u 2 2 + u 2 3, . . . , u 2 1 + · · ·+ u2n chia các số này cho n, thì chúng có nhiều nhất n số dư. Theo nguyên lí Dirichlet tồn tại hai số có cùng số dư, giả sử đó là : u21 + · · ·+ u2j và u21 + · · ·+ u2k, 0 ≤ j < k ≤ n có nghĩa là số: (u21 + · · ·+ u2j)− (u21 + · · ·+ u2k) chia hết cho n hoặc: uj+1 + uj+2 + · · ·+ uk chia hết cho n. Dãy con phải tìm là uj+1, uj+2, . . . , uk. Ví dụ 4.5 Cho x1, x2, x3, . . . là dãy vô hạn các số nguyên và k là một số tự nhiên bất kì. Chứng minh rằng tồn tại dãy số gồm những phần tử liên tiếp của dãy, mà tổng của chúng chia hết cho k. Lời giải: Chúng ta có thể giới hạn lại, giữa mọi bộ k phần tử liên tiếp của dãy có thể chọn được một số phần tử có tính chất mong muốn. Để đơn giản ta xem xét k phần tử đầu tiên: x1, x2, . . . , xk . Chúng ta xét tổng: S1 = x1, S2 = x1 + x2, S3 = x1 + x2 + x3, . . . , Sk = x1 + x2 + · · ·+ xk. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 45 Nếu một tổng nào đó trong số trên chia hết cho k, thì bài toán được giải. Ngược lại, các số S1, S2, . . . , Sk, (có số lượng k) khi chia cho k được các số dư: 1, 2, 3, . . . , k−1. Từ nguyên lí Dirichlet suy ra có một cặp chỉ số i và j, 1 ≤ i < j ≤ k, mà các tổng Si và Sj cho cùng một số dư khi chia cho k. Khi đó tổng các phần tử liên tiếp: xi+1, xn+2, . . . , xj của dãy đã chia hết cho k, vì xi+1 + xn+2 + · · ·+ xj = Sj − Si. Ví dụ 4.6 Cho dãy vô hạn các chữ số. Chứng minh rằng với mọi số tự nhiên n, nguyên tố cùng nhau với 10, trong dãy vô hạn trên tồn tại một nhóm chữ số liên tiếp, mà số tạo bởi các chữ số trong nhóm (viết theo thứ tự chỉ số lớn đứng trước) chia hết cho n. Lời giải: Cho dãy các chữ số a1, a2, . . . , an, . . . . Chúng ta xét các số A1 = a1, A2 = a2a1, . . . , An = anan−1 . . . a1, An+1 = an+1 . . . a1 Vì số lượng những số này là n + 1, còn số lượng khả năng của số dư khi chia chúng cho n là n, nên theo nguyên lí Dirichlet tồn tại ít nhất hai số cho cùng số dư ta kí hiệu chúng là Ai và Aj, (i < j). Khi đó hiệu Aj −Ai chia hết cho n. Hay nói cách khác: Aj −Ai = aj . . . a1 − ai . . . a1 = aj . . . ai−1.10j−i+1. Vì (n, 10) = 1 nên aj . . . ai−1 chia hết cho n. Ví dụ 4.7 Một hội toán học bao gồm các thành viên ở 6 nước. Danh sách các hội viên gồm 1978 người được đánh số báo danh từ 1 đến 1978. Chứng minh rằng tồn tại ít nhất một hội viên có số báo danh gấp đôi số báo danh của một hội viên khác cùng nước, hoặc bằng tổng hai số báo danh của hai hội viên cùng một nước với mình. Lời giải: Từ 329.6 < 1978 suy ra một trong các nước (kí hiệu là A) có không ít hơn 330 đại biểu trong hội và chúng ta có thể viết số báo danh a1 < a2 < · · · < a330 < . . . . Chúng ta xét những hiệu: xi − a330 − ai, i = 1, 329. Nếu có một số xi nào đó trùng với aj (số báo danh của một đại biểu của A) thì chúng ta có a330 = ai + aj. Bài toán đã chứng minh xong. Nếu xi 6= aj thì với mọi i, j, thì số xi là số báo danh của một đại biểu thuộc 5 nước còn lại. Bây giờ, vì 65.5 < 329, thì ít nhất có một trong 5 nước này (kí hiệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 46 là B) sẽ có không ít hơn 66 thành viên, mà số báo danh của họ là một trong các số:x1, x2, . . . , x329. Cho các số đó là b1 < b2 < · · · < b66 < . . . với bi = xn, i = 1, 66. Chúng ta lại xét hiệu yi = b66 − bi, i = 1, 65. Nếu trong một hiệu nào đó trùng với số báo danh bi của một đại biểu nước B thì b66 = bi + bj . Nếu với hai số i và k nào đó chúng ta có yi = ak, thì ak = b66 − bi = xn66 − xni = a330 − an66 − (a330 − ani) = ani − an66 hoặc là ani = a66 + ak. Nếu hai trường hợp trên không xảy ra, thì những số báo danh này sẽ là số báo danh của đại biểu 4 nước còn lại và suy ra ít nhất một trong các nước này có số hội viên ít nhất là 17 với số báo danh yi . Tiếp tục quá trình như vậy và lặp lại lí luận trên chúng ta có kết luận của bài toán. Ví dụ 4.8 Giả sử a và x là hai số tự nhiên thực sự lớn hơn 1 và (x, a−1) = 1. Dãy số vô hạn un được xác định như sau: un = ax n − a+ 1, n = 1, 2, . . . . Chứng minh rằng trong dãy số nói trên chứa vô hạn số đôi một nguyên tố cùng nhau. Lời giải: Giả thiết phản chứng trong dãy số chỉ có hữu hạn số ui1, ui2, . . . , uik nguyên tố cùng nhau. Đặt q = ui1ui2 . . . uik . Xét q + 1 số sau: a, ax, ax2, . . . , axq. Theo nguyên lí Dirichlet tồn tại hai số nguyên r và s sao cho 0 ≤ r < s ≤ q và axr ≡ axs(modq) ⇒ axr − axs ≡ 0(modq) hay: axr(1− xs−r) ≡ 0(modq). (4.1) Theo giả thiết ta có (x, a− 1) = 1 nên suy ra (axr, uij) = 1, ∀j = 1, k. (4.2) Từ (4.2) suy ra: (axr, q) = 1. (4.3) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 47 Từ (4.1) và (4.3) ta có: xs−r ≡ 1(modq) ⇒ xs−r = lq + 1, l ∈ N. Xét số: uik+j = ax s−r − a+ 1. Vậy: uik+j = a(lq + 1− a+ 1). (4.4) Từ (4) ta có: (uik+j , uij) = 1, ∀j = 1, k. (4.5) Hệ thức (4.5) chứng tỏ rằng luôn có thể bổ sung thêm vào bộ số: q = ui1ui2 . . . uik các số mới, mà bộ này vẫn thoả mãn điều kiện: Bất kì hai số nào cũng nguyên tố cùng nhau. Điều này có nghĩa là trong dãy un đã cho có vô hạn số đôi một nguyên tố cùng nhau. Ví dụ 4.9 Cho {un} là dãy các số tự nhiên tăng dần: u1 < u2 < u3 < . . . và thoả mãn điều kiện: u1 = 1, un+1 ≤ 2n, ∀n ∈ N. Chứng minh rằng với mọi số tự nhiên n tồn tại các số hạng up và uq của dãy sao cho up − uq = n. Lời giải: Giả sử n ∈ N là số tự nhiên cho trước. Từ giả thiết suy ra mỗi số hạng: u1, u2, u3, . . . , un+1 không vượt quá 2n. Xét tập hợp 2n số tự nhiên sau {1, 2, . . . , 2n}. Chúng chia tập hợp này thành n cặp: (1, n+ 1), (2, n+ 2), . . . , (n, 2n). Do tập hợp trên chứa không ít hơn n + 1 phần tử của dãy un đã cho (vì nói riêng u1, u2, . . . , un+1 đã thuộc tập hợp ấy), vậy theo nguyên lí Dirichlet tồn tại hai số hạng khác nhau up và uq của dãy thuộc vào một cặp (giả sử up > uq). Nhưng hiệu số của mỗi cặp đều bằng n nên chúng ta có : up − uq = n. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 48 Ví dụ 4.10 Cho uk, k = 1, n là dãy số tự nhiên sao cho: 1 ≤ u1 ≤ u2 ≤ · · · ≤ un và u1 + u2 + · · ·+ un = 2n. Chứng minh rằng nếu n chẵn và un 6= n+1 , thì từ dãy trên luôn chọn ra được một dãy con mà tổng các số hạng của dãy con đó bằng n. Lời giải: Đặt Sk = u1 + u2 + · · ·+ un, k = 1, n. Xét n + 2 số {0, u1 − un, S1, S2, . . . , Sn}. Theo nguyên lí Dirichlet thì ít nhất hai số khi chia chia cho n cùng phần dư.Vậy chỉ có 4 khả năng sau đây: 1. (u1 − un) chia hết cho n. Do: u1 + u2 + · · ·+ un ≥ nu1 ⇒ 2n ≥ nu1 ⇒ u1 ≤ 2. (a) Nếu u1 = 2 thì từ 1 ≤ u1 ≤ u2 ≤ · · · ≤ un và u1 + u2 + · · ·+ un = 2n suy ra: u1 = u2 = · · · = un = 2. Do n chẵn nên n = 2m .Vậy: u1 = u2 = · · · = un = 2m = n (b) Nếu u1 < 2 thì từ u1 − un chia hết cho n, suy ra un = 1 hoặc là un = 1+ n(do u1 nguyên nên u1 = 1 và 1 ≤ un ≤ 2n suy ra được kết luận trên ). Nhưng un 6= n + 1 suy ra u1 = 1. Mặt khác: 1 ≤ u1 ≤ u2 ≤ · · · ≤ un Vậy thì u2 = u3 = · · · = un−1 = 1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 49 Suy ra :u1 + u2 + · · ·+ un = n, vô lí. Như vậy trong trường hợp này ta chỉ ra tồn tại dãy con u1, u2, . . . , um sao cho u1 + u2 + · · ·+ um với m = n2 . 2. Sj − Si, j > i chia hết cho n Ta có Sj − Si = ui+1 + ui+2 + · · ·+ uj Rõ ràng vế phải của đẳng thức trên có ít nhất một số hạng mà uk ≥ 1, ∀k = 1, n, suy ra Sj − Si ≥ 1. Mặt khác cũng hiệu trên nếu không đủ các phần tử của dãy thì bao giờ ta cũng có: Sj − Si < u1 + u2 + · · ·+ un ≤ 2n− 1. Do đó cuối cùng ta có: 1 ≤ Sj − Si < u1 + u2 + · · ·+ un ≤ 2n− 1 mà Sj − Si chia hết cho n. Điều này chỉ xảy ra khi Sj − Si = n hoặc ui+1 + ui+2 + · · ·+ uj = n. 3. Si chia hết cho n. Ta có 1 ≤ Si ≤ Sn−1 = 2n− un < Si mà Si chia hết cho n,suy ra Si = n hoặc là u1 + u2 + · · ·+ ui chia hết cho n. 4. Sk và u1 − un cho cùng phần dư khi chia cho n, với k nào đó, 1 ≤ k ≤ n− 1. Suy ra Sk(u1 − un)|n ⇒ (u1 + u2 + · · ·+ uk + un)|n. Mà u2 + u3 + · · ·+ uk + un ≤ 2n− u1 < 2n. Suy ra: u2 + u3 + · · ·+ uk + un = n. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 50 Tóm lại luôn luôn chọn được dãy con mà tổng của chúng bằng n. Ví dụ 4.11 Cho tập hợp gồm 10 số có 2 chữ số. Chứng minh rằng tập hợp đó có ít nhất hai tập con không giao nhau, mà tổng những phần tử trong chúng bằng nhau. Lời giải: Nếu có hai tập con giao nhau mà mà tổng trong chúng bằng nhau thì chúng ta có thể bỏ những phần tử chung đi. Khi đó còn lại hai tập không giao nhau và tổng các phần tử trong chúng vẫn bằng nhau. Chúng ta tính có bao nhiêu tập con không rỗng của một tập hợp có 10 phần tử. Số lượng những tập con chỉ chứa một phần tử có C110. Số lượng những tập con chứa 2 phần tử có C210. Số lượng những tập con chứa 3 phần tử có C310,. . . Số lượng những tập con chứa 10 phần tử có C1010 . Suy ra tổng số lượng các tập hợp con là: C110 + C 2 10 + C 3 10 + · · ·+ C1010 = 210 = 1024. Điều kiện bài ra là 10 số gồm hai chữ số suy ra các số nhỏ hơn hoặc bằng 99. Vậy tổng của các số trong mỗi tập hợp con không vượt quá 99.10 = 990. Như vậy số lượng những tổng khác nhau nhiều nhất là 990. Theo nguyên lí Dirichlet trong số 1024 tập con của tập hợp gồm 10 số sẽ có ít nhất hai tập mà tổng các phần tử trong chúng phải bằng nhau. Ví dụ 4.12 Tổng độ dài một số véc tơ trong mặt phẳng là 4. Chứng minh rằng từ những véc tơ này có thể chọn ra một số véc tơ mà độ dài của chúng lớn hơn 1. Lời giải: Ta đưa vào hệ trục toạ độ và xét véc tơ đại diện những véc tơ đã cho tại điểm gốc, ta chiếu những véc tơ này xuống trục toạ độ Ox và Oy. Vì mỗi véc tơ có độ dài nhỏ hơn tổng của các độ dài hình chiếu của nó xuống hai trục nên tổng độ dài của tất cả các hình chiếu của các véc tơ lớn hơn 4. Khi đó trên ít nhất một trong 4 nửa trục của hệ toạ độ tổng độ dài của hình chiếu sẽ lớn hơn 1, điều đó có nghĩa là tổng độ dài của những véc tơ tương ứng sẽ lớn hơn 1 (độ dài hình chiếu lớn hơn thì tất nhiên độ dài véc tơ cũng lớn hơn). Ví dụ 4.13 Cho 7 số thực bất kì. Chứng minh rằng giữa chúng có thể chọn được hai số, chẳng hạn x và y , sao cho: 0 ≤ x− y 1 + xy ≤ √ 3 3 . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 51 Lời giải: Các số đã cho kí hiệu là x1, x2, . . . , x7. Mục đích của chúng ta là biểu diễn mọi số dưới dạng xi = tanαi, ở đây αi là một số trong khoảng (−pi2 ; pi 2 ), i = 1, 7. Chúng ta chia đoạn này thành ra 6 đoạn con có độ dài bằng nhau, nghĩa là bằng pi 6 . Theo nguyên lí Dirichlet ta có ít nhất hai số trong α1, α2, . . . , α7 cùng nằm trong một đoạn con đó. Nếu chúng ta kí hiệu các số đó là αi và αj; αi ≥ αj, thì từ đó suy ra: 0 ≤ αi − αj ≤ pi6 . Vì hàm số tan tăng trong khoảng (−pi 2 ; pi 2 ).Suy ra: 0 ≤ tan (αi − αj) = tanαi − tanαj1 + tanαi tanαj = xi − xj 1 + xixj ≤ tan pi 6 = √ 3 3 . Chú ý: Bằng cách giải của bài toán trên ta có bài toán sau với lời giải tương tự, cách giải khác khó mà thực hiện được. Ví dụ 4.14 Cho 4 số dương bất kì. Chứng minh rằng có hai trong bốn số đó, chẳng hạn x và y, thoả mãn bất phương trình sau: 0 < x− y 1 + x + y + 2xy ≤ √ 3. Lời giải: Gọi các số đã cho là x1, x2, x3, x4. Đặt yi = 1 + 1 xi , i = 1, 2, 3, 4. Đặt yi = tanαi, αi ∈ (−pi2 , pi 2 ) ra làm ba đoạn, mỗi đoạn bằng pi 3 . Suy ra tồn tại hai số αi, αj thuộc cùng một đoạn (theo nguyên lí Dirichlet). ⇒ 0 < αi − αj ≤ pi3 ⇒ 0 < tan(αi − αj) ≤ tan pi3 = √ 3 ⇒ 0 < tanαi − tanαj 1 + tanαi tanαj ≤ √ 3 ⇒ 0 < yi − yj 1 + yiyj ≤ √ 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 52 ⇒ 0 < 1 + 1 xi − 1− 1 xj 1 + (1 + 1 xi )(1 + 1 xj ) ≤ √ 3 ⇒ 0 < xj − xi xixj + (1 + xi)(1 + xj) ≤ √ 3 ⇒ 0 < xj − xi 1 + xi + xj + 2xixj ≤ √ 3. Ví dụ 4.15 Chứng minh rằng mỗi bộ số 11 số thực khác nhau trong khoảng [1, 1000] có thể chọn được hai số x và y mà chúng thoả mãn bất đẳng thức sau: 0 < x− y < 1 + 3 3√xy. Lời giải: Ta xét căn bậc ba của các số trong bộ số đã cho x1, x2, . . . , x11. Từ điều kiện xi ∈ [1, 1000] đã cho suy ra 1 ≤ 3√xi ≤ 10, (i = 1, . . . , 11). Ta chia khoảng [1, 1000] ra 10 phần bằng nhau. Có tất cả 11 số 3 √ x1, 3 √ x2, . . . , 3 √ x11. Theo nguyên lí Dirichlet suy ra có ít nhất 2 trong số 11 số đó nằm trong cùng một đoạn nhỏ. Giả sử hai số đó là 3√xi, 3√xj , (i 6= j) và xi > xj . ⇒ 0 < 3√xi − 3√xj ≤ 910 < 1 ⇒ 0 < ( 3√xi − 3√xj)3 < 13 ⇒ 0 < xi − xj − 3. 3 √ x2i xj + 3 3 √ xix2j < 1 3 ⇒ 0 < xi − xj < 1 + 3 3 √ x2i xj − 3 3 √ xix2j ⇒ 0 < xi − xj < 1 + 3 3√xixj( 3√xi − 3√xj), vì 0 < 3√xi − 3√xj < 1 ⇒ 0 < xi − xj < 1 + 3 3√xixj . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Tài liệu tham khảo [1] Nguyễn Hữu Điển, Phương pháp DIRICHLET và ứng dụng, NXB Khoa học và kĩ thuật Hà nội, 1999. [2] Phan Huy Khải, Các bài toán hình học tổ hợp, NXB Giáo dục, 2007. [3] Phan Huy Khải, Các bài toán cơ bản của số học, NXB Giáo dục, 2009. [4] Phan Huy Khải, Số học và dãy số, NXB Giáo dục, 2009. [5] Nguyễn Vũ Thanh, Số học, NXB Giáo dục, 2006. [6] Phạm Minh Phương, Các chuyên đề số học, NXB Giáo dục, 2006. [7] Nguyễn Văn Vĩnh, 23 chuyên đề giải 1001 bài toán sơ cấp, NXB Giáo dục, 2005. [8] Tập san Toán học tuổi trẻ các năm. 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên