🔙 Quay lại trang tải sách pdf ebook Phương pháp Dirichlet và Ứng dụng Ebooks Nhóm Zalo NGUYỄN HỮU ĐIỂN PHƯƠNG PHÁP ĐIRICHLÊ VÀ ỨNG DỤNG NHÀ XUẤT BẢN KHOA HỌC VÀ KỸ THUẬT HÀ NỘI - 1999 LỜI NÓI ĐẦU Nguyên lý những cái lồng và các chú thỏ đã được biết đến từ rất lâu. Ngay trong chương trình phổ thông cơ sở chúng ta cũng đã làm quen với phương pháp giải toán này. Thực ra nguyên lý này mang tên nhà bác học người Đức Pête Gutxtap Legien Dirichlet (1805- 1859). Nguyên lý phát biểu rất đơn giản: Nếu chúng ta nhốt thỏ vào các lồng mà số lồng ít hơn số thỏ, thì thể nào cũng có một lồng nhốt ít nhất hai con thỏ. Chỉ bằng nguyên lý đơn giản như vậy hàng loạt các bài toán đã được giải. Cuốn sách được biên soạn lại theo từng chủ đề có liên quan đến nguyên lý, mỗi cách giải trong ví dụ của từng chương là áp dụng điển hình nguyên lý Đirichlê. Bài tập giải trước có liên quan đến bài giải sau nên cần lưu ý khia đọc sách. Với mong muốn cùng bạn đọc thảo luận một phương pháp chứng minh toán học và hy vọng cung cấp một tài liệu bổ ích cho các thầy cô giáo và các em học sinh ham mê tìm tòi trong toán học, tác giả mạnh dạn biên soạn cuốn sách này. Do khả năng và thời gian còn hạn chế, cuốn sách chắc chắn không tránh khỏi thiếu sót. Chúng tôi mong được sự đóng góp ý kiến của đọc giả. Thư góp ý xin gửi về Nhà xuất bản Khoa học và Kỹ thuật - 70 Trần Hưng Đạo, Hà Nội. Tác giả xin chân thành cảm ơn PGS-TSKH Đỗ Hồng Tân đã đọc và đóng góp nhiều ý kiến quí báu trong quá trình hoàn chỉnh bản thảo. Tác giả 3 CHƯƠNG 1 NGUYÊN LÝ ĐIRICHLÊ VÀ VÍ DỤ 1.1. Nguyên lý Đirichlê . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1. NGUYÊN LÝ ĐIRICHLÊ Nguyên lý Đirichlê nhiều khi người ta gọi là ¨Nguyên lý những ngăn kéo¨. Đây là một nguyên lý rất đơn giản, đặc biệt có nhiều ứng dụng trong các lĩnh vực khác nhau của toán học. Dùng nguyên lý này người ta dễ dàng chứng minh tồn tại một đối tượng với tính chất xác định. Dạng đơn giản nhất có thể phát biểu như sau: Nếu có m vật đặt vào n cái ngăn kéo và m > n thì có ít nhất một ngăn kéo chứa ít nhất hai vật. Tuy rằng với nguyên lý này người ta chỉ chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm được vật cụ thể, nhưng trong thực tế nhiều bài toán ta chỉ cần chỉ ra sự tồn tại là đủ rồi. Nguyên lý Đirichlê là một định lý về tập hợp hữu hạn. Phát biểu chính xác nguyên lý này như sau: Cho A và B là hai tập hợp không rỗng có số phần tử hữu hạn, mà 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 qui tắc nào đấy, mỗi phần tử của A cho tương ứng với một 1.2. Ví dụ 5 phần tử B, thì tồn tại hai phần tử khác nhau của A mà chúng tương ứng với cùng một phần tử của B. Để dễ hiểu ta cứ cho rằng các phần tử của tập B là ¨Những ngăn kéo¨ và các phần tử của A được đặt vào các ngăn kéo của nó. Trong phát biểu của nguyên lý trên các phần tử hữu hạn được tính bằng số tự nhiên, vì vậy Nguyên lý Đirichlê có liên quan mật thiết tới tập hợp số tự nhiên và các tính chất của tập hợp số này. 1.2. VÍ DỤ Ví dụ 1.1. Để kỷ niệm 20 năm ngày giải phóng Miền Nam, tại một thành phố người ta tổ chức buổi lễ gặp mặt những người 20 tuổi. Ngày 30 tháng 4 năm đó trong buổi gặp mặt có 400 thanh niên. Chứng minh rằng có ít nhất hai người trong số người tới dự cùng chung một ngày sinh. Lời giải. Năm 1995 có 365 ngày. Chúng ta coi mỗi ngày như một ngăn kéo và đánh số từ 1 đến 365 (ngăn kéo cuối cùng là ngày 31 tháng 12 năm 1995). Chúng ta đặt những thanh niên có ngày sinh tương ứng vào các ngăn kéo đó. Nhưng số thanh niên đến dự lễ lớn hơn số ngăn kéo, theo nguyên lý Đirichlê có ít nhất hai người được đặt vào cùng một ngăn kéo. Điều đó có nghĩa là họ sinh cùng một ngày. J Ví dụ 1.2. Trong sinh học người ta biết rằng số tóc trên đầu của mỗi người không quá 200.000 cái. Chứng minh rằng trong số người của thành phố Hà Nội, với số dân hơn 2.000.000, có ít nhất 11 người có cùng số tóc. Lời giải. Chúng ta xét 200.000 ngăn kéo được đánh số từ 0 đến 199.999. Chúng ta ¨đặt¨ mỗi người dân Hà nội vào một ngăn kéo 6 Chương 1. Nguyên lý Đirichlê và ví dụ mà số tóc bằng số thứ tự của ngăn kéo. Giả sử không có 11 người có cùng số tóc, như vậy mỗi ngăn có nhiều nhất là 10 người có cùng số tóc, do đó số dân Hà nội nhiều nhất là 200.000×10=2.000.000, điều này không đúng với giả thiết là số dân Hà nội lớn hơn 2 triệu. J Ví dụ 1.3. Ba mươi học sinh làm bài viết chính tả. Một trong số học sinh đó bị 14 lỗi, còn các học sinh khác mắc lỗi ít hơn. Chứng minh rằng có ít nhất ba người mắc số lỗi bằng nhau. Lời giải. Chúng ta xét 15 ngăn kéo được đánh số từ 0 đến 14. Chúng ta ¨đặt¨ mỗi học sinh vào một ngăn kéo mang số đúng bằng số lỗi của học sinh này. Nếu không có ba học sinh nào có số lỗi bằng nhau, thì trong mỗi ngăn mang số từ 0,1,2,. . . ,13 sẽ có nhiều nhất hai học sinh. Khi đó số lượng của những học sinh này nhiều nhất là 28. Nếu thêm vào đó học sinh mắc 14 lỗi (trong ngăn kéo số 14) chúng ta sẽ nhận được nhiều nhất 29 học sinh viết chính tả, điều này dẫn đến sự vô lý với điều kiện đã cho. J Ví dụ 1.4. Chứng minh rằng trong mỗi nhóm bạn 5 người có ít nhất hai người có cùng số lượng người quen giữa những người trong nhóm đos. Chứng minh rằng cùng kết luận như vậy với nhóm bạn có số lượng thành viên bất kỳ. Lời giải. Chúng ta xét năm ngăn kéo, đánh số từ 0 đến 4. Mỗi người tham dự được đặt vào ngăn kéo mang số trùng với số người trong nhóm mà người đó quen. a) Nếu có một người không quen ai cả trong số những người còn lại, thì ngăn số 4 là trống (vì ngược lại thì cả hai ngăn 0 và 4 đều không trống, dẫn đến vô lý). Như vậy, mỗi người trong số 5 1.2. Ví dụ 7 người được đặt vào các ngăn mang số 0,1,2,3 với số lượng 4 ngăn. Từ nguyên lý Đirichlê suy ra ít nhất có hai người ở trong một ngăn, hay là, họ có chung số lượng người quen. b) Nếu mọi người có ít nhất một người quen, mỗi người sẽ được đặt vào các ngăn mang số 1,2,3,4, với số lượng 4 ngăn. Phần còn lại áp dụng nguyên lý Đirichlê. J Ví dụ 1.5. Trong một giải bóng đá tham dự 16 đội. Mỗi cặp hai đội phải đấu với nhau. Chứng minh rằng tại mỗi thời điểm của giải có ít nhất 2 đội có số trận đã đấu như nhau. Lời giải. Chúng ta xét 16 ngăn kéo đánh số từ 0 đến 15. Chú ý rằng 15 là số lượng lớn nhất các trận bóng mà mỗi đội có thể đấu tại thời điểm đang xét. Hãy đặt mỗi đội bóng vào ngăn kéo mang số bằng số các trận mà đội đã đấu đến thời điểm đó. Chúng ta nhận ra rằng các ngăn 0 và 15 không thể đồng thời không trống được và như vậy có thể áp dụng nguyên lý Đirichlê. J Ví dụ 1.6. Trên trái đất sống hơn 5 tỷ người, biết rằng không quá 1% sống trên một trăm tuổi. Chứng minh rằng ít nhất có hai người sinh cùng một giây đồng hồ. Lời giải. Theo dương lịch hiện hành 100 năm có ít hơn 37000 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. Từ điều kiện chúng ta tìm được những người trên trái đất không quá 100 tuổi ít nhất là 99% từ 5 tỷ người nghĩa là ít nhất có 4,9 tỷ. Việc còn lại áp dụng nguyên lý Đirichlê: đặt 4,9 tỷ người vào 3,33 tỷ ngăn kéo. J Ví dụ 1.7. Trong thời gian kéo dài một năm học một học sinh giải ít nhất một bài tập mỗi ngày. Để tránh căng thẳng học sinh giải hàng 8 Chương 1. Nguyên lý Đirichlê và ví dụ tuần không quá 12 bài tập. Chứng minh rằng trong thời gian kéo dài liên tục một số ngày học sinh này phải giải đúng 20 bài tập mỗi ngày. Lời giải. Chúng ta ký hiệu a1 là số lượng bài tập học sinh đã giải trong ngày đầu tiên, a2 là số lượng bài tập đã giải trong hai ngày đầu, a3 là số lượng bài tập đã giải trong ba ngày đầu, và v.v. a77 là số lượng bài tập đã giải trong 77 ngày đầu (11 tuần). Theo giả thiết a77 ≤ 11.12 = 132. Chúng ta xét tập hợp các số tự nhiên M = {a1, a2, a3, . . . , a77, a1 + 20, a2 + 20, a3 + 20, . . . , a77 + 20}. Nó chứa 154 phần tử và số lớn nhất trong chúng là a77 + 20 ≤ 152. Theo nguyên lý Đirichlê trong M có ít nhất hai số bằng nhau. Nhưng các số a1, a2, a3, . . . , a77 là hoàn toàn khác nhau. suy ra tồn tại ak và al mà ak = al + 20, l < k ≤ 77. Như vậy ak − al = 20, điều này có nghĩa là từ ngày thứ l + 1 đến ngày thứ k học sinh này phải giải đúng 20 bài. J Ví dụ 1.8. Trong một khu tập thể sống 123 người. Tổng số tuổi của họ là 3813. Chứng minh rằng có thể chọn 100 người sống ở khu tập thể này, mà tổng số tuổi của họ không nhỏ hơn 3100. Lời giải. Chúng ta hãy chọn 100 người nhiều tuổi nhất và giả sử tổng số tuổi của họ nhỏ hơn 3100. Khi đó người trẻ nhất trong số người được chọn là 3100:100=31 tuổi. Mặt khác người này không trẻ hơn 23 người còn lại theo cách chọn. Khi đó tổng số tuổi của 23 người này không lớn hơn 23.31=713. Suy ra tổng số tuổi của tất cả mọi người sống trong tập thể nhỏ hơn 3100+713=3813 dẫn đến vô lý. J Ví dụ 1.9. Năm cặp vợ chồng tổ chức một buổi gặp mặt. Khi gặp nhau họ bắt tay nhau, nhưng không ai tự bắt tay người trong gia đình mình 1.2. Ví dụ 9 và người mà chồng mình (hoặc vợ mình) đã bắt tay rồi. Cũng không ai bắt tay cùng một người hai lần. Sau cuộc gặp chúc mừng ban đầu, một người đàn ông tên là Hùng hỏi tất cả những người có mặt, kể cả vợ mình, là họ đã bắt tay được bao nhiêu lần. Họ nhận thấy rằng chín người được hỏi đều trả lời các con số khác nhau. Như vậy vợ của Hùng đã bắt tay bao nhiêu lần? Lời giải. Mỗi một người khách bắt tay không quá 8 lần. Vì câu trả lời của 9 người là các số khác nhau nên các số đó phải là 0,1,2,3,4,5,6,7 và 8. Người bắt tay 8 lần phải là vợ (hoặc chồng) của người không bắt tay lần nào (nếu ngược lại thì người đó không bắt tay 8 lần mà nhiều nhất chỉ là 7 lần thôi). Tương tự như vậy người bắt tay 7 lần có người vợ (hoặc chồng) bắt tay một lần, người bắt tay 6 lần có người vợ (hoặc chồng) bắt tay 2 lần, người bắt tay 5 lần có người vợ (hoặc chồng) bắt tay 3 lần. Chỉ còn lại một người duy nhất bắt tay 4 lần, đó chính là người vợ của Hùng. J Ví dụ 1.10. Một câu chuyện cổ tích kể lại rằng: Một lần vua Hùng vương 18 có mời các quan trong triều họp ngồi quanh một cái bàn tròn. Theo lệnh của vua, một cận thần đã viết tên của mỗi quan trên bàn trước chiếc ghế mà ông ta phải ngồi. Các quan trong triều không được báo trước nên họ đã ngồi không theo sắp xếp đã định mà chiếm chỗ một cách bất kỳ. Chứng minh rằng ông cận thần có thể quay chiếc bàn sao cho ít nhất có hai ông quan ngồi đúng vị trí tên của mình ? Lời giải. Đặt số lượng các quan là n. Khi đó mặt bàn có n trạng thái, với các trạng thái này đối diện với các quan là biển đề tên nào đó. Ngoài ra với mỗi một ông quan chỉ có một trạng thái, mà khi ngồi đúng thì ông ấy đối diện với chính tên của mình trên biển đề sẵn. Nghĩa là, nếu mỗi trạng thái của bàn (vì bàn có thể xoay được) ta 10 Chương 1. Nguyên lý Đirichlê và ví dụ cho tương ứng với một số bằng số lượng các quan ngồi đúng vị trí tên mình, thì tổng của tất cả những số nhận được (mọi trạng thái bàn) sẽ không nhỏ hơn n. Nhưng một trạng thái đầu tiên của sắp xếp bàn cho tương ứng với 0 (không ai ngồi đúng chỗ ). Nếu giả sử trong n − 1 trạng thái mặt bàn còn lại tương ứng với số nhỏ hơn 2 (tức là chỉ có số 1 hoặc 0), thì tổng của n số nhận được sẽ nhỏ hơn n, điều đó không thể được. Suy ra từ n − 1 trạng thái mặt bàn còn lại có ít nhất một trạng thái mà hai người sẽ đối diện với chính tên của mình. J 1.3. BÀI TẬP . 1.11. Trong sân cung điện nhà vua hội họp 2n(n ≥ 2) ông quan, mỗi ông quan đã quen biết không ít hơn n ông có mặt tại đó. Chứng minh rằng người xếp bàn tròn có thể xếp được mỗi bàn 4 người sao cho mỗi người đứng giữa hai người quen của mình. . 1.12. Một khu rừng thông có dạng hình vuông mỗi chiều 1km. Trong rừng có 4500 cây thông, cây to nhất có đường kính 0,5m. Chứng minh rằng trong khu rừng có ít nhất 60 mảnh đất, diện tích mỗi mảnh 200m2, không có một cây thông nào. . 1.13. Trong một giá sách có 25 ngăn. Ta thấy có một ngăn chứa 10 cuốn, còn các ngăn khác chứa số sách ít hơn. Chứng minh rằng có ít nhất ba ngăn sách chứa cùng số sách như nhau (kể cả những ngăn không có sách). . 1.14. Tại một thành phố biển xe ôtô được đánh số bằng tổ hợp chữ cái rồi đến dãy số. Chứng minh rằng trên một đoạn đường cứ có 11 chiếc ôtô đi qua thì bao giờ cũng có hai chiếc ôtô có cùng chữ số tận cùng. 1.3. Bài tập 11 . 1.15. Một chiếc hồ lớn được bọc bởi 4 trạm chuyển tiếp sóng thông tin. Giữa hai trạm người ta xây dựng các trung tâm phát sóng và nhận sóng, đường sóng bao phủ lớn nhất là đường tròn có tâm ở trung tâm và đi qua hai trạm. Chứng minh rằng với bốn trung tâm ở các đoạn giữa của từng cặp trạm thì toàn bộ mặt hồ sẽ được phủ sóng thông tin. CHƯƠNG 2 SỐ HỌC 2.1. Phép chia số tự nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Vídụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1. PHÉP CHIA SỐ TỰ NHIÊN Trong các phép tính trên số nguyên: cộng, trừ, nhân, chia, thì phép chia là rất đặc biệt. Phép chia có hàng loạt tính chất mà tất cả các phép tính còn lại không có. Ví dụ các phép toán đều thực hiện với số 0 được, nhưng riêng phép chia cho số 0 thì không được. Phép chia không chỉ đặc biệt với phép chia cho 0. Với các phép tính cộng, trừ, nhân trên số nguyên cho ta số nguyên, nhưng với phép chia thì tính chất đó không còn đúng vì không phải lúc nào ta cũng nhận được số nguyên sau phép chia. Nhờ những dị biệt của phép chia mà trong toán học xây dựng hẳn một lý thuyết về phép chia những số nguyên. Những ví dụ và bài tập chương này có liên quan mật thiết giữa phép chia và nguyên lý Đirichlê, nên chúng ta nhắc lại định nghĩa phép chia: Cho a và b là những số nguyên, với b > 0. Chúng ta nói rằng a chia hết cho b, ký hiệu là b|a, khi tồn tại một số nguyên q sao cho đẳng thức sau đúng a = bq. 2.2. Vídụ 13 Chúng ta thường gọi số a là bội của b, hoặc b là ước của a. Số q gọi là thương số của phép chia a cho b. Trong phát biểu định nghĩa trên, nếu không tồn tại một số q nào cả, thì chúng ta nói rằng a không chia hết cho b và ký hiệu là b 6 |a. Từ định nghĩa chúng ta dễ dàng chứng minh được các tính chất sau 1) Với mọi số nguyên a > 0 chúng ta có a|a, Phép chia hết có tính phản xạ. 2) Nếu b|a và a|c thì b|c- phép chia hết có tí nh bắc cầu. 3) Nếu b|a và b|c, thì b|(ac). 4) Nếu a, b, m, n là những số nguyên và nếu c|a và c|b, thì c|(ma + nb). Định lý sau đây giữ vai trò quan trọng cho phép chia một số nguyên cho một số nguyên. Với hai số nguyên bất kỳ a và b sao cho b > 0, tồn tại duy nhất những số nguyên q và r thỏa mãn a = bq + r và 0 ≤ r < b. Còn rất nhiều tính chất khác của số nguyên cũng như số thực nhưng chúng ta không đi theo hướng này, mà chỉ dùng các tính chất của số học và Nguyên lý Đirichlê để giải các bài toán. 2.2. VÍDỤ Ví dụ 2.1. Cho k là một số tự nhiên, A là tập hợp gồm k + 1 số tự nhiên. Chứng minh rằng có ít nhất một hiệu hai phần tử trong A chia hết cho k. Lời giải. Gọi a1, a2, . . . , ak+1là các phần tử của A, còn b1, b2 , . . . , bk+1 là những số dư của phép chia các số trên cho k. Khi đó a1 = 14 Chương 2. Số học kc1 + b1, a2 = kc2 + b2, . . . , ak+1 = kck+1 + bk+1,với các số nguyên c1, c2, . . . , ck+1 sao cho 0 ≤ b1 ≤ k − 1, 0 ≤ b2 ≤ k − 1, . . . , 0 ≤ bk+1 ≤ k − 1. Một phần tử bất kỳ as thuộc A cho tương ứng với số dư bs của nó.Gọi tập hợp các số dư là B. Như vậy, mỗi phần tử của A được đặt tương ứng với một phần tử của tập hợp B, gồm tất cả các số nguyên từ 0 đến k − 1. Nhưng số lượng phần tử của A theo giả thiết là k + 1, còn B có số lượng k. Theo nguyên lý Đirichlê suy ra tồn tại hai phần tử khác nhau của A có cùng số dư. Điều đó nghĩa là, tồn tại hai chỉ số khác nhau s và t với as = kcs + bs và at = kct + bs sau khi trừ đi cho nhau ta được at − as = k(ct − cs). J Ví dụ 2.2. Cho A một tập hợp bất kỳ gồm 101 số tự nhiên, mỗi số không lớn hơn 200. Chứng minh rằng trong A có ít nhất hai số mà một số này chia hết cho số kia. Lời giải. Mỗi số a của A có thể biểu diễn dưới dạng a = 2kb với k là số nguyên không âm, còn b là một số lẻ. Với mỗi số a thuộc A cho tương ứng với số b trong sự biểu diễn ở trên. Bằng cách này, mỗi phần tử a của A được đặt tương ứng với một phần tử của tập hợp B gồm các số lẻ giữa 1 và 200. Nhưng tập hợp B chỉ có 100 phần tử vì vậy số phần tử của A lớn hơn số phần tử của B. Ta có thể áp dụng nguyên lý Đirichlê, suy ra tồn tại hai phần tử khác nhau a1 và a2 thuộc A mà chúng tương ứng với cùng một số của tập hợp B. Nghĩa là, a1 = 2k1 b, a2 = 2k2 b và nếu k1 < k2, thì số a2 chia hết cho a1. J Ví dụ 2.3. Cho M là tập hợp bất kỳ gồm 75 số tự nhiện mà mỗi số không lớn hơn 100. Chứng minh rằng với mỗi số tự nhiên l nhỏ hơn hoặc bằng 49 tồn tại hai phần tử của M có hiệu là l. Lời giải. Gọi các phần tử của M là x1, x2, . . . , x75. Ký hiệu A là tập hợp các số tự nhiên từ 1 đến 150. Với mỗi số 1, 2, 3 . . . , 75 cho tương 2.2. Vídụ 15 ứng với các số x1, x2, . . . , x75, còn các số 76, 77, 78, . . . 150 lần lượt ứng với x1 + l, x2 + l, . . . , x75 + l. Vì xm ≤ 100(m = 1, 2, . . . , 75) và l ≤ 49 thì xm + l < 150. Suy ra mỗi phần tử của A tương ứng với một phần tử của B gồm những số tự nhiên từ 1 đến 149. Vì số phần tử của A lớn hơn số phần tử của B, theo nguyên lý Đirichlê tồn tại hai phần tử khác nhau của A, mà chúng tương ứng với cùng một phần tử của B. Nhưng với các giá trị khác nhau của m từ 1 đến 75 được cho tương ứng với các giá trị khác nhau của x1 đến x75 trong B. Tương tự các giá trị của m ở khoảng 76 đến 150 tương ứng với các giá trị khác nhau trong khoảng còn lại. Từ đó suy ra tồn tại xm và xn mà xm = xn + l, nghĩa là xm − xn = l. J Ví dụ 2.4. 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 là đú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 cho x = 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 đó có 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) = 16 Chương 2. Số học (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, 2, . . . ,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ý Đirichlê chúng ta nhận được s ≤ n − 1, vì ngoài A có đú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. J Ví dụ 2.5. Chứng minh rằng từ n + 1 số dương khác nhau nhỏ hơn 2n, có thể chọn được ba số sao cho tổng hai số trong chúng bằng số thứ ba. Lời giải. Ký hiệu 0 < a1 < a2 < . . . < an+1 là những số đã cho. Chúng ta xét các hiệu số a2 − a1, a3 − a1, . . . , an+1 − a1 và các số a2, a3 . . . , an+1. Vì tất cả các số này đều nhỏ hơn 2n nên các số trên chỉ nằm trong khoảng 1, 2, . . . , 2n − 1. Như vậy chúng ta sẽ tìm được một số ở nhóm thứ nhất bằng một số ở nhóm thứ hai: ak − a1 = al, suy ra ak = a1 + al. J Ví dụ 2.6. Chứng minh rằng với một số bất kỳ n tồn tại một số có dạng 111 . . . 000 | {z } n chữ số mà chia hết cho n. Lời giải. Chúng ta xét những số 1, 11, 111, . . . , 111 . . . 111 | {z } n chữ 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 những số dư dương khác nhau khi chia chúng cho n có số lượng n − 1. 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 đó 2.2. Vídụ 17 sẽ có hai số trong chúng, ví dụ 111 . . . 111 | {z } k chữ số và 111 . . . 111 | {z } l chữ số , l > k, mà khi chia chúng cho n sẽ cho cùng một số dư. Do đó l − k = 111 . . . 000 | {z } (l-k chữ số 1, k chữ số 0) sẽ chia hết cho n. J Ví dụ 2.7. 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 . . . 111 mà chia hết cho p. Lời giải. Ta xét dãy số 1, 11, 111, . . . , 111 . . . 1 | {z } (p chữ số ) . 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, . . . , 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ý Đirichlê tồn tại hai số có cùng số dư. Giả sử các số đó là 111 . . . 1 | {z } (m chữ số ) đó 1 ≤ n < m ≤ p. Vậy và 111 . . . 1 | {z } ( n chữ số ) với m > n. Khi 111 . . . 1 | {z } (m chữ số ) − 111 . . . 1 | {z } (n chữ số ) = 111 . . . 000 | {z } (m-n chữ số 1, n chữ số 0) = 111 . . . 1 | {z } (m-n chữ số ) .10n Tích này chia hết cho p vì (p, 10) = 1, suy ra 111 . . . 1 | {z } (m-n chữ số 1) chia 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. J Ví dụ 2.8. (Đề thi Olympic toán thế giới lần thứ 14) Cho M là tập 18 Chương 2. Số học 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 hai tập thỏa mãn kết luận của bài toán, thì ta có thể chọn được hai tập con có 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ông 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 tập hợp 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ý Đirichlê ở đây. Suy ra tồn tại ít nhất hai tập hợp con khác nhau có cùng một tổng các phần tử. J Ví dụ 2.9. (Đề thi học sinh giỏi toán Cấp II toàn quốc 1983) Chứng minh rằng trong các số tự nhiên thế nào cũng có số k sao cho 1983k − 1 chia hết cho 105. Lời giải. Cho k lấy giá trị từ 1 đến 105 + 1 rồi thay vào biểu thức 1983k − 1 sẽ nhận được 105 + 1 giá trị khác nhau. Chia 105 + 1 số vừa nhận ở trên cho 105, sẽ được nhiều nhất là 105số dư. Do đó theo nguyên lý Đirichlê phải có ít nhất hai số cho cùng một số dư. Giả sử đó là số 1983m − 1 và 1983n − 1(m > n). Thế thì (1983m − 2.3. Bài tập 19 1) − (1983n − 1) chia hết cho 105 mà (1983m − 1) − (1983n − 1) = (1983m − 1983n) = 1983n(1983m−n − 1). Nhưng 1983 và 105 nguyên tố cùng nhau, do vậy phải có (1983m−n − 1) chia hết cho 105. Số k = m − n thỏa mãn điều kiện đầu bài. J Ví dụ 2.10. 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 0 và giá trị tuyệt đối của mỗi số không quá 1000000, thỏa mãn |a + b√2 + c√3| < 10−11. Lời giải. Đặt S là tập hợp của 1018 số thực r + s√2 + t√3 với mọi r,s, t thuộc {0, 1, 2, . . . , 106 − 1} và đặt d = (1 +√2 +√3d)106. Khi đó mỗi x trong S đều nằm trong khoảng 0 ≤ x < d. Chia đoạn này thành 1018 − 1 phần bằng nhau, mỗi đoạn nhỏ có độ dài e =d 1018 − 1. Theo nguyên lý Đirichlê tồn tại hai số trong 1018 số của S nằm trong cùng một đoạn nhỏ. Hiệu của hai số này ký hiệu là a + b√2 + c√3 đó chính là các số a, b, c vì e <107 1018 = 10−11. J 2.3. BÀI TẬP . 2.11. Cho A là tập hợp bất kỳ gồm 201 số tự nhiên, mỗi số không vượt quá 300. Chứng minh rằng A chứa ít nhất hai số, mà tỷ số của chúng là lũy thừa bậc ba. . 2.12. Cho k là số tự nhiên bất kỳ, còn a và b là những số nguyên sao cho a ≤ b và b − a < 2k − 2. Chứng minh rằng nếu M là tập hợp k số tự nhiên nằm trong khoảng [a, b], và l là số tự nhiên thỏa mãn 1 ≤ l ≤ 2k + a − b − 2, thì có ít nhất một hiệu những phần tử của M trùng với l. . 2.13. Cho dẫy số a1, a2, a3, . . . , a41, mà mỗi phần tử chỉ được tạo bởi số 1 và, số 2, trong đó có ít nhất 21 số chỉ được tạo bởi các số 1. 20 Chương 2. Số học Chứng minh rằng tồn tại một số phần tử liên tiếp của dãy có tổng bằng đúng 20. . 2.14. Chứng minh rằng tồn tại một số tự nhiên n, sao cho số 111 . . . 1 | {z } (n chữ số ) chia hết cho 139. (Bài toán còn đúng nếu ta thay 139 bằng một số nguyên tố cùng nhau với 10). . 2.15. Chứng minh rằng trong mọi số tạo bởi 100 chữ số N tồn tại một số chia hết cho 1967. . 2.16. Chứng minh rằng bao giờ cũng tìm được số 19971997. . . 19970. . . 0 chia hết cho 1998. . 2.17. Chứng minh rằng có một số tự nhiên chia hết cho 1997, mà bốn chữ số cuối cùng của nó là 1998. . 2.18. Chứng minh rằng nếu các số nguyên m và n nguyên tố cùng nhau thì tìm được số tự nhiên k sao cho mk − 1 chia hết cho n. CHƯƠNG 3 DÃY SỐ 3.1. Nguyên lý Đirichlê cho dãy số vô hạn . . . . . . . . . . . . . . . 21 3.2. Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1. NGUYÊN LÝ ĐIRICHLÊ CHO DÃY SỐ VÔ HẠN Trong phần này chúng ta xét nguyên lý Đirichlê dưới dạng: 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ì ít nhất có một ngăn kéo chứa vô hạn những vật đã có. Chúng ta dễ có cảm tưởng rằng nguyên lý này là hiển nhiên nên ít chú ý đến nó. Bằng phản chứng có thể chứng minh nguyên lý này là đúng. Trong số học, tập hợp có liên quan đến vô hạn phần tử là dẫy số. Chúng ta biết rất nhiều dãy số đẹp như dãy cấp số cộng, dãy cấp số nhân, dãy các số nguyên tố, hoặc dãy Fibonaxi,. . . Chương này chúng ta chỉ quan tâm đến áp dụng điều phát biểu trên để giải các bài toán liên quan đến dẫy số. Những tập vô hạn trong các bài toán dưới đây ta xét như các dãy số. 22 Chương 3. Dãy số 3.2. Ví dụ Ví dụ 3.1. Xét dãy số 6, 62, 63, 64, 65, . . . , 6n, . . . và viết 4 chữ số cuối cùng của các số này 0006, 0036, 0216, 1296, 7776, . . .. Chứng minh rằng bắt đầu từ một số n0 nào đó dẫy vừa lập là dẫy tuần hoàn. Lời giải. Vì tồn tại hữu hạn số lượng (104) cách chọn khác nhau các số có 4 chữ số, nên trong dãy đã cho chắc chắn tìm được hai cách chọn có cùng 4 chữ số cuối. Có nghĩa là tìm được hai số n0 và n0 + t mà với chúng thì 6n0 và 6n0+t+1có cùng 4 chữ số cuối (6n0+t+1 − 6n0 = 104.6k). Nói chung, chữ số 6n và 6n+t với bất kỳ n > n0 sẽ có cùng 4 chữ số cuối (6n+t − 6n = 104.6n−n0 ). J Ví dụ 3.2. (Đề thi Toán Olympic quốc tế lần 17 năm 1975) Cho a1, a2, . . . , an, . . . là dãy tăng ngặt các số tự nhiên. Chứng minh rằng vô hạn các phần tử an của dẫy trên có thể biểu diễn dưới dạng an = xap + yaq,ở đây x và y là những số nguyên dương và p 6= q. Lời giải. Nếu a1 = 1 kết luận của bài toán là hiển nhiên. Thật vậy, với mọi n ≥ 3 số hạng an có biểu diễn dạng an = an−1 + (an + an−1) = 1.an−1 + (an − an−1).a1 có tính chất mong muốn. Chúng ta sẽ chứng minh tồn tại chỉ số p lớn hơn 1 sao cho vô hạn các số hạng của dãy đã cho có thể viết dưới dạng xap + ya1 với các số nguyên dương thích hợp x và y. Mỗi số hạng của dãy ta đặt tương ứng với số dư của nó khi chia chính nó cho a1. Tập hợp tất cả các số hạng của dãy là vô hạn, còn tất cả các khả năng của số dư khi chia các số hạng cho a1 là hữu hạn. Điều đó chứng tỏ rằng vô hạn phần tử an1, an2, . . . , ank, . . . , với n1 < n2 < . . . < nk < . . . cho cùng một số dư r khi chia cho a1. Không mất tính tổng quát ta giả thiết n1 > 1, vì trong trường hợp ngược lại ta xét các số 3.2. Ví dụ 23 an2, an3, . . . , ank, . . . cũng là dãy vô hạn và cho cùng số dư r khi chia cho a1. Với mọi k = 1, 2, . . . tồn tại số nguyên dương xk sao cho ank = xk a1 + r. Khi đó ank − an1 = (xk a1 + r) − (x1a1 + r) = (xk − x1)a1 suy ra với mọi k ≥ 2 ta có đẳng thức ank = an1 + (xk − x1)a1 = 1.an1 + (xk − x1)a1. Nghĩa là, những số an2, an3, . . . , ank, . . . ., có biểu diễn và các tính chất như bài toán đòi hỏi. Thật vậy, chỉ số 1 và n1 khác nhau vì theo cách chọn trên n1 thực sự lớn hơn 1. Chỉ còn phải khẳng định rằng số xk − x1 là số nguyên dương với k ≥ 2, điều đó đúng vì từ n1 < nk suy ra x1 < xk. J Ví dụ 3.3. Cho số tự nhiên bất kỳ k. Chứng minh rằng tồn tại số nguyên tố p và một dãy số tự nhiên tăng ngặt a1, a2, . . . , an, . . . sao cho tất cả các phần tử của dãy p + ka1, p + ka2, . . . , p + kan, . . . là những số nguyên tố. Lời giải. Ký hiệu P là tập hợp tất cả các số nguyên tố. Với mọi i = 0, 1, . . . , k − 1 ký hiệu Pilà tập hợp các số nguyên tố mà khi chia cho k có số dư i. Dễ thấy rằng mọi số nguyên tố nằm trong một trong các tập hợp P0, P1, P2, . . . , Pk−1. Bởi vì số nguyên tố là vô hạn, vậy ít nhất phải có một trong số các tập hợp P0, P1, P2, . . . , Pk−1 chứa vô hạn số nguyên tố. Giả sử Pi chứa vô hạn số và ký hiệu p là phần tử nhỏ nhất của nó. Khi đó mọi số x thuộc Pi có dạng x = p + ka với một số tự nhiên a. Lấy x1, x2, x3, . . . là các phần tử của Pi xếp theo thứ tự lớn dần. Với mọi số tự nhiên n đặt an =xn − p k. Dễ thấy rằng số nguyên tố p và dãy a1, a2, . . . , an, . . . có tính chất mong muốn. J Ví dụ 3.4. Cho f là đa thức k đối số với hệ số nguyên và a1, a2, . . . , an, . . . là dãy những số nguyên thỏa mãn hệ thức an+1 = f(a,a2, . . . , an−k+1), với mọi số nguyên n, k mà n ≥ k. Chúng ta xét số dương bất kỳ m và với mọi n = 1, 2, . . .. Ký hiệu an là số dư 24 Chương 3. Dãy số không âm nhỏ nhất của an theo mô đun m. Chứng minh rằng dãy a1, a2, a3, . . . , an, . . . . là dãy tuần hoàn. Lời giải. Chúng ta sẽ sử dụng khẳng định sau: Nếu g là đa thức k đối số với hệ số nguyên và x1, x2, . . . , xk, y1, y2, . . . , yklà các số nguyên sao cho x1 ≡ y1 (mod m), x2 ≡ y2 (mod m), . . . , xk ≡ yk (mod m), thì g(x1, x2, . . . , xk) ≡ g(y1, y2, . . . , yk) (mod m). Mọi số hạng của dãy bằng một trong các số a1, a1, a3, . . . , an, . . . 0, 1, . . . , m − 1. Chúng ta xét các bộ sắp thứ tự gồm k phần tử (a1, a2, . . . , ak),(a2, a3, . . . , ak+1), . . . ,(an, an+1 . . . , an+k−1).. Có tất cả vô hạn bộ sắp như vậy, nhưng số lượng các bộ k số (α1, α2, α3, . . . , αk), với 0 ≤ αi ≤ m − 1, i = 1, 2 . . . , k là hữu hạn (bằng mktheo lý thuyết tổ hợp). Theo nguyên lý Đirichlê tồn tại hai chỉ số i và j, i < j sao cho ai = aj, ai+1 = aj+1, . . . , ai+k−1 = aj+k−1 hoặc là x1 ≡ y1 (mod m), x2 ≡ y2 (mod m) , . . . , xk ≡ yk (mod m). Từ đây suy ra dãy a1, a2, a3, . . . , an . . . là tuần hoàn (chu kỳ của nó là ước số của j − i). Thật vậy, vì f là đa thức với hệ số nguyên nên theo cách chứng minh trên chúng ta có f(ai+k−1, ai+k−2, . . . , ai) ≡ f(aj+k−1, aj+k−2, . . . , aj) (mod m) =⇒ ai+k ≡ aj+k (mod m) hoặc là ai+k ≡ aj+k. Biến đổi một chút dễ thấy rằng với mọi n ≥ i ta có đẳng thức sau an+(i−j) ≡ an. J Ví dụ 3.5. Cho dãy x1, x2, . . . , xn, . . . . được xác định theo công thức sau x1 = 1, x2 = 0, x3 = 2, xn+1 = 2xn−1 + xn−2, n ≥ 3. Chứng minh rằng với mọi số tự nhiên m tồn tại hai phần tử liên tiếp 3.2. Ví dụ 25 của dãy mà chúng đều chia hết cho m. Lời giải. Công thức hồi quy trên có thể viết lại xn−2 = xn+1 − 2xn−1 (3.1) Từ đó chỉ ra rằng dãy có khả năng phát triển về phía trái, tức là xác định xn với n ≤ 0. Ví dụ với n = 2, 1, 0 chúng ta nhận được x0 = 0, x−1 = 0, x−2 = 1. Như mục 3.4 chỉ ra rằng dãy x1, x2, . . . , xn, . . . gồm những số dư tương ứng x1, x2, . . . , xn, . . . theo môdd un m, là dãy tuần hoàn. Từ công thức (3.1) suy ra mỗi phần tử của dãy {xn} và suy ra cả {xn} xác định duy nhất từ 3 phần tử trước nó. Khi đó nếu (r1,r2, . . . ,rk) là phần chu kỳ của dãy x1, x2, . . . , xn, . . . thì phần này sẽ chuyển động tuần hoàn về phía trái của dãy . . . , x−3, x−2, x−1, x0, x1, x2, . . . và sẽ có dạng . . . ,r1,r2, . . . ,rk,r1,r2, . . . ,rk,r1,r2, . . . ,rk. . . (3.2) Bây giờ ta chú ý rằng x−1 = x0 = 0, suy ra x−1 = x0 = 0. Từ (3.2) suy ra rằng dãy các số dư theo môdd un m chứa vô số cặp phần tử liên tiếp bằng không. Nói cách khác tồn tại vô số các cặp số liên tiếp của dãy x1, x2, . . . , xn, . . . mà mỗi phần tử trong cặp đều chia hết cho m. J Ví dụ 3.6. Dãy số Fibonaxi được định nghĩa bằng các đẳng thức F1 = F2 = 1, Fn+2 = Fn+1 + Fn, n ≥ 1. Chứng minh rằng ít nhất một trong 1.000.000.000 phần tử đầu tiên của dãy chia hết cho 10.000. Lời giải. Tương tự như 3.5 chúng ta xét các số dư của các số trong dãy đã cho khi chia cho 10.000. Ký hiệu số dư đứng ở vị trí thứ k khi chia cho 10 000 là rk. Khi đó thì r1 = 1,r2 = 1,r3 = 2,r4 = 3, . . . . . . .rk = rk−1 + rk−2. Rõ ràng có 10.000 số 26 Chương 3. Dãy số dư khác nhau do đó có 100002 = 100000000 (trăm triệu) cặp số dư khác nhau. Xét 100000001 cặp số dư (r1,r2),(r2,r3),(r3,r4). . . . . .(r100000001,r100000002). Theo nguyên lý Đirichlê trong số này có ít nhất 2 cặp số trùng nhau, tức là tìm được hai số n và p với n, p đều nhỏ hơn 100000002,n nhỏ hơn p sao cho rn = rp,rn+1 = rp+1. Nhưng nếu biết số dư của tổng hai số và số dư của một số thì số dư kia cũng tính được. Vì vậy ta có rn−1 = rp−1,rn−2 = rp−2, . . . . cho đến khi r2 = 1 = rp−n+2,r1 = 1 = rp−n+1, Áp dụng công thức số dư hồi qui ở trên ta có rp−n = 0 với p − n ≤ 100000001 − 1 = 100000000. Nghĩa là số đứng ở vị trí p − n sẽ thỏa mãn điều kiện bài ra, chia hết cho 10 000. J Ví dụ 3.7. (Định lý Fecma) Nếu một số nguyên tố p không chia hết số nguyên a, thì đẳng thức sau đúng ap−1 ≡ 1( mod p). Lời giải. Chúng ta chứng minh mệnh đề tổng quát hơn. Cho m > 1 là số tự nhiên bất kỳ và a là số nguyên tố cùng nhau với m. Chúng ta xét dãy những lũy thừa liên tiếp của a a1, a2, a3, . . . (3.3) và ký hiệu r1,r2,r3, . . . (3.4) là những số dư tương ứng của (3.3) khi chia cho m, nghĩa là ak ≡ rk (mod m), 1 ≤ rk ≤ m − 1. Khi đó số lượng các số trong (3.3) là vô hạn, còn những số ở (3.4) chỉ có thể nhận những giá trị trong 1, 2, 3, . . . , m − 1 nên số lượng là hữu hạn. Suy ra theo nguyên lý Đirichlê, giữa những số dư rk sẽ có ít nhất hai số trùng nhau; nói cách khác tồn tại hai chỉ số i và j với i 6= j sao cho ri = rj. Khi đó chúng ta có ai ≡ aj( mod m). Theo giả thiết (a, m) = 1, với i 6= j chúng ta nhận được ai−j ≡ 1( mod m). 3.2. Ví dụ 27 Chúng ta có kết luận tồn tại số tự nhiên l sao cho đẳng thức sau đây đúng: al ≡ 1 (mod m) (3.5) - Số l trong (3.5) không xác định duy nhất, thậm chí còn tồn tại vô số số tự nhiên l thỏa mãn (3.5). - Trong trường hợp m = p là số nguyên tố, Fecma tìm ra l có thể chọn là số p − 1. -Trường hợp m bất kỳ thì Ơle chứng minh rằng l có thể chọn là hàm chỉ số của m (chúng ta không xem xét vấn đề này ở đây, độc giả có thể tìm trong bất cứ cuốn sách số học nào). J Ví dụ 3.8. 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, x3, . . . , xk. Chúng ta xét tổng S1 = x1, S2 = x1 + x2, S3 = x1 + x2 + x3, . . . , Sk = x1 + x2 + · · · + xk 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ý Đirichlê 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 đã cho chia hết cho k, vì xi+1 + xn+2 + · · · + xj = Sj − Si. J Ví dụ 3.9. 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 28 Chương 3. Dãy số 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ý Đirichlê tồn tại ít nhất hai số cho cùng một 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. J Ví dụ 3.10. Cho k là số nguyên dương bất kỳ và x1, x2, . . . , xn, . . . y1, y2, . . . , yn, . . . là những chuỗi số nguyên bất kỳ. Chứng minh rằng tồn tại vô số cặp chỉ số (i, j), với i < j sao cho mỗi tổng xi+1 + xn+2 + · · · + xj; yi+1 + yn+2 + · · · + yj đều chia hết cho k. Lời giải. Chỉ cần chứng minh rằng trong bộ số k2 phần tử liên tiếp của 2 dẫy trên có thể chọn được tổng với tính chất đã chỉ ra. Vì vậy chúng ta chỉ quan tâm đến k2 phần tử đầu tiên của các chuỗi đã cho. Bằng cách tổng quát hóa cách giải bài toán 3.8, lấy tổng S1 = x1, S2 = x1 + x2, S3 = x1 + x2 + x3, . . . , Sk2 = x1 + x2 + · · · + xk2 T1 = y1, T2 = y1 + y2, T3 = y1 + y2 + y3, . . . , Tk2 = y1 + y2 + · · · + yk2 Với mỗi m = 1, 2, 3, . . . , k2 đặt tương ứng cặp (Sm, Tm) với cặp (RSm, RTm) của những số dư, khi chia Sm và Tm cho k. Vì RSm 3.3. Bài tập 29 và RTm là một trong các số 0, 1, 2, . . . , k − 1, nên tổ hợp tất cả các dạng khác nhau (RSm, RTm) là không quá k2. Nếu tồn tại một chỉ số m, sao cho (RSm, RTm) trùng với (0, 0), thì mọi tổng Sm = x1 + x2 + · · · + xm và Tm = y1 + y2 + · · · + ym đều chia hết cho k. Vì nếu không như vậy, thì các cặp số (RSm, RTm), m = 1, 2, . . . .., k2 có nhiều nhất là k2 − 1 khả năng khác nhau. Nhưng số lượng những cặp số này là k2suy ra có ít nhất hai trong chúng bằng nhau. Nói cách khác, tồn tại hai chỉ số i và j, sao cho 1 ≤ i < j ≤ k2 và (RSi, RTi) = (RSj, RTj). Trong trường hợp này mỗi số xi+1 + xn+2 + · · · + xj = Sj − Si; yi+1 + yn+2 + · · · + yj = Tj − Ti đều chia hết cho k. J Chú ý: Đây là bài toán tổng quát hóa bài toán 3.8. Mở rộng kết quả này các bạn hãy xem và làm bài tâp 3.15. 3.3. BÀI TẬP . 3.11. Có tồn tại luỹ thừa của số 3 mà các chữ số cuối cùng của nó là 0001 không ? . 3.12. Cho F là tập hữu hạn những số nguyên dương và x1, x2, . . . , xn, . . . và y1, y2, . . . , yn, . . . là hai dẫy vô hạn những phần tử thuộc F. Chứng minh rằng tồn tại những chỉ số i và j, i < j sao cho tích của xi+1, xi+2, . . . , xj và yi+1, yi+2, . . . , yjlà một số có lũy thừa bậc k. . 3.13. Cho u1, u2, . . . , un, . . . là dãy những số nguyên xác định bằng công thức u1 = 39, u2 = 45, un+2 = u2n+1 − un(n ≥ 1). Chứng minh rằng 1986 chia hết cho vô số những phần tử trong dãy này. . 3.14. Cho k là một số tự nhiên. Dãy x1, x2, . . . , xn, . . . thỏa mãn các đẳng thức x0 = 0, x1 = 1 và xn =1k(xn+1 − xn−1) với mọi n ≥ 1. 30 Chương 3. Dãy số Chứng minh rằng giữa những số x1, x2, . . . , x1986 tồn tại hai số mà tích của chúng chia hết cho tich 19.86. . 3.15. Cho k là số nguyên dương và x11, x12, . . . , x1n, . . . x21, x22, . . . , x2n, . . . . . . . . . . . . . . . . . . xs1, xs2, . . . , xsn, . . . là s dãy số nguyên. Khi đó tồn tại vô hạn các cặp chỉ số (i, j), với i < j sao cho các tổng sau đây x1i+1 + x1i+2 + · · · + x1j x2i+1 + x2i+2 + · · · + x2j . . . . . . . . . . . . . . . . . . . . . xsi+1 + xsi+2 + · · · + xsj đều chia hết cho k. CHƯƠNG 4 HÌNH HỌC 4.1. Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1. VÍ DỤ Trong số các bài toán hình học trong toán học tổ hợp có một lớp bài toán giải bằng phương pháp Đirichlê rất thuận tiện và rõ ràng. Bạn đọc có thể tìm thấy những cách giải khác, nhưng vì mục đích chuyên đề phương pháp chúng ta đang xét nên chúng ta chỉ khảo sát các ví dụ sau. Ví dụ 4.1. Trong hình vuông với cạnh 1 đơn vị được chọn 101 điểm. Chứng minh rằng có năm điểm trong các điểm đã chọn có thể phủ bởi đường tròn bán kính 17. Lời giải. Chia hình vuông ra ra 25 hình vuông con có cạnh 0,2. Những hình vuông này có số lượng 25 và vì tất cả số điểm đã chọn là 101, thì ít nhất có một hình vuông nhỏ chứa ít nhất 5 điểm. Mà bán kính đường tròn ngoại tiếp hình vuông nhỏ bằng 1 5√5<17. J Ví dụ 4.2. Chứng minh rằng trong mọi khối đa diện lồi tồn tại ít nhất hai mặt có cùng số cạnh. 32 Chương 4. Hình học Lời giải. Ký hiệu F là mặt có số cạnh lớn nhất của khối đa diện. Nếu số cạnh của F là k, thì khối đa diện có ít nhất k + 1 mặt (vì có k mặt có cạnh chung với F), còn số lượng các cạnh của mỗi mặt là một trong các số 3, 4, . . . , k. Theo nguyên lý Đirichlê có ít nhất hai mặt có cùng số cạnh. J Ví dụ 4.3. Trong phần trong của một hình tròn với đường kính 5 đơn vị, người ta chọn bất kỳ 10 điểm. Chứng minh rằng ít nhất có hai điểm trong các điểm đã chọn có khoảng cách nhỏ hơn 2. Lời giải. Chia đường tròn thành 8 rẻ quạt bằng nhau với góc ở tâm mỗi rẻ quạt là 450 và dựng đường tròn đồng tâm C1 với bán kính 1. Ký C9 C8 F C2 A1 A C B C3 hiệu C2, C3, . . . , C9 là những hình từ tám rẻ quạt trừ đi phần mà đường tròn C1 đã chiếm. Có thể chứng minh được bất cứ hai điểm nào C7 C6 O C1 C5 E D B1 C4 thuộc một trong chín hình trên đều có khoảng cách nhỏ Hình 4.1 hơn 2. Thật vậy, nếu hai điểm rơi vào đường tròn đồng tâm thì khoảng cách giữa chúng nhỏ hơn 2. Giả sử hai điểm A và B rơi vào một CDEF trong số tám rẻ quạt. Trên bán kính OC và OD lấy tương ứng hai điểm A1 và B1 sao cho OA1 = OA;OB1 = OB, nghĩa là AB ≤ A1B1 (theo định lý hàm cosin, bởi vì AOB [ ≤ A\1OB1). Để ý rằng A1B1 ≤ max{A1D, A1E}. Thật vậy điểm B1 nằm trong đoạn thẳng tạo bởi hình chiếu H của A1 trên OD và ít nhất một trong hai điểm D, E, chẳng hạn điểm D. Bởi vậy hình chiếu HD 4.1. Ví dụ 33 của đường xiên A1D không bé hơn hình chiếu HB1 của A1B1 trên OD. Nghĩa là A1B1 ≤ A1D. Cũng chứng minh như trên ta có DA1 ≤ max{DF, DC}, EA1 ≤ max{EF, EC}. Từ sự đánh giá EF2 < CD2 = OC2 + OD2 − 2.OC.OD. cos 450 = 2254−25√2 4< 3, 75 < 4 và EC2 = FD2 = OF2 + OD2 − 2OF.OD. cos 450 = 1 +254−5√2 2< 7, 25 −5.1, 4 2= 3, 75 < 4, ta được AB ≤ A1B1 ≤ max{DF, DC, EF, EC} < 2. J Ví dụ 4.4. Giả sử mỗi điểm trong một mặt phẳng được sơn bằng một trong hai mầu đỏ và xanh. Chứng minh rằng có một hình chữ nhật nào đó trong mặt phẳng mà bốn đỉnh của nó cùng mầu. Lời giải. Dễ thấy theo nguyên lý Đirichlê, một tập bất kỳ 7 điểm mà sơn một trong hai mầu thì ít nhất có 4 điểm cùng mầu. Trên một đường thẳng có 7 điểm thì chúng ta phải có 4 điểm thẳng hàng cùng mầu, giả sử đó là P1, P2, P3, P4 có cùng mầu đỏ. Ta P1 P2 P3 P4 Q1 Q2 Q3 Q4 R1 R2 R3 R4 Hình 4.2 chiếu những điểm này xuống hai đường thẳng song song với đường chứa chúng tạo ra (Q1, Q2, Q3, Q4) và (R1, R2, R3, R4) tương ứng với (P1, P2, P3, P4). Những điểm này tạo ra một số hình chữ nhật, chúng ta chú ý đến các hình chữ nhật có đỉnh là Pi, i = 1, 2, 3, 4. Như vậy nếu 2 điểm bất kỳ của Q là đỏ thì ta có kết quả một hình vuông 34 Chương 4. Hình học PiPjQjQi có đỉnh cùng mầu. Tương tự cho các điểm R. Nếu đồng thời không có điểm Q và R thỏa mãn trường hợp trên thì có 3 (hoặc hơn) điểm Q nào đó và 3 điểm R nào đó có cùng mầu xanh. Nhưng trong bộ ba như vậy phải có cặp đôi tạo ra hình chữ nhật với các đỉnh mầu xanh trong số các điểm Q và R. J Ví dụ 4.5. Giả sử một bàn cờ hình chữ nhật có 4x7 ô vuông được sơn đen hoặc trắng. Chứng minh rằng với cách sơn mầu bất kỳ, trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô vuông, mà bốn ô ở góc là các ô cùng mầu. Lời giải. Chúng ta chứng minh cho bài toán bàn cờ 3 × 7. Mẫu sơn mầu có thể xẩy ra với bàn cờ này có dạng từ 1 đến 8. Giả sử một trong số các cột thuộc dạng 1. Bài toán sẽ được chứng minh nếu tất cả những cột còn lại trong 6 cột thuộc các dạng 1, 2, 3, 4. Như vậy giả sử tất cả các cột còn lại thuộc dạng Hình 4.3 5, 6, 7, hoặc 8. Khi đó theo nguyên lý Đirichlê hai trong số sáu cột có hai cột cùng một dạng và như vậy bài toán cũng được chứng minh. Chứng minh hoàn toàn tương tự nếu một cột có dạng 8. Giả sử không có cột nào trong 7 cột có dạng 1 hoặc 8. Như vậy ta có 7 cột với 6 dạng. Theo nguyên lý Đirichlê có hai cột cùng dạng và bài toán được chứng minh đầy đủ. J 4.1. Ví dụ 35 Ví dụ 4.6. Năm điểm A, B, C, D, E nằm trong một mặt phẳng và tọa độ của chúng là các số nguyên. Chứng minh rằng trong số những tam giác mà đỉnh của nó là ba điểm nào đó trong các điểm này, có ít nhất ba tam giác với diện tích là các số nguyên. Lời giải. Ta có thể chứng minh rằng nếu một trong các tọa độ của các đỉnh tam giác đã cho thay đổi một số chẵn, thì diện tích của tam giác cũng thay đổi một số nguyên. Một cách tổng quát hơn ta có thể khẳng định nếu các tọa độ đỉnh của một tam giác thay đổi một số chẵn, thì diện tích của nó cũng thay đổi một số nguyên. Vì vậy, nếu diện tích của tam giác mới nhận được là số nguyên, thì diện tích tam giác ban đầu cũng là số nguyên (hãy vẽ hình và chứng minh). Vì những tọa độ của các điểm đã cho A, B, C, D, E là những số nguyên, sau khi thêm vào các tọa độ này những số chẵn thích hợp, thì mỗi tọa độ sẽ chỉ nhận các giá trị 0 và 1. Do đó mọi 5 điểm đã cho tạo nên bởi các điểm (0, 0),(0, 1),(1, 0),(1, 1). Áp dụng nguyên lý Đirichlê suy ra ít nhất hai điểm trong các điểm A, B, C, D, E biến đổi thành cùng một điểm trong {(0, 0),(0, 1),(1, 0),(1, 1)}. Giả sử đó là A, B. Chúng ta sẽ khẳng định diện tích các tam giác ABC, ABD và ABE là những số nguyên. Thật vậy, các tam giác này bị biến thành đoạn thẳng (do A và B biến thành cùng một điểm) nên diện tích ảnh của chúng bằng 0. Vậy trước khi biến đổi, diện tích của chúng phải là số nguyên. J Ví dụ 4.7. Trong một mặt phẳng cho một tập hợp A có 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 A 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. 36 Chương 4. Hình học Lời giải. Với mọi điểm bất kỳ a thuộc A chúng ta ký hiệu S(a) là số lượng những điểm của A mà a nối thành đoạn thẳng. Bài toán muốn khẳng định rằng tồn tại hai điểm khác nhau a1 và a2 của A mà S(a1) = S(a2). Chúng ta thấy ngay rằng 0 ≤ S(a) ≤ n − 1 với mọi phần tử a thuộc A. Mặt khác, cũng không tồn tại những điểm x1 và x2 thuộc A, mà S(x1) = n − 1 và S(x2) = 0. Bởi vì điều này có nghĩa là điểm x1 nối với tất cả các điểm còn lại của A, còn x2 không nối với điểm nào của A, đẫn đến vô lý. Các số nguyên từ 0 đến n − 1 có số lượng là n. Vì 0 và n − 1 không đồng thời là giá trị vủa S nên S nhận nhiều nhất là n − 1 giá trị. Bài toán được giải suy ra từ nguyên lý Đirichlê. J Ví dụ 4.8. Cho đa giác đều 100 cạnh nội tiếp trong đường tròn k. Mỗi đỉnh được gán một trong các số 1, 2, . . . , 49. Chứng minh rằng trên k tồn tại hai cung AB và CD với các tính chất sau: a) Các điểm A, B, C và D là đỉnh của đa giác đều đã cho. b) Các dây cung AB và CD song song với nhau c) Nếu A, B, C và D có nhãn tương ứng là các số a, b, c, d thì a + b = c + d. Lời giải. Trong đường tròn k có đúng 50 đường kính khác nhau mà điểm cuối của đường kính là một đỉnh của đa giác đều 100 cạnh đã cho. Nếu PQ là một trong số đường kính đó và đir nh P được gán nhãn p, còn Q với nhãn q thì đường kính PQ tương ứng với số nguyên |p − q|. Rõ ràng, 0 ≤ |p − q| ≤ 48. Bằng cách này mỗi đường kính đã xét (tổng số có 50 tất cả) được cho tương ứng với một trong các số 0, 1, 2, . . . , 48. Suy ra có ít nhất hai đường kính được đặt tương ứng với cùng một số. 4.1. Ví dụ 37 Ta ký hiệu đó là AB và CD, còn các đỉnh được gán tương ứng các nhãn a, b, c, d. Không mất tính tổng quát chúng ta có thể giả thiết c ≤ a và b ≤ d. Khi đó dây cung AC và BD có các tính chất mong muốn. Thật vậy, với đường kính AC chúng ta đã đặt tương ứng với a − c, còn BD ứng với d − b và những số này bằng nhau, chúng ta nhận được a − c = d − b hay là a + b = c + d. Ngoài ra, tứ giác ABCD là hình vuông, nên AB song song với CD (thậm chí AB = CD). J Ví dụ 4.9. Tất cả các điểm trong một mặt phẳng được bôi bởi n mầu khác nhau. Cho trước 2n − 1 đường tròn đồng tâm khác nhau k1, k2, . . . , k2n−1. Trong các đường tròn dựng bán kính tương ứng OA1,OA2, . . . ,OA2n−1 sao cho mỗi cặp bán kính không có điểm chung nào khác ngoài O. Chứng minh rằng tồn tại một đường tròn ki, i = 1, 2, . . . , 2n − 1 sao cho trên nó và trên bán kính OAi của nó có những điểm tương ứng Xi và Yi, mà chúng được bôi cùng một mầu và Yi không trùng với O và Ai. Lời giải. Ký hiệu các mầu đã cho là c1, c2, . . . , cn. Chúng ta sẽ tính số lượng các tổ hợp khác nhau của các mầu mà với chúng có thể bôi mầu các điểm trên một hình phẳng. Mọi tập con khác trống {i1, i2, . . . , ik}, 1 ≤ k ≤ n của tập hợp N = {1, 2, . . . , n} tương ứng với tổ hợp mầu {ci1, ci2, . . . , cik}. Rõ ràng những tập con khác trống khác nhau của N bằng cách này tương ứng với những tổ hợp mầu khác nhau. Ngoài ra, mọi tổ hợp mầu {ci1, ci2, . . . , cik} có thể nhận được nhờ xây dựng tập con khác trống {i1, i2, . . . , ik}. Suy ra, tổ hợp những mầu c1, c2, . . . , cn mà với chúng có thể bôi các điểm một hình phẳng là tương ứng một - một với những tập hợp con khác trống của N = {1, 2, . . . , n}. Nghĩa là số các tổ hợp khác nhau của mầu 38 Chương 4. Hình học bằng số các tập hợp con khác trống của N, có tất cả 2n − 1 tập hợp như vậy. Trước tiên chúng ta giả thiết rằng tồn tại đường tròn ki, i = 1, 2, . . . , 2n − 1 mà muốn bôi kín nó phải dùng tất cả các mầu c1, c2, . . . , cn. Khi đó chúng ta chọn điểm bất kỳ Yilà điểm trong của bán kính OAi. Giả sử Yi được bôi bằng mầu c1. Nhưng trên ki có ít nhất một điểm Xi, được bôi cùng mầu như vậy, vì mọi mầu đã cho đều bắt gặp trên ki; vậy bài toán D C B A Hình 4.4 được giải trong trường hợp giả thiết này. Ta xét trường hợp còn lại: Giả sử không có đường tròn nào mà những điểm của nó được bôi mầu với toàn bộ tổ hợp c1, c2, . . . , cn. Khi đó có tất cả 2n − 2 khả năng tổ hợp mầu, với nó các điểm được bôi cho các đường tròn k1, k2, . . . , k2n−1 . Bởi vì 2n − 1 > 2n − 2 nên có hai đường tròn ki và kj, i < j trên nó sẽ có cùng một tổ hợp mầu. Giả sử ki có bán kính lớn hơn kj. Ký hiệu Yilà điểm cắt của OAi và kj. Trong trường hợp đó Yi nằm trên kj và vì những điểm của ki và kj được bôi với cùng một tổ hợp mầu, trên ki có điểm Xi được bôi cùng mầu với Yi. J Ví dụ 4.10. Tổng của độ dài một số vectơ trong mặt phẳng là 4. Chứng minh rằng từ những vectơ này có thể chọn một số vectơ mà tổng độ dài của chúng lớn hơn 1. Lời giải. Chúng ta đưa vào hệ tọa độ và xét vectơ đại diện những vectơ đã cho tại điểm gốc. Chúng ta chiếu những vectơ này xuống 4.2. Bài tập 39 trục tọa độ Ox và Oy. Vì mỗi vectơ 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ả hình chiếu của các vectơ lớn hơn 4. Khi đó trên ít nhất một trong 4 nửa trục của hệ tọa độ tổng độ dài của hình chiếu sẽ lớn hơn 1, điều đó có nghĩa là tổng của độ dài của những vectơ 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 vectơ cũng lớn hơn.) J 4.2. BÀI TẬP . 4.11. Trong hình vuông với cạnh 1 đơn vị cho 112 điểm. Chứng minh rằng ít nhất hai trong số đó có khoảng cách nhỏ hơn 215. . 4.12. (Đề thi Toán Olympic quốc tế lần thứ 25 năm 1984) Trong mặt phẳng cho hai điểm khác nhau O và A. Với mỗi điểm X thuộc mặt phẳng khác O chúng ta ký hiệu a(X) là độ đo bằng radian của góc AOX, đo theo chiều ngược kim đồng hồ từ OA đến OX (0 ≤ a(X) ≤ 2). Còn c(X) là đường tròn tâm O và bán kính có độ dài OX +a(X) OX . Cho trước bộ hữu hạn mầu và mỗi điểm trong mặt phẳng được bôi bằng 1 trong số đó. Chứng minh rằng tồn tại điểm X1 với a(X1) > 0 và trên đường tròn c(X1) có ít nhất 1 điểm được bôi cùng mầu với X1. . 4.13. Trong mặt phẳng cho n điểm, n ≥ 7, sao cho khoảng cách mỗi cặp điểm giữa chúng là khác nhau. Mỗi một điểm được nối với điểm gần nó nhất. Chứng minh rằng không có điểm nào được nối với nhiều hơn 5 điểm khác. . 4.14. Chứng minh rằng trong một hình tròn bán kính 1, không thể chọn được quá năm điểm mà khoảng cách giữa hai điểm một lớn hơn 1. 40 Chương 4. Hình học . 4.15. Người ta quăng 120 hình vuông có kích thước 1 × 1 vào một hình chữ nhật kích thước20 × 25. Chứng minh rằng với mọi cách sắp xếp các hình vuông thì ở trong hình chữ nhật vẫn còn chỗ trống để đặt một hình tròn đường kính 1. CHƯƠNG 5 MỞ RỘNG NGUYÊN LÝ ĐIRICHLÊ 5.1. Nguyên lý Đirichlê mở rộng . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2. Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.3. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.1. NGUYÊN LÝ ĐIRICHLÊ MỞ RỘNG Cho A là tập hữu hạn những phần tử, ký hiệu s(A) là số lượng các phần tử thuộc A. Nguyên lý Đirichlê có thể mở rộng như sau: Nếu A và B là những tập hợp hữu hạn và s(A) > k.s(B), ở đây k là một số tự nhiên nào đó 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, thì tồn tại ít nhất k + 1 phần tử của A mà chúng tương ứng với cùng một phần tử của B Thật vậy, trường hợp k = 1 là nguyên lý Đirichlê mà ta đã xét trong các bài tập từ đầu tới giờ. Để chứng minh mệnh đề trên chúng ta 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 đó s(A) ≤ k.s(B) trái với giả thiết s(A) > k.s(B). Chú ý. Ngay từ những chương đầu nguyên lý này đã được sử dụng với cách chứng minh tương tự như trên. Để tiếp tục hiểu sâu thêm nguyên lý ở dạng mới chúng ta xét một loạt bài toán điển hình. 42 Chương 5. Mở rộng nguyên lý Đirichlê 5.2. VÍ DỤ Ví dụ 5.1. Trong một hình vuông có cạnh bằng 1 ta chọn bất kỳ 51 điểm. Chứng minh rằng ít nhất có ba điểm trong số đó nằm trong một hình vuông có cạnh 0,2. Lời giải. Chúng ta chia hình vuông thành 25 hình vuông con có cạnh 0,2 bằng các đường thẳng song song với các cạnh của hình vuông.Nếu giả sư rằng mỗi hình vuông vừa nhận được chứa không quá 2 điểm thì tất cả các điểm trong hình vuông lớn sẽ có số điểm nhiều nhất là 2 × 25 = 50 dẫn đến vô lý. J Ví dụ 5.2. Tất cả 9 cạnh và 27 đường chéo của một hình chóp đáy đa giác 9 đỉnh được bôi sơn: một số bôi sơn đỏ, còn lại bôi sơn xanh. Chứng minh rằng tồn tại ba đỉnh của hình chóp, mà chúng là những đỉnh của một hình tam giác với các cạnh được sơn cùng một mầu. Lời giải. 9 cạnh bên của hình chóp được sơn bằng hai mầu. Vì 9 > 4.2, từ nguyên lý mở rộng trên suy ra ít nhất có 5 cạnh bên được bôi cùng một mầu. Giả sử đó là SA1, SA2, SA3, SA4, SA5 được bôi cùng mầu đỏ, ở đây S là đỉnh hình chóp. Không ảnh hưởng tới kết luận bài toán chúng ta giả sử các điểm A1, A2, A3, A4, A5 được sắp xếp theo chiều ngược kim đồng hồ. Ít nhất một trong các cạnh của ngũ giác là đường chéo của đa giác đáy; giả sử đó là A1A2. Chúng ta xét tam giác A1A2A4. Những cạnh của nó là các đường chéo của đa giác đáy (do cách xếp trên) và suy ra chúng được bôi sơn.Nếu tất cả các cạnh A1A2, A2A4, A4A1 là mầu xanh thì bài toán đã giải xong. Trường hợp ngược lại một trong các cạnh A1A2, A2A4, A4A1 là mầu đỏ, giả sử đó là A1A2. Khi đó các cạnh của tam giác SA1A2 là mầu đỏ. J 5.2. Ví dụ 43 Ví dụ 5.3. Chứng minh rằng trong mọi đa giác lồi với số cạnh chẵn tồn tại đường chéo không song song với một cạnh nào của đa giác. Lời giải. Bằng qui nạp ta có thể dễ d1 chứng minh được mọi đa giác với n cạnh có n(n − 3) 2đường chéo. Bây giờ chúng ta xét đa giác lồi bất kỳ P có 2k cạnh với k(≥ 2) là một số nguyên. d2 dk−1 a Hình 5.1 Giả sử mỗi đường chéo của P song song với một cạnh nào đó của P. Khi đó mỗi đường chéo d có thể cho tương ứng với cạnh song song với d. Ký hiệu s là số các đường chéo chúng ta có s =2k(2k − 3) 2= k(2k − 3) = 2k(k − 2) + k > (k − 2).2k. Như vậy theo nguyên lý Đirichlê mở rộng suy ra tồn tại k − 1 đường chéo d1, d2, . . . , dk−1 của đa giác P mà chúng tương ứng với cùng một cạnh a của đa giác, nghĩa là a, d1, d2, . . . , dk−1 song song với nhau. Suy ra các đường chéo d1, d2, . . . , dk−1 cùng nằm trong một nửa mặt phẳng xác định bởi cạnh a vì P là đa giác lồi (hình vẽ). Ngoài ra d1, d2, . . . , dk−1 và a là những đoạn thẳng khác nhau và bởi vì số lượng của chúng là k, mỗi đỉnh của đa giác P là điểm đầu của một đoạn nào đó trong chúng. Không ảnh hưởng đến kết quả chứng minh ta giả thiết d1 là đoạn xa nhất đối với a trong các đường chéo d1, d2, . . . , dk−1. Khi đó từ lý luận trên suy ra rằng đa giác P nằm toàn bộ trong một nửa mặt phẳng xác định bởi d1. Điều này trái với tính lồi của đa giác P. J Ví dụ 5.4. Trong mặt phẳng cho 6 điểm. Mỗi đoạn thẳng nối từng cặp 44 Chương 5. Mở rộng nguyên lý Đirichlê điểm được bôi mầu đỏ hoặc xanh. Chứng minh rằng ba điểm trong số các điểm là đỉnh của một tam giác, mà các cạnh của nó được bôi cùng một mầu. Lời giải. Ký hiệu A là một trong các điểm đã cho và xét năm đoạn thẳng, có đỉnh chung là A. Những đoạn thẳng này được sơn hai mầu và vì 5=2.2+1, suy ra từ nguyên lý Đirichlê mở rộng chúng ta có ít nhất ba đoạn cùng mầu. Giả sử đó là AB1, AB2, AB3 mầu xanh. Nếu một vài đoạn thẳng B1B2, B2B3, B3B1 là xanh thì tồn tại một tam giác với ba cạnh xanh và có đỉnh là A. Nếu ba đoạn thẳng B1B2, B2B3, B3B1 là đỏ, thì một tam giác thỏa mãn đề toán đã ra là B1B2B3 (các cạnh đều mầu đỏ). J Ví dụ 5.5. Cho dãy vô hạn các số tự nhiên u1, u2, . . . , un, . . . được xác định theo công thức sau u1 = 3, un+1 = (n + 1)un − n + 1, n = 1, 2, . . .. Cho n số tự nhiên bất kỳ và tập hợ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 bôi sơn bằng một trong n mầu đã cho. Khi đó tồn tại 3 điểm trong M là đỉnh của một tam giác đồng mầu. Lời giải. Chứng minh bằng qui nạp theo n. Với n = 1 chúng ta có u1 = 3 và kết luận là hiển nhiên. Với n = 2 từ công thức tính được u2 = 6, đây là trường hợp ta đã chứng minh ở bài trên. Giả sử bài toán với un điểm và các đoạn thẳng nối được bôi bởi n mầu, có một tam giác với các cạnh cùng mầu. Bây giờ ta xét un+1 điểm bất kỳ, mà đường nối giữa chúng được bôi bằng n + 1 mầu: c1, c2, . . . , cn+1. Lấy A là một trong các điểm trên. Điểm này có thể nối với các điểm còn lại được un+1 − 1 đoạn thẳng bôi mầu. Mặt khác do công thức hồi qui un+1 − 1 = (n + 1)(un − 1) + 1, như vậy theo nguyên lý Đirichlê mở rộng ít nhất un đoạn thẳng có chung đỉnh A được bôi cùng mầu. 5.2. Ví dụ 45 Giả sử AB1, AB2, . . . , ABun được bôi cùng mầu, chẳng hạn mầu c1. Những khả năng có thể xẩy ra như sau: a) Nếu một trong các đoạn thẳng nối giữa các điểm B1, B2, . . . , Buntheo từng cặp được bôi bằng mầu c1 thì tồn tại tam giác đồng mầu có đỉnh A. Các cạnh của tam giác này sơn mầu c1. b) Không có một đoạn nào trong các đoạn thẳng nối giữa các điểm B1, B2, . . . , Bun được sơn mầu c1. Khi đó áp dụng qui nạp toán học cho những điểm B1, B2, . . . , Bun. Điều này có thể được vì tất cả các đoạn thẳng đã nối được bôi sơn n mầu c2, c3, . . . cn+1. Trong trường hợp này ta cũng dẫn đến kết luận tồn tại một tam giác đồng mầu. J Ví dụ 5.6. Cho số hạng của dãy un được định nghĩa như bài trước. Tập hợp những số tự nhiên từ 1 đến un − 1 được phân chia bằng phương pháp bất kỳ vào n tập hợp con, mà từng đôi một không có phần tử chung. Chứng minh rằng tồn tại hai số của cùng một tập hợp con, mà tổng của chúng cũng nằm trong tập hợp con này ; hoặc là tồn tại một số trong một tập hợp con nào đó, mà sau khi nhân đôi vẫn thuộc tập hợp con này. Lời giải. Ký hiệu những tập hợp con đã cho là là A1, A2, . . . , An. Chúng ta xét tập hợp bất kỳ M gồm un điểm, mà chúng được đánh số bằng phương pháp nào đó trong các số 0, 1, 2, . . . , un − 1. Chúng ta bôi mầu những đoạn thẳng nối các điểm trong M bằng n mầu c1, c2, . . . , cn theo cách sau: Đoạn thẳng nối các điểm thứ i và j, với i > j được sơn bằng mầu ck khi và chỉ khi hiệu i − j thuộc tập hợp Ak. Theo bài toán trước 5.5 ba điểm nào đó của M là đỉnh của một tam giác cùng mầu. Giả sử các điểm này là i, j, k và i > j > k. Khi đó các số i − j, j − k và i − k = (i − j) + (j − k) nằm trong cùng một 46 Chương 5. Mở rộng nguyên lý Đirichlê tập hợp As và chúng có các tính chất ta cần tìm. J Ví dụ 5.7. Trong mặt phẳng cố định hệ tọa độ Oxy. Chúng ta xét tập hợp R gồm những điểm với tọa độ (x, y), ở đây x, y là những số nguyên và 1 ≤ x ≤ 12, 1 ≤ y ≤ 10. Mỗi điểm này được sơn bằng một mầu trắng, xanh hoặc đỏ. Chứng minh rằng tồn tại hình chữ nhật có các cạnh song song với các trục tọa độ, mà đỉnh của nó là những điểm của R được sơn cùng một mầu. Lời giải. Trong chứng minh ta dùng hai khẳng định sau: a) Nếu X là tập hữu hạn với n phần tử, thì số lượng tập hợp con của X gồm các cặp phần tử {x, y}, với x ∈ X, y ∈ X là n(n − 1) 2. b) Mọi số dương bất kỳ x1, x2, . . . , xn đều thỏa mãn bất đẳng thứcx21 + x22 + · · · + x2n 2≥ (x1 + x2 + · · · + xn 2)2 Dấu bằng chỉ xẩy ra khi x1 = x2 = . . . = xn. Trở lại bài toán đang xét, vì tổng số các điểm ta xét là 120, nên ít nhất có 40 điểm được bôi cùng mầu, giả sử là mầu đỏ. Với mỗi i = 1, 2, . . . , 12 chúng ta ký hiệu lilà đường thẳng đi qua điểm (i, 0) và song song với trục Oy. Nếu trên li có ni điểm đỏ, i = 1, 2, . . . , 12, n1 + n2 + · · · + n12 ≥ 40. Ngoài ra từ ni điểm có thể tạo ra các cặp đôi được sắp có số lượng ni(ni − 1) tồn tại đúng ni(ni − 1) 2. Nghĩa là với mỗi i = 1, 2, . . . , 12 2cặp số nguyên {j1, j2} thỏa mãn 1 ≤ j1 ≤ 10, 1 ≤ j2 ≤ 10 và các điểm {i, j1} và {i, j2} là đỏ. Mặt khác số lượng của tất cả cặp những số nguyên {j1, j2} với 1 ≤ j1 ≤ 10, 1 ≤ j2 ≤ 10 bằng 10(10 − 1) 2= 45. Chúng ta phải chứng minh rằng tổng các số n1(n1 − 1) 2,n2(n2 − 1) 2, . . . ,n12(n12 − 1) 2 5.2. Ví dụ 47 lớn hơn 45. Từ đó suy ra tồn tại những chỉ số khác nhau i1 và i2 với 1 ≤ i1 < i2 ≤ 12 và cặp số nguyên {j1, j2} với 1 ≤ j1 ≤ 10, 1 ≤ j2 ≤ 10 sao cho 4 điểm {i1, j1}, {i1, j2}, {i2, j1}, {i2, j2} là đỏ. Bởi những điểm này là đỉnh của hình chữ nhật với các cạnh song song với trục tọa độ, như vậy bài toán được chứng minh. Như vậy, ta chỉ còn phải chứng minh 2+n2(n2 − 1) S =n1(n1 − 1) Sử dụng bất đẳng thức b) 2+ · · · +n12(n12 − 1) 2> 45 S =12((n1 −12)2 −14) + 12((n2 −12)2 −14) + · · · +12((n12 −12)2 −14) =12((n1 −12)2 + (n2 −12)2 + · · · + (n12 −12)2) − 1218 ≥12.12((n1 −12) + (n2 −12) + · · · + (n12 −12) 12 )2 −32 =124((n1 + n2 + · · · + n12) − 1212)2 −32 ≥124(40 − 6)2 −32=342 24 −32> 45 vì n1 + n2 + · · · + n12 ≥ 40. J Ví dụ 5.8. (Bài thi Olympic toán quốc tế lần thứ 20, 1978) 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 48 Chương 5. Mở rộng nguyên lý Đirichlê số báo danh a1 < a2 < . . . < a330 < . . . Chúng ta xét những hiệu xi = a330 − ai, i = 1, 2, . . . 329. Nếu có một số xi nào đó trùng với aj (số báo danh của một đaj 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 với mọi i, j, thì số xilà số báo danh của một số đạ 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 năm nước này (ký hiệu 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 < b3 < . . . < b66 < . . . với bi = xni, i = 1, 2, . . . , 66. Chúng ta lại xét hiệu yi = b66 − bi, i = 1, 2, . . . , 65 Nếu một hiệu nào đó trùng với số báo danh bj của một đại biểu của 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 = an66 + ak. Nếu hai trường hợp trên không xẩy ra, thì những số 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. J Ví dụ 5.9. (Đề thi Toán vô địch nước Anh, 1978) Một hình lập phương có cạnh bằng 15 chứa 11.000 điểm. Chứng minh rằng có một hình cầu bán kính bằng đơn vị chứa ít nhất 6 điểm trong số 11.000 điểm đã cho. Lời giải. Chia mỗi cạnh của hình lập phương thành 13 phần bằng nhau, thế thì hình lập phương ban đầu được chia thành 133 = 2187 hình lập phương nhỏ. Vì hình lập phương ban đầu chứa 11.000 điểm, nên tồn tại một hình lập phương nhỏ chứa ít nhất 6 điểm. Dễ thấy cạnh của hình lập phương nhỏ là 1513, do đó bán kính hình cầu ngoại tiếp hình lập phương nhỏ là r =12r3(1513)2 =12r675 169 < 5.2. Ví dụ 49 r676 169 =12√4 = 1. Vậy: Tồn tại một hình cầu bán kính 1 chứa ít 1 2 nhất 6 điểm trong 11.000 điểm đã cho. J Ví dụ 5.10. Trong mặt phẳng cho một số hữu hạn điểm, một số trong chúng được nối lại bằng đoạn thẳng. Chúng ta nói rằng một dãy e1,e2, . . . ,em từ các đọan thẳng được nối là một dây chuyền, nếu mọi cặp đoạn thẳng liền nhau ei và ei+1 có chung một đầu mút, i = 1, 2, . . . , m − 1. Số lượng m những đoạn thẳng trong dây chuyền gọi là độ dài của nó. Chúng ta xét bài toán: Cho n điểm, từ các điểm này dựng những đoạn thẳng, số lượng đoạn thẳng đã dựng là q. Giả sử những đoạn thẳng được đánh số một cách bất kỳ bằng các số 1, 2, . . . , q. Khi đó trong cách tạo hình như vậy tồn tại một dây chuyền với độ dài nhỏ nhất là 2qn, trên dây chuyền này các số ứng với những đoạn thẳng thành phần lập nên một dãy số giảm ngặt. Lời giải. Gọi G là cấu hình bất kỳ của những điểm và đoạn thẳng, mà chúng được đánh số bằng số tự nhiên như đề bài đã ra. Với mọi v thuộc G chúng ta ký hiệu LG(v) là độ dài của dây chuyền dài nhất trong G, mà nó bắt đầu từ v và giảm dần. Bằng phương pháp qui nạp chúng ta sẽ chứng minh bất đẳng thức sau được thỏa mãn LG(v1) + LG(v2) + · · · + LG(vn) ≥ 2q (5.1) ở đây v1, v2, . . . , vn là tất cả các điểm thuộc G. Kết luận phải chứng minh suy ra từ (5.1) theo nguyên lý Đirichlê mở rộng: Một trong các số LG(v1), LG(v2), . . . , LG(vn) lớn hơn hoặc bằng 2qn, như vậy tồn tại dây chuyền với tính chất đã chỉ ra. Do đó chỉ còn phải chứng minh (5.1) được thỏa mãn với n điểm của G và q đoạn thẳng được 50 Chương 5. Mở rộng nguyên lý Đirichlê đánh số như mô tả ở đầu bài. Bằng qui nạp với q = 1 bất đảng thức (5.1) là hiển nhiên. Giả sử (5.1) thỏa mãn cho mọi cấu hình với q − 1 đoạn thẳng và chúng ta xem xét cấu hình với n điểm và q đoạn thẳng. Nếu đoạn thẳng ký hiệu là q nối với hai điểm vi và vjthì chúng ta bỏ đoạn thẳng này và nhận được cấu hình G0của n điểm và q − 1 đoạn thẳng. Với cấu hình này theo qui nạp chúng ta có LG0(v1) + LG0(v2) + · · · + LG0(vn) ≥ 2(q − 1). Bây giờ chúng ta xét điểm vj. Dây chuyền giảm dần xuất phát từ xj có độ dài LG0(vj), và những đoạn thẳng trong dây chuyền này được ký hiệu bởi những số nào đó trong dẫy 1, 2, . . . , q − 1. Nếu nối thêm vào dây chuyền một đoạn thẳng có ký hiệu q chúng ta sẽ nhận được dây chuyền giảm với điểm đầu vi và với độ dài LG0(vj) + 1. Theo định nghĩa của LG(vi) chúng ta có LG(vi) ≥ LG0(vj) + 1. Bằng một cách chứng minh hoàn toàn tương tự chúng ta cũng chứng minh được LG(vj) ≥ L0G(vi) + 1. Mặt khác, LG(vk) = LG0(vk) với mọi điểm vkthuộc G mà nó khác vi và vj. Suy ra, LG(v1) + LG(v2) + · · · + LG(vn) ≥ LG0(v1) + LG0(v2) + · · · + LG0(vn) + 2 ≥ 2(q − 1) + 2 = 2q. J 5.3. BÀI TẬP . 5.11. (Đề thi vô địch Áo - Balan, 1978) Cho 1978 tập hợp, mỗi tập hợp có 40 phần tử. Biết rằng hai tập hợp bất kỳ có đúng một phần tử chung. Chứng minh rằng, tồn tại một phần tử thuộc tất cả 1978 tập hợp trên. . 5.12. Chứng minh rằng mọi tập hợp chứa 55 số chọn được từ tập hợp số {1, 2, 3, . . . , 100} chứa hai số mà hiệu của chúng bằng 9. . 5.13. Cho n là số tự nhiên. Cho n tập hợp con A1, A2, . . . , An của mặt phẳng với tính chất: với mọi i = 1, 2, . . . , n tồn tại n + 1 phép tịnh tiến sao cho các ảnh của Ai qua các phép tịnh tiến từng đôi một 5.3. Bài tập 51 không có điểm chung. Chứng minh rằng tồn tại một điểm trên mặt phẳng, không nằm trong bất cứ tập hợp Ai nào, i = 1, 2, . . . , n. . 5.14. Trong phần trong của một tam giác đều với cạnh dài 15 đơn vị, chúng ta chọn bằng phương pháp bất kỳ 111 điểm. Chứng minh rằng tồn tại hình tròn với đường kính √3, mà nó phủ ít nhất 3 điểm trong số những điểm đã chọn ở trên. . 5.15. (Đề thi vô địch Quốc gia Bungari, 1977) Trong một nhóm người, hai người X và Y gọi là quen nhau gián tiếp, nếu họ trực tiếp quen nhau, hoặc là nếu tồn tại một dây truyền những người Z1, Z2, . . . , Zp sao cho X và Z1 quen nhau, Z1 và Z2 quen nhau,... , Zp và Y quen nhau. Cho biết nhóm đó gồm 134 người, còn giữa mỗi nhóm nhỏ 8 người từ nhóm đã biết ít nhất có hai người quen gián tiếp. Chứng minh rằng có một nhóm nhỏ 12 người trong nhóm người đã biết, mà mọi cặp hai người trong nhóm nhỏ này đều quen nhau gián tiếp. CHƯƠNG 6 BÀI TẬP SỐ HỌC NÂNG CAO 6.1. Định lý cơ bản của số học . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2. Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.3. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.1. ĐỊNH LÝ CƠ BẢN CỦA SỐ HỌC Trong lý thuyết số học cơ sở có một định lý cơ bản: Mọi số tự nhiên lớn hơn một đều có thể phân tích ra tích các thừa số nguyên tố và phân tích đó là duy nhất nếu ta không để ý đến thứ tự của các thừa số. Cho p1, p2, . . . , pn là những số nguyên tố khác nhau. Trong chương này chúng ta xét một số kết luận về về tập hợp M của các số tự nhiên mà nó có thể phân tích ra các thừa số nằm trong {p1, p2, . . . , pn}. Mọi số x của M có thể biểu diễn dưới dạng x = pα1 1pα2 2. . . pαn n ở đây α1, α2, . . . , αn là các số nguyên không âm. 6.2. VÍ DỤ Ví dụ 6.1. Từ tập hợ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ố 6.2. Ví dụ 53 chính phương. Lời giải. Nhận xét rằng một số tự nhiên x = pα1 1pα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 với mọi i = 1, 2, . . . , n. Vậy (α1, α2, . . . , αn) là bộ xếp thứ tự n số gồm số 0 và 1. 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ó 2 số trong chúng có cùng bộ sắp xếp gồm số 0 và số 1 giống n và y = pβ1 1pβ2 nhau. Giả sử các số đó là x = pα1 1pα2 2. . . pαn 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, 2, . . . , n . Do đó các số mũ αi và βicó cùng tính chẵn lẻ như nhau với bất kỳ i = 1, 2, . . . , n. Khi đó α1 + β1, α2 + β2, . . . , αn + βn, là các số chẵn và theo nhận xét ban đầu tích n ) = pα1+β1 1pα2+β2 xy = (pα1 1pα2 n )(pβ1 1pβ2 2. . . pβn 2. . . pαn+βn 2. . . pαn n đúng là số chính phương. J Ví dụ 6.2. 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. Lời giải. Cho x1, x2, . . . , xn là những số bất kỳ của M. Với mỗi tập con khác trố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 hợp con {i1, i2, . . . , ik} cho tương ứng với n-bộ (α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. 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 và 1 là 2n. Suy ra tồn tại những 54 Chương 6. Bài tập số học nâng cao tập hợp con khác trống khác nhau {i1, i2, . . . , ik} và {j1, j2, . . . , jl} 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 1pα2 2. . . pαn n và xj1xj2. . . xjk = pβ1 1pβ2 2. . . pβn n thì các số mũ αi và βi có cùng tính chẵn lẻ với i = 1, 2, . . . , k. Điều này có nghĩa là tích của những số xi1, xi2, . . . , xik, xj1, xj2, . . . , xjklà chính phương. Nếu {i1, i2, . . . , ik} và {j1, j2, . . . , jl} 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 = xi1xi2. . . xikxj1xj2. . . xjklặp lại đúng những số xs, mà s thuộc {i1, i2, . . . , ik} và {j1, j2, . . . , jl}. Chúng ta loại trừ trong P tất cả cá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à chính phương. J Ví dụ 6.3. Chứng minh rằng giữa mọi 3.2n + 1 số từ tập hợp M có thể chọn được 4 số mà tích của chúng là lũy thừa bậc bốn của một số. Lời giải. Vì 3.2n + 1 > 2n + 1 giữa những số đã chọn theo bài 6.1 có hai số mà tích của chúng là một số chính phương. Tách hai số trên ra thì còn lại 3.2n − 1 số và áp dụng tiếp 6.1 cho hai số nữa mà tích của chúng là số chính phương. Chúng ta có thể lặp lại quá trình này ít nhất (3.2n − 1) − (2n + 1) 2= 2n + 1 lần. Giả sử chúng ta nhận được 2n + 1 cặp (x1, y1),(x2, y2), . . . , với xiyilà các số chính phương, i = 1, 2, . . . , 2n + 1. Chú ý rằng theo cách chọn trên thì các cặp số (x1, y1),(x2, y2), . . . ,(x2n+1, y2n+1) từng đôi một khác nhau. Đến đây suy ra các số √x1y1,√x2y2, . . . , √x2n+1y2n+1 là những số nguyên và thuộc M. Khi đó áp dụng một lần nữa 6.1 chỉ ra rằng tích của hai số nào đó trong chúng là chính phương. Như vậy xiyixjyj = t4 nghĩa là tích của 4 số từng đôi một khác nhau xi, yi, xj, yjlà lũy thừa bậc bốn của một số. J Ví dụ 6.4. Cho p là một số nguyên tố lẻ và a1, a2, . . . , a p+1 2 là những số 6.2. Ví dụ 55 tự nhiên khác nhau nhỏ hơn p. Chứng minh rằng với mọi số tự nhiên r nhỏ hơn p, tồn tại hai số (có thể bằng nhau) ai và aj, mà tích của chúng khi chia cho p có số dư đúng là r. Lời giải. Áp dụng một định lý trong lý thuyết số cơ sở: Nếu a và b là hai số nguyên tố cùng nhau, thì tồn tại một số nguyên x sao cho ax ≡ 1 (mod b). Với mỗi i = 1, 2, . . . , p + 1 2, các số ai và p là nguyên tố cùng nhau, vì 1 ≤ ai ≤ p − 1 và p là số nguyên tố. Áp dụng định lý vừa phát biểu trên, tồn tại các số nguyên b1, b2, . . . , b p+1 sao cho với mọi 2 i = 1, 2, . . . , p+1 2các đẳng thức sau đều thỏa mãn aibi ≡ 1 (mod p) (6.1) Chúng ta xét dãy số a1, a2, . . . , a p+1 2 ,rb1,rb2, . . . ,rb p+1 2 . Chúng ta có tất cả p + 1 số sao cho ít nhất hai số trong chúng khi chia cho p có cùng một số dư. Theo giả thiết các số a1, a2, . . . , a p+1 2 khác nhau hoàn toàn và nhỏ hơn p. Suy ra số dư của chúng theo môdd un p là khác nhau. Vì r là số nguyên tố cùng nhau với p, nên dễ dàng chứng minh được rằng các số rb1,rb2, . . . ,rb p+1 2 cho số dư hoàn toàn khác nhau khi chia cho p. Nghĩa là chỉ tồn tại hai chỉ số i và j sao cho ai ≡ rbj (mod p). Từ (6.1) chúng ta nhận được aiaj ≡ rbjaj ≡ r.1 ≡ r (mod p). J Ví dụ 6.5. Bổ đề Tue: Cho n là số tự nhiên lớn hơn 1 và a là số nguyên tố cùng nhau với n. Khi đó tồn tại các số nguyên x và y, mà chúng thỏa mãn phương trình ax ≡ y (mod n) và các bất phương trình 1 ≤ x ≤ [√n], 1 ≤ |y| ≤ [√n]. Lời giải. Chúng ta xét tất cả các số có dạng au − v, ở đây u và v chạy 56 Chương 6. Bài tập số học nâng cao độc lập nhau trong các số 0, 1, 2, . . . , [√n]. Số lượng tất cả các số đó là ([√n] + 1)2. Suy ra số này lớn hơn n vì ([√n] + 1)2 > (√n)2 = n. Bởi có đúng n số dư khác nhau theo môđun n, nên tồn tại hai cặp số khác nhau (u1, v1),(u2, v2) từ các số nguyên sao cho 1 ≤ ui ≤ [√n], 1 ≤ vi ≤ [√n], i = 1, 2 và au1 − v1 ≡ au2 − v2 (mod n). Dễ dàng chứng minh được v1 khác v2. Thật vậy, nếu ngược lại thì au1 ≡ au2 (mod n),suy ra u1 ≡ u2 (mod n), do a là số nguyên tố cùng nhau với n. Mặt khác, u1, u2 là các số tự nhiên nhỏ hơn n. Như vậy đẳng thức sau cùng chỉ có một khả năng duy nhất u1 = u2. Do đó cặp (u1, v1),(u2, v2) trùng nhau, trái với cách chọn trên. Như vậy u1 và u2 cũng phải khác nhau. Có thể giả thiết u1 > u2 mà không ảnh hưởng đến kết quả chứng minh. Bây giờ ta đặt x = u1 − u2, y = v1 − v2. Từ đó suy ra 1 ≤ x ≤ [√n], 1 ≤ |y| ≤ [√n] và ax ≡ y (mod n). J Ví dụ 6.6. Áp dụng bổ đề Tue: Mọi số nguyên tố dạng 4k + 1 có thể biểu diễn dưới dạng tổng bình phương của hai số nguyên. Lời giải. Chúng ta chứng minh khẳng định sau: Nếu p = 4k + 1 là số nguyên tố, thì phương trình x2 ≡ −1 (mod p) có nghiệm. Thật vậy, Vì p là số nguyên tố, theo định lý Wilson, (p − 1)! ≡ −1 (mod p). Ngoài ra p − 1 ≡ −1 (mod p), p − 2 ≡ −2 (mod p), . . . , p −p+1 p+1 2(mod p). Suy ra, −1 ≡ (p − 1)! = 1.2 . . . .(p − 1) 2 ≡ (−11)(−21). . .(−(p − 1 2 ≡ (p + 1) 2 2)2) 2 (1.2 . . . p − 1 = (−1)p−1 = (( p − 1 2)2 = (−1)2k(( p − 1 2)!)2 2)!)2(mod p). 6.2. Ví dụ 57 Như vậy a = ( p − 1 2)! là nghiệm của phương trình trên. Vì a2 + 1 chia hết cho p nên a là nguyên tố cùng nhau với p. Bây giờ ta áp dụng bổ đề Tue cho hai số a và p. Tồn tại các số nguyên x và y mà 1 ≤ x ≤ [√p], 1 ≤ |y| ≤ [√p] và ax ≡ y (mod p). Khi đó a2x2 ≡ y2 (mod p), như vậy x2 ≡ −y2(mod p), vì a2 ≡ −1 (mod p). Từ đó suy ra x2 + y2chia hết cho p. Mặt khác 1 ≤ x2 ≤ p, 1 ≤ y2 ≤ p. Ta thấy rằng x2 = p và y2 = p không thể xẩy ra vì p là số nguyên tố, suy ra 0 < x2 + y2 < 2p và vì x2 + y2chia hết cho p, nên x2 + y2 = p. J Chú ý: Tương tự, chứng minh rằng mọi số p, sao cho phương trình x2 ≡ −2 (mod p) có nghiệm, đều có thể biểu diễn dưới dạng p = x2 + 2y2 với x, y là các số nguyên. Ví dụ 6.7. (Đề thi Toán Olympic quốc tế lần 18 năm 1976) Cho hệ p phương trình với q = 2p ẩn a11x1 + a12x2 + · · · + a1qxq = 0 . . . . . . . . . . . . . . . . . . . . . ap1x1 + ap2x2 + · · · + apqxq = 0 Tất cả các hệ số aij thuộc tập hơp {−1, 0, 1}. Chứng minh rằng tồn tại nghiệm (x1, x2, . . . , xq) của hệ, mà nó thỏa mãn a) tất cả xj(j = 1, 2, . . . , q) là nhưng số nguyên; b) ít nhất có một j(j = 1, 2, . . . , q) mà xj ≤ 0; c) với mọi j(j = 1, 2, . . . , q) ta luôn có xj ≤ q; Lời giải. Xét bộ (x1, x2, . . . , xq) gồm những số nguyên bất kỳ, mà chúng thỏa mãn |x1| ≤ p, |x2| ≤ p, . . . , |xq| ≤ p. Bởi vì tất cả các hệ số của hệ phương trình chỉ là -1,0 hoặc 1, với việc thay các ẩn 58 Chương 6. Bài tập số học nâng cao x1, x2, . . . , xq chúng ta nhận được giá trị của mỗi phương trình nằm trong khoảng [−pq, pq]. Thật vậy, với mỗi i = 1, 2, . . . , p chúng ta có |ai1x1 + ai2x2 + · · · + aiqxq| ≤ |x1| + |x2| + · · · + |xq| ≤ pq. Suy ra, nếu thay những ẩn trong tất cả phương trình của hệ tương ứng với x1, x2, . . . , xq sẽ nhận được bộ p số nguyên (y1, y2, . . . , yp). Tất cả những số này đều nằm trong khoảng [−pq, pq]. Trong khoảng này có đúng 2pq + 1 số nguyên. Suy ra giữa những bộ sắp xếp p phần tử như ở trên có (2pq + 1)p bộ xếp khác nhau. Mặt khác số lượng những bộ xếp q phần tử (x1, x2, . . . , xq) mà |xj| ≤ p với j = 1, 2, . . . q, là (2p +1)q. Dễ thấy rằng từ q = 2p suy ra (2p + 1)q > (2pq + 1)p. Theo nguyên lý Đirichlê tồn tại hai bộ q- số nguyên (x01, x02, . . . , x0q) và (x001, x002, . . . , x00q) khác nhau mà chúng thỏa mãn |x0j| ≤ p, |x00j| ≤ p với j = 1, 2, . . . q và sau khi thế vào hệ phương trình cho cùng một bộ p số nguyên (y1, y2, . . . , yp). Đặt x1 = x01 − x001, x2 = x02 − x002, . . . , xq = x0q − x00q. Rõ ràng (x1, x2, . . . , xq) là nghiệm của hệ phương trình và xjlà các số nguyên với mọi j = 1, 2, . . . , q. Vì (x01, x02, . . . , x0q) và (x001, x002, . . . , x00q) là hai bộ q số hoàn toàn khác nhau, thì ít nhất một trong các số xj khác không. Cuối cùng với mọi j = 1, 2, . . . , q chúng ta có |xj| = |x0j − x00j| ≤ |x0j| + |x00j| ≤ p + p = 2p = q. Như vậy (x1, x2, . . . , xq) là nghiệm của hệ phương trình có tính chất mong muốn. J Ví dụ 6.8. (Đề thi Toán Olympic quốc tế lần 28 năm 1987) Cho x1, x2, . . . , 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, 2, . . . , n và thỏa mãn bất phương trình sau |a1x1 + a2x2 + · · · + anxn| ≤ (k−1)√n kn−1 6.2. Ví dụ 59 Lời giải. Chúng ta sử dụng bất đẳng thức Cosi-Buniakovski-Svars |α1β1 + |α2β2 + · · · + |αnβn| ≤ q α21 + · · · + α2n q β21 + · · · + β2n , đus 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. 2, y1 = −k−1 Bây giờ chúng ta xét các số y0 = −k−1 2 + (k − 1) = k−1 2 + 1, . . . , yk−1 = −k−1 2Số lượng của chúng là k và hiệu từng cặp trong chúng là những số nguyên, mà giá trị tuyệt đối của nó không quá k − 1. Mỗi bộ sắp xếp n-thành phần β = (b1, b2, . . . , bn), ở đây bilà một số nào đó trong y1, y2, . . . , yn với mọi i = 1, 2, . . . , n, chúng ta đặt tương ứng với một số Sβ = b1x1 + b2x2 + · · · + bnxn. Từ bất đẳng thức Cosi Sβ = b1x1 + b2x2 + · · · + bnxn ≤ = q q b21 + b22 + · · · + b2n b21 + b22 + · · · + b2n q x21 + x22 + · · · + x2n Nhưng |bi| ≤ k−1 2với mọi i = 1, 2, . . . , n sao cho q |Sβ| ≤ b21 + b22 + · · · + b2n ≤k − 1 2 √n hoặc là −k−1 2 √n ≤ Sβ ≤ k−1 2 √n. Theo phương pháp này n-bộ β = (b1, b2, . . . , bn), ở đây bilà một trong các số y0, y1, . . . , yk−1 với mọi i = 1, 2, . . . , n, được đặt tương ứng với một số Sβ = b1x1 + b2x2 + · · · + bnxn trong đoạn ∆ = [−k−1 2 √n,k−1 2 √n]. Số lượng n-bộ √n. được sắp xếp là kn. Chia ∆ ra kn − 1 đoạn nhỏ với độ dài k−1 kn−1 Từ nguyên lý Đirichlê 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 60 Chương 6. Bài tập số học nâng cao một đoạn nhỏ. Đặt a1 = b1 − c1,a2 = b2 − c2, . . . , an = bn − cn. Dễ kiểm tra được a1, a2.., an thỏa mãn điều kiện đã cho. Thật vậy, với mọi i = 1, 2, . . . , n số ai = bi − cilà 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. J Ví dụ 6.9. Chứng minh rằng mỗi bộ gồm 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 thỏa mãn bất đẳng thức sau 0 < x − y < 3√3 xy (6.2) Lời giải. Chúng 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 đã cho suy ra 1 ≤√3 xi ≤ 10, i = 1, 2, . . . , 11. Chúng ta chia khoảng [1,10] ra mười phần bằng nhau. Khi đó, có ít nhất một trong hai số √3 x1,√3 x2, . . . , √3 x11 nằm trong cùng một đoạn nhỏ. Nếu các số đó là √3 xi và 3√xj, i 6= j và xi > xj, chúng ta có 0 <√3 xi − 3pxj ≤910 < 1. (6.3) Như vậy, 0 < (√3 xi − 3√xj)3 < 1, kết hợp với (6.3) ta có 0 < xi − xj < 1 + 3 3√xixj(√3 xi − 3√xj) < 1 + 3 3√xixj. J Chú ý: Bài toán không còn đúng với bộ 10 số thực trong khoảng [1,1000]. Phản ví dụ: bộ số 13, 23, . . . , 103. nếu i 6= j và i > j chúng ta có (i − j)3 ≥ 1, như vậy i2 + ij + j2 ≥ 1 + 3ij. Nghĩa là i − j = (i − j)(i2 + ij + j2) ≥ 1 + 3ij. đẳng thức xẩy ra khi i = j + 1. Ví dụ 6.10. Cho 7 số thực bất kỳ. Chứng minh rằng giữa chúng có 6.3. Bài tập 61 thể chọn được hai số, chẳng hạn x và y, sao cho 0 ≤x − y 1 + xy≤ √3 3. 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 = tg αi, ở đây αilà một số trong khoảng (−π2,π2), i = 1, 2, . . . , 7. Chúng ta chia đoạn này ra sáu đoạn con có độ dài bằng nhau, nghĩa là bằng π6. Dễ dàng thấy rằng ít nhất có hai số trong α1, α2, . . . , α7 cùng nằm trong một đoạn coni đó. Nếu chúng ta ký hiệu các số đó là αi và αj, αi ≥ αj, thì từ đó suy ra 0 ≤ αi − αj ≤ π6. Vì hàm số tg là tăng trong khoảng (−π2,π2), suy ra 0 ≤ tg(αi − αj) = tg αi − tg αj 1 + xixj≤ tgπ6=√33. 1 + tg αitg αj=xi − xj J Chú ý: Bằng cách giải của hai bài tập này chúng ta có thể sáng tạo ra một loạt bài toán tương tự, mà với cách giải bình thường khó mà giải quyết được. 6.3. BÀI TẬP . 6.11. (Đề thi Toán Olympic quốc tế lần 26 năm 1985). Cho tập hợp M gồm 1985 số tự nhiên, không có số nào có ước số lớn hơn 26. Chứng minh rằng từ những phần tử của M có thể chọn được 4 số từng đôi một khác nhau mà tích của chúng là lũy thừa bậc 4 của một số nguyên. (kết luận đúng với tập hợp gồm 3.29 + 1 = 1537 số mà những ước số của chúng không quá 23). . 6.12. Cho bốn số dương bất kỳ. Chứng minh rằng có hai số trong 62 Chương 6. Bài tập số học nâng cao bốn số đó, chẳng hạn x và y, thỏa mãn bất phương trình sau 1 + x + y + 2xy≤ 2 −√3. 0 ≤x − y . 6.13. Chứng minh rằng một số tự nhiên có thể biểu diễn thành tổng bình phương của hai số nguyên khi và chỉ khi, trong phân tích ra dạng chính tắc của nó, các thừa số nguyên tố dạng 4k + 3 đều có số mũ chẵn. . 6.14. Chứng minh rằng từ k + 1 số, mà chúng nhỏ hơn 2k, luôn luôn có thể chọn được hai số mà tỷ số của chúng là một lũy thừa của 2. . 6.15. Cho n là một số lẻ. Chứng minh rằng từ (n − 1)2 + 1 số nguyên bất kỳ có thể chọn được n số sao cho tổng của chúng chia hết cho n. CHƯƠNG 7 BÀI TẬP DẪY SỐ NÂNG CAO 7.1. Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.2. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.1. VÍ DỤ Ví dụ 7.1. Cho dãy Fibonaxi u1 = u2 = 1, un = un−1 + un−2. Với mọi số nguyên dương m, thì giữa những số hạng từ đầu dẫy đến số hạng thứ m2 − 1 tồn tại một số hạng chia hết cho m. Lời giải. Chúng ta ký hiệu k là phần dư của số k cho m. Chúng ta xét các cặp phần dư của dãy Fibonaxi khi chia cho m: (u1, u2).(u2, u3),(u3, u4), . . . ,(un, un+1), . . . (7.1) Nếu chúng ta qui định hai cặp (a1, b1) và (a2, b2) là bằng nhau khi a1 = b1 và a2 = b2, thì số tất cả khả năng của các cặp phần dư khi chia cho m là m2. Vì thế chúng ta lấy m2 + 1 số hạng đầu tiên của dãy (7.1) thì trong chúng phải có hai cặp trùng nhau,( theo nguyên lý Đirichlê ) và từ đó các cặp sau lặp lại. Giả sử cặp (uk, uk+1) là cặp đầu tiên lặp lại trong (7.1). Chúng ta sẽ chứng minh rằng cặp này bằng cặp (1, 1). Thật vậy, giả sử ngược lại, nghĩa là cặp đầu tiên lặp lại là (uk, uk+1), với k > 1. Khi đó chúng ta sẽ tìm được trong (7.1) một cặp (ul, ul+1),(l > k), mà nó bằng (uk, uk+1) 64 Chương 7. Bài tập dẫy số nâng cao . Như vậy ul−1 = ul+1 − ul và uk−1 = uk+1 − uk, do ul+1 = uk+1 và ul = uk, nên phần dư của ul−1 và uk−1 khi chia cho m cũng bằng nhau, nghĩa là ul−1 = uk−1. Từ đó suy ra (uk−1, uk) = (ul−1, ul), vậy cặp (uk−1, uk)nằm trong dãy (7.1) trước cả (uk, uk+1). Điều đó nói lên rằng (uk, uk+1) không phải cặp lặp lại đầu tiên, trái với giả thiết đặt ra. Nghĩa là k > 1 không thể xảy ra, vậy k = 1. Như vậy cặp (1, 1) là cặp đầu tiên lặp lại trong (7.1). Giả sử nó lặp lại t lần (1 < t < m2 + 1). hoặc là (ut, ut+1) = (1, 1). Nghĩa là ut và ut+1 khi chia cho m cho phần dư cùng là 1, vậy hiệu của chúng chia hết cho m. Nhưng ut+1 − ut = ut−1. Như vậy số hạng thứ t − 1 của dãy Fibonaxi sẽ chia hết cho m. J Ví dụ 7.2. Giả sử a và x là các 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 = axn − 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đôi một nguyên tố cùng nhau. Đặt q = ui1ui2. . . uik. Xét (q + 1) số sau a, ax, ax2, . . . , axq. Theo nguyên lý Đirichlê tồn tại hai số nguyên r,s sao cho 0 ≤ r < s ≤ q và axr ≡ axs(mod q) =⇒ axr − axs ≡ 0 (mod q) hay axr(1 − xs−r) ≡ 0 (mod q) (7.2) Theo giả thiết ta có (x, a − 1) = 1, nên suy ra (axr, uij) = 1, ∀j = 1, 2, . . . , k. (7.3) 7.1. Ví dụ 65 Từ (7.3) suy ra (axr, q) = 1. (7.4) Từ (7.2) và (7.4) có xs−r ≡ 1 (mod q) =⇒ xs−r = lq + 1 với l ∈ N. Xét số uik+j = axs−r − a + 1. Vậy uik+j = a(lq + 1) − a + 1 = qal + 1. (7.5) Từ (7.5) ta có (uik+j, uij) = 1, ∀j = 1, 2, . . . , k. (7.6) Hệ thức (7.6) chứng tỏ rằng luôn có thể bổ sung thêm vào bộ số q = ui1ui2. . . uikcác số mới, mà bộ số này vẫn thỏa 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. J Ví dụ 7.3. Cho {un} là dãy các số tự nhiên tăng dần: u1 < u2 < u3 < . . . và thỏa mãn điều kiện u1 = 1, un+1 ≤ 2n, với mọi n là số tự nhiê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, . . . , 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 ta chia tập hợp này ra làm 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ý Đirichlê 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 ta có up − uq = n. J Ví dụ 7.4. Cho {uk}, k = 1, 2, . . . , n là dãy số tự nhiên sao cho 1 ≤ u1 ≤ u2 ≤ . . . ≤ un và u1 + u2 + · · · + un = 2n 66 Chương 7. Bài tập dẫy số nâng cao 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 + · · · + uk, k = 1, 2, 3, . . . , n. Xét n + 2 số {0, u1 − un, S1, S2, . . . , Sn} Theo nguyên lý Đirichlê thì ít nhất hai số khi chia cho n có 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 + · · · + um = 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 un = 1. Mặt khác 1 ≤ u1 ≤ u2 ≤ . . . ≤ un vậy thì u2 = u3 = . . . = un−1 = 1. 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 = n 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, 2, . . . , 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 là ui+1 + ui+2 + · · · + uj = n. 3) Si chia hết cho n. 7.1. Ví dụ 67 Ta có 1 ≤ Si ≤ Sn−1 = 2n − un < 2n 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 =⇒ (u2 + u3 + · · · + uk + un)|n. Mà u2 + u3 + · · · + uk + un ≤ 2n − u1 < 2n. Suy ra u2 + u3 + · · · + uk + un = n. Tóm lại luôn luôn chọn được dãy con mà tổng của chúng bằng n. J Ví dụ 7.5. 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, . . . , ukmtrong đó 1 ≤ k1 < k2 < . . . < km ≤ n sao cho u2k1+ u2k2+ · · · + u2kmchia hết cho n. Lời giải. Xét (n + 1) số 0, u21, u21 + u22, u21 + u22 + u23, . . . , u21 + u22 + · · · + u2n Chia các số này cho n, thì chúng cho nhiều nhất n số dư. Theo nguyên lý Đirichlê tồn tại hai số cho cùng số dư, giả sử đó là u21 + u22 + · · · + u2jvà u21 + u22 + · · · + u2k(0 ≤ j < k ≤ n). Có nghĩa là số (u21 + u22 + · · · + u2j) − (u21 + u22 + · · · + u2k) chia hết cho n. Hoặc là uj+1 + uj+2 + · · · + uk chia hết cho n. Dãy con phải tìm là uj+1, uj+2, . . . , uk. J Ví dụ 7.6. Cho dãy Fibonaxi 1, 2, 3, 5, 8,. . . .Đặt f(n) = 19852 + 1956n2 + 1960 Chứng minh rằng tồn tại vô hạn số hạng uk của dãy Fibonaxi, sao cho f(uk)|1989 Lời giải. Đặt h(n) = 4n2 + 33n + 29 =⇒ h(n) = 1989(n2 + n + 1) − f(n). Từ đó suy ra f(n)|1989 ⇐⇒ h(n)|1989. 68 Chương 7. Bài tập dẫy số nâng cao Xét dãy số {vn} sau đây, trong đó v0 = −1, v1 = 1 vn+1 = vn + vn+1, n = 1, 2, . . . Nói cách khác dãy {vn} là dãy sinh ra bởi dãy Fibonaxi {un} : 1, 1, 2, 3, 5, . . . bằng cách thêm vào trước dãy này ba số hạng -1, 1, 0. Gọi rilà phần dư trong phép chia vi cho 1989(i = 0, 1, 2, . . .). Như vậy ta có 0 ≤ r ≤ 1988. Xét dãy các cặp số sau đây (r0,r1),(r1,r2),(r2,r3), . . . . Vì mỗi cặp ri chỉ nhận một trong 1989 giá trị, vậy số các cặp khác nhau tối đa là 19892. Từ đó theo nguyên lý Đirichlê thì trong 19892 + 1 cặp đầu tiên ít nhất có hai cặp trùng nhau. Giả sử hai cặp ấy là (rp,rp+1),(rp+q,rp+q+1), p, q ∈ N Điều ấy có nghĩa là rp = rp+1,rp+q = rp+q+1. Theo cách xác định dãy, ta có vp−1 = vp+1 − vp =⇒ rp−1 = rp+1 − rp Tươngtự, ta có vp+q−1 = vp+q+1 − vp+q =⇒ rp+q−1 = rp+q+1 − rp+q Từ đó suy ra rp−1 = rp+q−1. Tươngtự, ta có rp−2 = rp+q−2 . . . . . . . r2 = rq+2 r1 = rq+1 r0 = rq Từ r0 = rq, r1 = rq+1 và vn+1 = vn + vn+1 suy ra ri = ri+q, ∀i = 0, 1, 2, . . .. Do vậy r0 = rq = r2q = r3q = . . . = rkq, ∀k ≥ 1, suy 7.1. Ví dụ 69 ra h(vkq) = 1989.A + h(−1) = 1989.A. Nhưng ∀k = 1, 2, 3 . . . vkq đều là số Fibonaxi suy ra có vô số số hạng vkq của dãy Fibonaxi mà f(vkq)|1989. J Ví dụ 7.7. Cho dãy số {un} xác định như sau u1 = 20, u2 = 100, và un+1 = 4un + 5un−1 − 1976, n = 1, 2, . . . Chứng minh rằng tồn tại ít nhất một số của dãy số chia hết cho 1996. Lời giải. Đặt un = 1996pn + qn, ∀n = 1, 2, . . . trong đó pn, qn là các số nguyên và 0 ≤ qn ≤ 1995. Xét dãy số (q1, q2),(q2, q3), . . . ,(qn, qn+1), . . . Vì dãy này vô hạn mà số các số qilà hữu hạn nên tồn tại hai số tự nhiên l, m ( giả sử m > l) sao cho (ql, ql+1) = (qm, qm+1) hiểu theo nghĩa ql = qm và ql+1 = qm+1. Chúng ta sẽ chứng minh rằng ql−1 = qm−1. Thật vậy, 5(um−1 − ul−1) = (um+1 − 4um + 1976) − (ul+1 − 4ul + 1976) = (um+1 − ul+1) − 4(um − ul) (7.7) Do uk = 1996pk + qk, nên từ (7.7) có 5(um−1 − ul−1) = 1996(pm+1 − pl+1) − (qm+1 − ql+1)− − 4[1996(pm − pl) − (qm − ql)] (7.8) Thay những giá trị bằng nhau vào ((7.8) ta đi đến 5(um−1 − ul−1) = 1996[(pm+1 − pl+1) − 4(qm − ql)] (7.9) Từ (7.9) suy ra 5(um−1 − ul−1)|1996, mà (5, 1996) = 1 =⇒ (um−1 − ul−1)|1996 =⇒ 1996(pm−1 − pl−1) + (qm−1 − ql−1)|1996 =⇒ (qm−1 − ql−1)|1996. (7.10) 70 Chương 7. Bài tập dẫy số nâng cao Do 0 ≤ qm−1 ≤ 1995, 0 ≤ ql−1 ≤ 1995 =⇒ −1995 ≤ qm−1 − ql−1 ≤ 1995 (7.11) Từ (7.10) và (7.11) suy ra (qm−1 − ql−1) = 0 hay qm−1 = ql−1. Tương tự chúng ta cũng có thể đi đến qm−2 = ql−2 và cứ tiếp tục như thế đi đến q2 = q2 + (m − 1) và q1 = q1 + (m − l) (7.12) Ta chứng minh rằng um−l chính là số hạng của dãy mà chia hết cho 1996. Thật vậy theo cách xác định dãy, ta có 5um−l = um−l+2 − 4um−l+1 + 1976 = 1996pm−l+2 + qm−l+2 − 4(1996pm−l+1 + qm−l+1) + 1996 = 1996(pm−l+2 + 4pm+l+1) + (qm−l+2 + 4qm−l+1) + 1996 Thay (7.12) vào đẳng thức trên ta có 5um−l = 1996(pm−l+2 − 4pm−l+1) + (q2 − 4q1) + 1996. (7.13) Do u1 = 20 =⇒ u1 = 0.1996 + 20 =⇒ q1 = 20 u2 = 100 =⇒ u2 = 0.1996 + 100 =⇒ q2 = 100 Vậy từ (7.13) suy ra 5um−l = 1996(pm−l+2 − 4pm−l+1) + 1996. (7.14) Do pm−l+2 và pm−l+1là số nguyên, vậy từ (7.14) suy ra 5um−l|1996 mà (5, 1996) = 1 suy ra um−l|1996. J Ví dụ 7.8. Cho dãy số tự nhiên u1, u2, . . . , un+1 sao cho 1 ≤ u1 < u2 < . . . < un+1 ≤ 2n . Chứng minh rằng tồn tại hai số tự nhiên i và j sao cho uj chia hết cho ui,(j > i). Lời giải. Ký hiệu vilà ước số lẻ lớn nhất của uitương ứng, nghĩa là ui = 2pi.vi, với vilẻ và số tự nhiên pi nào đó (i = 1, 2, . . . , n + 1). 7.1. Ví dụ 71 Do 1 ≤ u1 < u2 < . . . < un+1 ≤ 2n suy ra với mọi i = 1, 2, . . . , n + 1 ta có vi < 2n . Xét (n + 1) số lẻ v1, v2, . . . , vn+1. Các số lẻ này đều dương và nhỏ hơn 2n. nên số lượng của chúng bằng n. Vậy theo nguyên lý Đirichlê tồn tại hai số i, j sao cho 1 ≤ i < j ≤ n + 1 mà vi = vj. Theo cách đặt trên thì ui = 2pivi và uj = 2pjvj. Nhưng ui < uj suy ra 2pivi < 2pjvj, mà vi = vj. Suy ra 2pi < 2pj. Do pi, pjlà các số nguyên dương nên 2pj chia hết cho 2pi. Nghĩa là uj chia hết cho ui. J Ví dụ 7.9. (Đề thi Toán Olympic Quốc tế lần thứ 13) Dãy số {un}, n = 2, 3, 4, . . . xác định như sau un = 2n − 3. Chứng minh rằng dãy số này chứa một tập vô hạn các phần tử, sao cho bất kỳ hai số nào của tập hợp này cũng nguyên tố cùng nhau. Lời giải. Ta chứng minh bằng quy nạp. Giả thiết đã xây dựng được k phần tử của dãy u1 = 2n1 − 3, u2 = 2n2 − 3, . . . , uk = 2nk − 3 mà với mọi i 6= j, thì (uj, ui) = 1, với 1 ≤ i, j ≤ k, ở đây 2 = n1 < n2 < . . . < nk. Chúng ta sẽ xây dựng số uk+1 = 2nk+1 − 3 nguyên tố cùng nhau với các số u1, u2, . . . , uk bằng cách sau đây: Đặt l = u1.u2 . . . uk. Xét (l + 1) số 20, 21, . . . 2l Khi chia các số này cho l ta được một tập hợp gồm l số dư. Vậy theo nguyên lý Đirichlê có ít nhất hai số cho ta cùng phần dư. Giả sử hai số đó là 2r và 2s,(s > r). Bây giờ chọn số p sao cho pl = 2r − 2s = 2s(2r−s − 1). Do l là số lẻ nên 2s không chia hết cho l . Mặt khác (2r, 2r−s) = 1 suy ra (2r−s − 1) chia hết cho l. Điều này nghĩa là tồn tại số tự nhiên q sao cho 2r−s − 1 = ql, suy ra 2r−s+2 − 3 = 4.2r−s − 3 = 4(ql + 1) − 3 = 4ql + 1. 72 Chương 7. Bài tập dẫy số nâng cao Đặt uk+1 = 2r−s+2 − 3 = ql. Do uk+1 = 4ql + 1 và l = u1.u2 . . . uk, suy ra uk+1 > uk. Do uk+1 = 4ql + 1, suy ra (uk+1, 1) = 1. Do đó (uk+1, ui) = 1 với mọi i = 1, 2, . . . , k. Như vậy khi đã xây dựng được dãy con u1, u2, . . . , ukthỏa mãn điều kiện đầu bài, thì sẽ xây dượng được dãy con mới u1, u2, . . . , uk, uk+1 cũng có tính chất ấy. Theo nguyên lý qui nạp chúng ta xây dựng được dãy con vô hạn u1, u2, . . . , un, . . . . của dãy đã cho có tính chất: Bất cứ cặp phần tử nào của dãy con ấy cũng nguyên tố cùng nhau. J Ví dụ 7.10. Cho u1 và u2 là hai số nguyên dương nguyên tố cùng nhau. Dãy số {un} xác định với u1, u2 là hai số hạng đầu tiên, còn khi n = 2, 3, . . . ta xác định un+1 = unun−1 + 1 Chứng minh rằng với mọi i > 1 tồn tại j > i sao cho uj chia hết cho ui. Lời giải. Lấy i > 1 tùy ý, và p là ước số nguyên tố của ui. Xây dựng dãy số {vn} như sau 0 ≤ vn ≤ p − 1 vn ≡ un (mod p) Ta cũng có vn+1 = vnvn−1 + 1 (mod p), ∀n = 2, 3 . . . Vì các cặp (vn, vn−1) là vô hạn, mà vn chỉ nhận hữu hạn giá trị suy ra {vn} phải là dãy tuần hoàn từ một lúc nào đó. Ta cần chứng minh rằng tồn tại số nguyên dương kp > 0 sao cho vi+kp = 0. (7.15) Xét hai khả năng sau 7.1. Ví dụ 73 1) Giả sử dãy {vn} tuần hoàn từ vs với chu kỳ T, trong đó s > i. Ta có vs+1 = vsvs−1 + 1 = vs+T+1 = vs+Tvs+T−1 + 1 (mod p) vsvs−1 = vs+Tvs+T−1 (mod p). (7.16) a) Nếu vs = vs+T ≡ 0 (mod p), thì vs = vs+T = 0, do 0 ≤ vn ≤ p − 1, ∀n. Khi đó chỉ việc chọn kp = s − i, Suy ra vi+kp = vs = 0, vậy (7.15) đúng. b) Nếu vs = vs+T 6= 0, thì từ (7.16) có vs−1 = vs+T−1. Suy ra {vn} tuần hoàn không phải bắt đầu từ vs điều này mâu thuẫn với cách chọn s.Khả năng này không xẩy ra. Tóm lại hệ thức (7.15) đúng trong trường hợp 1). 2) Nếu s ≤ i thì hệ thức (7.15) hiển nhiên đúng. Ta có vi+1 ≡ ui+1 (mod p) ≡ uiui−1 + 1 (mod p) vậy vi ≡ ui (mod p) nhưng do p là ước nguyên tố của ui suy ra vi ≡ 0 (mod p), như vậy vi+1 ≡ 1 (mod p) hay là vi+1 = 1. Tươngtự, do vi+kp = 0 suy ra vi+kp+1 = 1. Như vậy suy ra {vn} cũng tuần hoàn với chu kỳ kp tức là với mọi l nguyên dương, ta có vi+l.kp = 0. (7.17) Nghĩa là ui+l.kpchia hết cho p. Như vậy với mọi ước nguyên tố p của uita xây dựng được số kp sao cho (7.17) đúng. Gọi m là bội số chung nhỏ nhất của tất cả các số kp, theo (7.3) suy ra vi+lm = 0 với mọi l nguyên dương. Suy ra ui+lm chia hết cho tất cả các ước số nguyên tố của ui. Tức là ui+lm chia hết cho ui với mọi số nguyên dương l. Lấy j = i + lm, ta có điều phải chứng minh. J 74 Chương 7. Bài tập dẫy số nâng cao 7.2. BÀI TẬP . 7.11. Nếu ba số nguyên tố thực sự lớn hơn 3 lập thành một cấp số cộng thì công sai của chúng chia hết cho 6. . 7.12. cho f(n) là hàm xác định trên tập các số nguyên dương như sau: nếu n = a1a2 . . . ak, thì f(n) = (a1 + a2 + · · · + ak)1998. Với mỗi số nguyên dương n, lập dãy vô hạn ui(n), i = 1, 2, . . . như sau ui(n) = f(f(. . . f(n)i lần f | {z } Chứng minh rằng với mọi n nguyên dương, tồn tại p sao cho dãy ui(n), i = p, p + 1, . . . là dãy tuần hoàn. . 7.13. Cho u1, u2, . . . , un là dãy số tùy ý gồm n số hạng. Chứng minh rằng luôn luôn trích được một dãy con sao cho nếu gọi S là tổng các phần tử của dãy con ấy, thì S khác với số nguyên gần nhất một lượng không vượt quá 1 n + 1. . 7.14. Chứng minh rằng nếu những số nguyên a và m nguyên tố cùng nhau, thì tồn tại một số tự nhiên n mà tích na chia cho m cho số dư 1. CHƯƠNG 8 SỐ THỰC VỚI TẬP TRÙ MẬT 8.1. Tập trù mật . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.2. Ví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 8.3. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.1. TẬP TRÙ MẬT Trên đường thẳng thực chúng ta thường quan tâm tới khái niệm một khoảng (một đoạn thẳng), ta có thể hiểu một khoảng trên đường thẳng thực là tập hợp tất cả các số thực nằm giữa hai điểm đã cho. Như vậy hai điểm để xác định một khoảng có thể nằm trong hoặc nằm ngoài khoảng đó ; đây là xuất phát của khái niệm đóng, mở,.. ở ngành giải tích, giải tích hàm trong toán học cao cấp. Nhưng ở đây ta không quan tâm điều đó, mà chỉ quan tâm tới các khái niệm sau đây với quan điểm kiến thức sơ cấp. Với a, b là số thực, ký hiệu [a,b] là khoảng được tính cả hai điểm đầu a, b và gọi là khoảng đóng. Khoảng mở được ký hiệu là (a, b), không lấy hai điểm đầu a, b. Ngoài ra ta còn xét khoảng nửa đóng (nửa mở ) do việc ta chỉ lấy một trong hai điểm đầu a hoặc b,ví dụ như [a, b) hoặc (a, b]. Một khoảng trong tập số thực gọi là suy thoái nếu nó chỉ là một điểm (tức là khi hai điểm đầu trùng nhau). 76 Chương 8. Số thực với tập trù mật Một tập hợp A của số thực gọi là trù mật, nếu mọi khoảng không suy thoái đều chứa một số phần tử của A. Một ví dụ dễ thấy là tập hợp số hữu tỷ gồm các số có thể biểu diễn như một thương của hai số nguyên và tập hợp số vô tỷ gồm nhứng số không phải là số hữu tỷ đều là những tập trù mật trong tập số thực. Người ta còn mở rộng khái niệm trù mật cho một khoảng trên đường thẳng thực. Cho ∆ là một khoảng bất kỳ trên đường thẳng thực. Chúng ta gọi tập hợp B gồm những số thực là trù mật trong ∆, nếu với mọi khoảng con không suy thoái của ∆ đều chứa những phần tử của B. Rõ ràng tập hợp các số hữu tỷ trù mật trong mọi khoảng; và tập hợp các số vô tỷ cũng có tính chất ấy. Những ký hiệu hay được dùng: với mọi số thực x, ký hiệu [x] là số nguyên lớn nhất không vượt quá x, {x} là số x − [x]; [x] và {x} gọi là phần nguyên và phần thập phân của số x. Từ định nghĩa có thể thấy ngay 0 ≤ x − [x] < 1. Để hiểu rõ hơn khái niệm trù mật trong phần này ta xét một loạt bài toán có liên quan và cách sử dụng nguyên lý Đirichlê để chứng minh đinh lý cơ bản Kronecker. 8.2. VÍ DỤ Ví dụ 8.1. Nếu một tập hợp A của số thực là trù mật và r là số thực khác không, thì tập hợp gồm tất cả tích số {ra} với a chạy trong A cũng là tập trù mật. Lời giải. Có hai trường hợp xẩy ra: r > 0 và r < 0. Vì cách chứng minh hoàn toàn tương tự nên ta chỉ xét trường hợp đầu. Cho x và y là hai số thực và x < y. Khi đó xr 0. Không ảnh hưởng đến kết quả chứng minh có thể giả thiết e < 1. Ngoài ra ta có thể chọn số tự nhiên k sao cho k ≥eα. Từ 8.1 và 8.2 suy ra tập các số kpα + kq với p và q là các số nguyên bất kỳ, là tập trù mật. Nghĩa là tồn tại các số nguyên p và q thỏa mãn 0 < kpα + kq < e. (8.1) Chúng ta sẽ chỉ ra rằng giữa những cặp số nguyên (p, q) trong (8.1) có những cặp mà p > 0. Thật vậy, trường hợp p = 0 không thể xẩy ra vì từ (8.1) suy ra 0 < kq < e, mâu thuẫn với điều ta đã biết là kq là số nguyên và e < 1. Do vậy chỉ còn phải chứng minh cho trường hợp p < 0. Trong trường hợp này số có dạng kpsα + kqt với s, t là những số nguyên bất kỳ, tạo thành tập trù mật. Từ (8.1) suy ra tồn tại số nguyên s và t sao cho 0 < kpsα + kqt < kpα + kq. (8.2) Nếu s < 0, thì kps > 0 và chứng minh lại đúng. Vì thế ta chỉ xét s ≥ 0. Từ (8.1) và (8.2) suy ra 0 < kp(1 − s)α + kq − kpt < e. (8.3) Vì với s = 0 bất đẳng thức (8.2) không thể xẩy ra, nên s > 0. Nhưng bởi vì s là số nguyên, thì từ s > 0 suy ra s ≥ 1. Tại vì ((8.3) không thể xẩy ra với s = 1, từ bất đẳng thức cuối cùng lại suy ra s > 1. Như vậy kp(1 − s) > 0. Điều đó có nghĩa là tồn tại các số nguyên p và q thỏa mãn (8.1) và p > 0. Từ (8.1) suy ra kq < e − kpα < e − peαα = e(1 − p) ≤ 0 Vậy kq < 0. Theo cách này (8.1) được đưa về dạng 0 < mα − n < e, ở đây m và n là những số tự nhiên. Bởi vì e là độ dài của∆, từ bất đẳng thức cuối cùng suy ra một ước số nào đó của mα − n, cũng có 8.2. Ví dụ 79 dạng này, sẽ nằm trong ∆. Tương tự cũng chứng minh được khi ∆ nằm ở bên trái số không. J Ví dụ 8.4. Cho α là số vô tỷ bất kỳ. Khi đó tập hợp những số dạng {αn}, với n là số tự nhiên bất kỳ, là tập trù mật trong khoảng (0,1). Lời giải. Cần phải chứng minh rằng mọi khoảng con không suy biến (a, b) của (0,1) chứa số có dạng {αn} với một số tự nhiên n nào đó. Chúng ta chứng minh cho trường hợp khi α là một số dương. Theo bài 8.3 những số có dạng nα − m với n, m là các số tự nhiên, tạo thành tập trù mật. Nghĩa là tồn tại những số tự nhiên m và n thỏa mãn 0 ≤ a < nα − m < b < 1. Nhưng từ định nghĩa [αn] suy ra 0 ≤ nα − [nα] < 1. Chúng ta nhận được hiệu hai số nguyên m và [nα] thỏa mãn −1 < m − [nαm] < 1, điều này chỉ xẩy ra khi m − [nαm] = 0, do đó m = [nα]. Từ (8.1) chỉ ra rằng số {nα} = nα − [nα] nằm trong khoảng (a, b). Với α > 0, chúng ta đã chứng minh xong. Trường hợp α < 0. Khi đó −α > 0 và từ Ví dụ 8.3 suy ra tồn tại những số tự nhiên m và n, thỏa mãn −1 ≤ −b < n(−α) − m < −a ≤ 0. Nhân các vế với -1 chúng ta nhận được 0 ≤ a < nα − m < b ≤ 1. Như vậy dễ dàng tính ra m = −[nα] và {nα} nằm trong khoảng (a, b). J Ví dụ 8.5. Tập hợp tất cả các số dạng {log n} với n là số tự nhiên bất kỳ là tập trù mật trong (0,1). Lời giải. Chúng ta có thể chứng minh mở rộng hơn một chút: tập hợp các số dạng {n log 2} với n là số tự nhiên bất kỳ, là tập trù mật trong (0,1). 80 Chương 8. Số thực với tập trù mật Để đạt mục đích này chúng ta chứng minh log 2 là một số vô tỷ. Thật vậy, trong trường hợp ngược lại thì tồn tại hai số tự nhiên p p và q, mà log 2 =pq, nghĩa là 2 = 10 q. Lũy thừa đẳng thức cuối cùng với q chúng ta nhận được 2q = 2p.5p. Điều này trái định lý cơ bản của số học về việc phân tích ra thừa số nguyên tố. Như vậy log 2 thực sự là một số vô tỷ. Áp dụng 8.4 suy ra tập các số có dạng {n log 2} là trù mật trong (0,1). Mặt khác, theo tính chất của logarit, log 2n = n log 2 với mọi n = 1, 2, . . . J Ví dụ 8.6. Cho m là số nguyên, n là số nguyên không âm. Tập hợp tất cả các số có dạng m2nlà tập trù mật. Lời giải. Do các bài toán trên, chúng ta chỉ cần chứng minh rằng tập hợp số dạng 3m 2nvới m, n là những số nguyên dương, là trù mật trong khoảng (0, +∞). Điều đó có nghĩa là với mọi cặp số dương a, b(a < b) tồn tại những số tự nhiên m và n thỏa mãn a <3m 2n < b. Sau khi logarit hóa cặp bất đẳng thức này theo cơ số 2, chúng ta nhận được cặp bất đẳng thức tương đương log2a < m log23 − n < log2b. Cách chứng minh tương tự như Ví dụ 8.5 cho thấy log23 là vô tỷ. Khi đó định lý Kronecker chỉ ra rằng trong đoạn (log2a, log2b) chứa số có dạng {m log23 − n}. J Ví dụ 8.7. Tập hợp tất cả các số hạng của dãy xác định bằng công thức xn =n 10[log n]+1, n = 1, 2, 3 . . ., là trù mật trong khoảng 1 10, 1 .