"Giải toán bằng phương pháp đại lượng cực biên 🔙 Quay lại trang tải sách pdf ebook Giải toán bằng phương pháp đại lượng cực biên Ebooks Nhóm Zalo NGUYỄN HỮU ĐIỂN GIẢI TOÁN BẰNG PHƯƠNG PHÁP ĐẠI LƯỢNG CỰC BIÊN (Tái bản lần thứ nhất) NHÀ XUẤT BẢN GIÁO DỤC LỜI NÓI ĐẦU Trong cuốn sách Những phương pháp điển hình trong giải toán phổ thông [13] của tác giả có đề cập đến phương pháp phần tử cực biên. Phương pháp này đã lợi dụng phần tử gọi là đại lượng cực biên theo một nghĩa nào đó như nhỏ nhất, lớn nhất, các điểm đầu của đoạn thẳng, phần tử nằm ở ranh giới giữa phần trong và phần ngoài một tập, ... Nội dung cuốn sách Giải toán bằng phương pháp đại lượng cực biên khảo sát rất kĩ những kĩ thuật và cách sử dụng đại lượng cực biên để giải toán. Rất nhiều bài toán mới được giải bằng phương pháp đại lượng cực biên. Một số tài liệu trong nước gọi phương pháp này là phương pháp cực hạn. Để thể hiện bản chất của phương pháp, tác giả gọi nó là phương pháp đại lượng cực biên. Bởi vì khi giải bài toán, ta đã dùng đại lượng cực biên làm mấu chốt cho xuất phát và lý luận. Mặt khác, đại lượng cực biên trong mỗi bài toán cụ thể là khác nhau, nhưng có tính chất chung là các phần tử này nằm giữa miền xác định và miền không xác định của bài toán theo một nghĩa nào đó. Nguyên lý thứ tự của số học là mấu chốt của phương pháp đại lượng cực biên. Ngay từ Chương một, ta sẽ thấy những bài toán giải được bằng phương pháp quy nạp thì đều giải được bằng phương pháp đại lượng cực biên thông qua nguyên lý thứ tự. Như vậy, ta thấy ngay được hai cách giải loại bài toán này là phương pháp quy nạp toán học và phương pháp dùng nguyên lý thứ tự. Trong phần này các bạn sẽ thấy mối liên kết giữa hai nguyên lý chặt chẽ như thế 3 4 Lời nói đầu nào. Chương hai trình bày các kĩ thuật chứng minh hoặc tính toán sử dụng phương pháp đại lượng cực biên, nhất là dùng lý luận phản chứng với đại lượng cực biên, sắp xếp thứ tự các phần tử, ... Những kĩ thuật này được áp dụng rất nhiều cho các chương sau. Chuyên đề của chương này là đưa thứ tự vào cho một tập hợp bất kì chứ không phải chỉ là tập hợp số nguyên. Điều quan trọng là sắp xếp như thế nào để thể hiện nguyên lý thứ tự và sử dụng giải bài toán. Chương ba ứng dụng phương pháp đại lượng cực biên vào hình học với các đại lượng cực biên đa dạng như số đo góc, độ dài cạnh, ... Rất nhiều bài toán hình học không thể giải bằng cách khác hay hơn. Chuyên đề của chương này là bài toán Sylvester-Gallai và những mở rộng của nó. Chương bốn lại là ứng dụng phương pháp đại lượng cực biên vào số học và đại số với đại lượng cực biên là số nhỏ nhất và lớn nhất. Đặc biệt, chuyên đề quan trọng là phương pháp xuống thang trong số học, phương pháp này đã có lịch sử từ thời Fermat. Chương năm về giải tích liên quan tới các định lý nổi tiếng như: định lý giá trị trung bình, định lý giá trị trung gian, định lý Rolle,... cho các hàm liên tục xác định trên một đoạn, mà giá trị hàm số tại hai đầu mút quyết định nội dung định lý. Từ những định lý cơ bản này, rất nhiều bài toán được giải cũng chỉ cần sử dụng giá trị hai đầu mút của đoạn thẳng là đủ... Chương sáu về hàm lồi và tính chất của hàm lồi đạt giá trị lớn nhất và giá trị nhỏ nhất tại các điểm cực biên trên miền xác định của nó. Cụ thể, nếu hàm lồi xác định trên đoạn thẳng hoặc miền đa giác, thì nó đạt cực trị tại hai đầu đoạn thẳng hoặc tại các đỉnh của đa giác. Hàng loạt bài toán dùng đại lượng cực biên của hàm lồi để giải một cách rất lý thú. Cuốn sách dành cho học sinh phổ thông yêu toán, học sinh khá giỏi môn toán, các thầy cô giáo, sinh viên đại học ngành toán, ngành Lời nói đầu 5 tin học và những người yêu thích toán học phổ thông. Trong biên soạn, chúng tôi không thể tránh khỏi sai sót và nhầm lẫn, rất mong bạn đọc cho ý kiến. Mọi góp ý gửi về địa chỉ: Ban biên tập sách Toán, Nhà xuất bản Giáo dục tại Hà Nội, 187B Giảng Võ, Hà Nội. Tác giả cảm ơn ban biên tập Toán - Nhà xuất bản Giáo dục Hà Nội đã hết sức giúp đỡ để cuốn sách được in ra. Tác giả đặc biệt cảm ơn biên tập viên, TS. Phạm Thị Bạch Ngọc đã đọc kĩ bản thảo và bổ sung rất nhiều ý kiến có giá trị để hoàn thiện cuốn sách. Hà Nội, ngày 2 tháng 9 năm 2005 Nguyễn Hữu Điển NHỮNG KÝ HIỆU Trong cuốn sách này ta dùng những ký hiệu với các ý nghĩa xác định trong bảng dưới đây: N tập hợp số tự nhiên N∗tập hợp số tự nhiên khác 0 Z tập hợp số nguyên Q tập hợp số hữu tỉ R tập hợp số thực C tập hợp số phức ≡ dấu đồng dư ∞ dương vô cùng (tương đương với +∞) −∞ âm vô cùng /0 tập hợp rỗng Ckm tổ hợp chập k của m phần tử ... chia hết 6... không chia hết UCLN ước số chung lớn nhất BCNN bội số chung nhỏ nhất deg bậc của đa thức J Kết thúc chứng minh IMO International Mathematics Olympiad APMO Asian Pacific Mathematics Olympiad 6 CHƯƠNG 1 NGUYÊN LÝ THỨ TỰ TRONG TẬP SỐ TỰ NHIÊN 1.1. Nguyên lý thứ tự . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2. Nguyên lý quy nạp toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3. Sự tương đương giữa hai nguyên lý. . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ. . . . . . . . . . . . . . . . . . . . . . . 29 1.4.1. Thứ tự của một tập hợp bất kì . . . . . . . . . . . . . . . 30 1.4.2. Tập hợp sắp thứ tự đầy đủ và ứng dụng . . . . . . 35 1.5. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Chương này nhắc lại những khái niệm khởi đầu của lý thuyết số. Tập hợp số tự nhiên, các phép toán của nó và một thứ tự thông thường trong nó. Trọng tâm là nguyên lý thứ tự và những ứng dụng của nó, liên quan đến vấn đề này ta xét nguyên lý quy nạp toán học, phương pháp phản chứng với nguyên lý thứ tự. 8 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên 1.1. NGUYÊN LÝ THỨ TỰ Tập hợp số N = {0,1,2,3,4,...} được gọi là tập hợp số tự nhiên. Mỗi phần tử của nó được gọi là một số tự nhiên. Tập hợp số tự nhiên thường gắn với hai phép toán cộng và nhân. Với những số tự nhiên a,b và c, các phép toán trên có những tính chất sau: 1. a+b và ab cũng là số tự nhiên (tính đóng). 2. (a+b) +c = a+ (b+c) và a(bc) = (ab)c (tính kết hợp). 3. a(b+c) = ab+ac (tính phân phối). 4. 0+a = a+0 (đơn vị cộng tính). 5. 1a = a1 = a (đơn vị nhân tính). Người ta còn xét thứ tự < (nhỏ hơn) thường dùng trong tập số tự nhiên: 0 < 1 < 2 < 3 < ... Thứ tự này có tính chất sau: Nếu a,b và c là những số tự nhiên khác nhau, thì (1) hoặc là a < b hoặc là b < a, nhưng không đồng thời có cả hai bất đẳng thức này; (2) nếu a < b và b < c thì a < c. Người ta công nhận một tính chất quan trọng trong tập số tự nhiên như một tiên đề cơ sở: Nguyên lý thứ tự: Mọi tập con khác rỗng những số tự nhiên luôn có phần tử nhỏ nhất. Ví dụ: Cho tập hợp S được định nghĩa như sau: S = {x|x là tích của những số nguyên dương chẵn khác nhau }. Ta có thể viết cụ thể tập hợp này S = {8,12,16,20,24,...}. Ta thấy rằng tập hợp S thực sự có phần tử nhỏ nhất là 8. Nguyên lý thứ tự đúng cho tập hợp số tự nhiên N nhưng không 1.1. Nguyên lý thứ tự 9 đúng cho tập số nguyên được định nghĩa và ký hiệu như sau: Z = {...,−3,−2,−1,0,1,2,3,....} Với thứ tự < thì tập con khác rỗng những số nguyên âm không có phần tử nhỏ nhất. Định lý 1.1. Cho tập hợp khác rỗng những số tự nhiên S = {x1, x2, x3,...} sao cho x1 > x2 > x3 > .... Khi đó S là tập hợp hữu hạn. Chứng minh. Theo giả thiết S là tập hợp khác rỗng. Giả sử S là tập vô hạn. Từ x1 > x2 > x3 > ... (theo giả thiết), suy ra S không có phần tử nhỏ nhất. Điều này trái với nguyên lý thứ tự. Do đó S là tập hợp hữu hạn. J Phần sau đây ta sử dụng nguyên lý thứ tự để giải toán gọi là phương pháp đại lượng cực biên. Trước khi xét một số ví dụ sử dụng phương pháp này để giải toán, ta nhắc lại những loại số khác cần thiết. Số hữu tỉ là số mà nó có thể biểu diễn dưới dạng ab, ở đây a,b là hai số nguyên và b 6= 0. Ký hiệu tập số này là Q. Số vô tỉ là số mà nó không thể biểu diễn dưới dạng tỉ số của hai số nguyên và ký hiệu tập hợp số này là I. Tập hợp các số hữu tỉ và số vô tỉ được gọi là tập số thực và ký hiệu là R. Dễ dàng thấy mối quan hệ sau đây N ⊂ Z ⊂ Q ⊂ R. Bài toán 1.1. Chứng minh rằng √2 là số vô tỉ. Lời giải. Chứng minh theo phản chứng. Giả sử √2 là một số hữu tỉ, nghĩa là √2 =abvới a,b là các số nguyên dương và b 6= 0. Điều này suy ra tập hợp S = {n√2 | đồng thời n và n√2 là những số nguyên dương} 10 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên là tập hợp khác rỗng (vì nó chứa a). Theo nguyên lý thứ tự, S có phần tử nhỏ nhất, gọi nó là j = k√2, k ∈ N∗. Vì √2−1 > 0 nên j(√2−1) = j√2−k√2 = (j −k)√2 là một số nguyên dương. Từ 2 < 2√2 và j√2 = 2k, ta suy ra (j −k)√2 = k(2−√2) < k√2 = j. Như vậy (j −k)√2 là một số nguyên dương trong S , mà nó lại nhỏ hơn cả số nhỏ nhất j. Điều này vô lý với cách chọn j. Suy ra điều cần chứng minh. J Bài toán 1.2. Cho những số nguyên không âm a (a 6= 0) và b. Chứng minh rằng tồn tại những số nguyên q (q ≥ 0) và r (0 ≤ r < a) sao cho b = aq+r. Lời giải. Ký hiệu S = {b−ax|x ≥ 0,b−ax ≥ 0}. Vì b = b−a.0 nằm trong S , nên tập S khác rỗng gồm những số nguyên không âm. Như vậy S có phần tử nhỏ nhất r. Ta sẽ chỉ ra rằng r thoả mãn những điều kiện của bài toán. Vì r thuộc S nên r ≥ 0 và r = b−aq với số q ≥ 0. Ta phải chỉ ra rằng r < a. Bây giờ r − a = b − qa − a = b − a(q + 1). Như vậy nếu r ≥ a, thì r − a = b − a(q + 1) ≥ 0 sẽ nằm trong S . Nhưng r −a < r và r là phần tử nhỏ nhất của S . Như vậy r −a không thể lớn hơn hoặc bằng 0. Vậy r −a < 0 hay r < a. Đó là điều cần chứng minh. J Bài toán 1.3. Cho a,b, c là những số nguyên sao cho a6 +2b6 = 4c6. Chứng minh rằng a = b = c = 0. Lời giải. Dễ thấy ta có thể chỉ cần chứng minh cho những số nguyên không âm là đủ. Ta chọn bộ ba số nguyên không âm a,b, c thỏa mãn điều kiện đầu bài đã cho và với max(a,b, c) > 0 có giá trị nhỏ nhất 1.1. Nguyên lý thứ tự 11 (điều này tồn tại vì theo nguyên lý thứ tự cho tập con khác rỗng các số tự nhiên). Nếu a6+2b6 = 4c6thì a phải là số chẵn, nghĩa là a = 2a1 với a1 là một số nguyên dương. Thay vào đẳng thức đã cho, ta nhận được 32a61+b6 = 2c6. Từ đây lại có b = 2b1 và suy ra 16a61+32b61 = c6. Như vậy ta lại có c = 2c1 và cuối cùng a61 +2b61 = 4c61. Vậy (a1,b1, c1) là bộ ba số nguyên không âm thỏa mãn đẳng thức đầu bài đã cho, mặt khác, ta có max(a1,b1, c1) < max(a,b, c). Điều này mâu thuẫn với cách chọn các số a,b, c. Suy ra max(a,b, c) = 0, nghĩa là a = b = c = 0. J Bài toán 1.4 (IMO 1988). Chứng minh rằng nếu a,b là những số 1+ablà một số nguyên thì a2 +b2 nguyên dương sao cho a2 +b2 chính phương. Lời giải. Giả sử số a2 +b2 1+ablà một số 1+ab= k là một số nguyên, nhưng không phải là số chính phương với max(a,b) nhỏ nhất (điều này tồn tại do tiên đề thứ tự). Không mất tính tổng quát ta có thể giả thiết rằng a ≤ b. Nếu a = b thì 0 < k =2a2 a2 +1< 2, từ đó suy ra k = 1 và nó là một số chính phương. Kết luận bài toán đúng. Xét trường hợp a < b: Ta xét a2 + b2 − k(ab + 1) = 0 là phương trình bậc hai theo biến b. Theo công thức Viète, tổng của hai nghiệm của phương trình đang xét là ka và tích của hai nghiệm là a2 −k. Ký hiệu b1,b2 là hai nghiệm nói trên thì b1 +b2 = ka và b1b2 = a2 −k. Vì a, k là những số nguyên dương và b1 thỏa mãn a2 +b21 −k(ab1 +1) = 0, nên ta có b1 ≥ 0. Nếu ngược lại thì b1 không thể là nghiệm của phương trình đang xét. Hơn nữa, nếu b1 = 0 thì a2 +02 = k(0.a+1), mà k không phải là 12 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên số chính phương, điều này vô lý. Như vậy b1 > 0 và b1 =a2 −k b2 0 vì 0 ∈ S . Vì k − 1 < k, theo cách chọn trên thì 1.2. Nguyên lý quy nạp toán học 13 k −1 ∈ S . Nhưng theo giả thiết thứ hai phải có k −1+1 cũng phải thuộc S . Vì thế k = k −1+1 cũng nằm trong tập S , điều này vô lý với cách chọn k. Suy ra S = N. J Từ định lý trên dễ dàng suy ra những hệ quả sau. Hệ quả 1.1. Nếu tập hợp S những số nguyên dương chứa số m và nó cũng chứa n + 1 mỗi khi nó chứa n với n ≥ m, thì S chứa tất cả những số nguyên dương lớn hơn hoặc bằng m. Chú ý: Để thuận tiện cho thể hiện các bài toán sau này và theo hệ quả trên ta ký hiệu N(m) = {m,m+1,...,n,...}. Ví dụ tập số nguyên dương bắt đầu từ 3 là N(3) = {3,4,5,...}. Ta ký hiệu N∗ = {1,2,...,n,...} là tập hợp các số nguyên dương. Hệ quả 1.2 (Nguyên lý quy nạp toán học mạnh). Nếu tập hợp S những số nguyên dương chứa số m và nó cũng chứa số n+1 mỗi khi nó chứa các số m,m+1,m+2,...,n với n ≥ m, thì S chứa tất cả các số nguyên dương lớn hơn hoặc bằng m. Chú ý: Nguyên lý quy nạp toán học được phát biểu khác với nguyên lý quy nạp ta thường dùng như trong [12], trong cuốn sách này tác giả đã đề cập tới mọi khía cạnh của việc dùng phương pháp quy nạp. Những ví dụ sau đây ứng dụng trực tiếp định lý trên và sau đó ta dẫn về dạng nguyên lý quy nạp quen thuộc. Bài toán 1.5. Chứng minh rằng A(n) = 7n +3n−1 chia hết cho 9, với mọi n ∈ N. Lời giải. Ta ký hiệu tập hợp S = {n | n ∈ N và A(n)... 9}. Ta sử dụng nguyên lý quy nạp để chứng minh, vậy ta kiểm tra các điều kiện giả thiết: 14 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên 1) Với n = 0, ta có A(0) = 0... 9. Vậy 0 ∈ S . 2) Giả sử n ∈ S , nghĩa là n ∈ N và A(n) = 7n +3n−1... 9 với n > 0. Ta xét n+1 ∈ N và A(n+1) = 7n+1 +3(n+1)−1 = 7.7n +3n+3−1 = 7(7n +3n−1)−9(2n−1) = 7A(n)−9(2n−1). Do A(n)... 9 (theo giả thiết), nên A(n+1)... 9, nghĩa là n+1 ∈ S . Theo nguyên lý quy nạp suy ra S = N, nghĩa là với mọi n ≥ 0, A(n) chia hết cho 9. J Bài toán 1.6. Chứng minh rằng 2 với mọi n ∈ N∗. 13 +23 +33 +···+n3 = n(n+1) 2 Lời giải. Ta ký hiệu T(n) = 13 +23 +33 +···+n3 và 2) S = ( n | n ∈ N∗và T(n) = n(n+1) . 2 Ta kiểm tra những điều kiện của nguyên lý quy nạp toán học: 1) Với n = 1, T(1) = 13 = 1 và 1(1+1) 2 2 = 1 = T(1), suy ra 1 ∈ S . 2) Giả sử n ∈ S , nghĩa là T(n) = n(n+1) 2 2 . Ta xét n+1 ∈ N và T(n+1) = 13 +23 +33 +·+n3 + (n+1)3 = T(n) + (n+1)3 = n(n+1) 2 2 + (n+1)3 = (n+1)(n+2) 2 2 . 1.2. Nguyên lý quy nạp toán học 15 Suy ra n+1 ∈ S . Theo nguyên lý quy nạp toán học S = N∗, nghĩa là với mọi n ≥ 1 ta có T(n) = n(n+1) 2 2 . J Bài toán 1.7. Chứng minh rằng 2n > n với mọi số tự nhiên n. Lời giải. Ta xét tập S = {n | n ∈ N và 2n > n}. Ta kiểm tra điều kiện của nguyên lý quy nạp toán học cho tập S . 1) Với n = 0, ta có 20 = 1 > 0, do đó 0 ∈ S . Với n = 1, ta có 21 = 2 > 1, do đó 1 ∈ S . 2) Giả sử n ≥ 1, n ∈ S nghĩa là n ∈ N∗ và 2n > n. Ta phải chứng minh n + 1 ∈ S . Thật vậy, từ 2n > n nhân hai vế bất đẳng thức với 2, ta nhận được 2n+1 > 2n. Mặt khác do n ≥ 1, cộng hai vế bất đẳng thức này với n, ta nhận được 2n ≥ n+1. Do đó 2n+1 > 2n ≥ n+1, suy ra 2n+1 > n+1, nghĩa là n+1 ∈ S . Theo nguyên lý quy nạp toán học suy ra S = N. Nghĩa là, 2n > n với mọi n ∈ N. J Bài toán 1.8. Chứng minh rằng với mọi số nguyên dương n, luôn có 1−12+13−14+··· −12n=1 n+1+1 n+2+···+12n. Lời giải. Đặt A(n) = 1−12+13−14+··· −12nvà B(n) = 1 n+1+1 n+2+···+12n. Khi đó A(n+1) = A(n) + 1 2n+1−1 2n+2, B(n+1) = B(n)−1 n+1+1 2n+1+1 2n+2. Đặt S = {n | n ∈ N∗ và A(n) = B(n)}. Ta chứng minh bài toán bằng nguyên lý quy nạp: 16 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên 1) Với n = 1, ta có A(1) = 12= B(1), suy ra 1 ∈ S . 2) Giả sử đã có n ∈ S , nghĩa là A(n) = B(n) là đúng. Ta xét A(n+1)−B(n+1) = A(n)−B(n) + 1 n+1−2 2n+2= A(n)−B(n) = 0. Do đó n+1 ∈ S . Theo nguyên lý quy nạp toán học S = N∗. Nghĩa là với mọi n ∈ N∗ta đều có A(n) = B(n). J Bài toán 1.9. Chứng minh rằng (1 +√2)2n + (1 −√2)2nlà một số nguyên chẵn và (1 +√2)2n − (1 −√2)2n = b√2, ở đây b là một số nguyên dương nào đó, với mọi số nguyên dương n. Lời giải. Đặt P(n) = {(1+√2)2n + (1−√2)2nlà một số nguyên chẵn và (1+√2)2n−(1−√2)2n = b√2 với b ∈ N∗} với n ∈ N∗ và S = {n|n ∈ N∗ và P(n) đúng}. Ta sử dụng nguyên lý quy nạp: 1) Với n = 1, thì (1 +√2)2 + (1 −√2)2 = 6 là một số chẵn và (1+√2)2 −(1−√2)2 = 4√2. Do đó 1 ∈ S . 2) Giả sử n−1 ∈ S với n > 1, nghĩa là (1+√2)2(n−1) + (1−√2)2(n−1) = 2N với một số nguyên dương N nào đó và (1+√2)2(n−1) −(1−√2)2(n−1) = a√2 với một số nguyên dương a đã biết. Ta xét đẳng thức (1+√2)2n + (1−√2)2n = (1+√2)2(1+√2)2n−2 + (1−√2)2(1−√2)2n−2 = (3+2√2)(1+√2)2n−2 + (3−2√2)(1−√2)2n−2 = 6N +2√2a√2 = 2(3N +2a). 1.2. Nguyên lý quy nạp toán học 17 Đây là một số chẵn và tương tự ta có (1+√2)2n −(1−√2)2n = 3a√2+2√2(2N) = (3a+4N)√2 và như vậy n ∈ S . Theo nguyên lý quy nạp ta có S = N∗. J Giải các bài toán trên bằng nguyên lý quy nạp theo kiểu tập hợp số tự nhiên. Trong khi sử dụng nguyên lý này ta luôn luôn gặp các mệnh đề lôgic P(n) đúng hoặc sai phụ thuộc vào biến số tự nhiên n và bằng cách đặt tập con S thích hợp để áp dụng được nguyên lý quy nạp. Nhưng thực chất lý luận dựa trên các mệnh đề lôgic đã đặt P(n) từ giả thiết của bài toán. Vì vậy người ta có thể phát biểu lại nguyên lý quy nạp theo dạng mệnh đề như sau: Định lý 1.3 (Nguyên lý quy nạp toán học dạng mệnh đề). Cho một dãy mệnh đề P(0),P(1),P(2),... có nghĩa và thỏa mãn: 1) P(0) đúng; 2) Nếu với mỗi k ∈ N, P(k) đúng suy ra P(k +1) cũng đúng, thì P(n) đúng với mọi n ∈ N. Chứng minh. Đặt S = {n | n ∈ N và P(n) đúng }. Dễ dàng kiểm tra thấy rằng 0 ∈ S và k ∈ S kéo theo k+1 ∈ S . Theo Định lý 1.2, ta có S = N. Từ đây suy ra kết quả cần chứng minh. J Thực tế người ta sử dụng Định lý 1.3 thuận tiện hơn. Phương pháp dùng nguyên lý quy nạp toán học để chứng minh gọi là phương pháp quy nạp toán học. Đặc điểm của phương pháp này bao gồm hai bước: Bước thứ nhất gọi là bước cơ sở: Kiểm tra P(0) đúng. Bước thứ hai gọi là bước quy nạp: Chứng minh nếu P(n) đúng thì P(n+1) cũng đúng. Kết luận là P(n) đúng với mọi n ∈ N. Vấn đề này được bàn kĩ trong cuốn sách [12]. Sau đây chỉ nêu một số ví dụ. 18 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Bài toán 1.10. Chứng minh rằng nếu k là một số lẻ, thì k2n−1 chia hết cho 2n+2với mọi số n nguyên dương. Lời giải. Cho k là một số lẻ. Đặt P(n) = {k2n−1 chia hết cho 2n+2} với n ∈ N∗. Ta chứng minh bằng phương pháp quy nạp theo n. Bước cơ sở: Với n = 1, k2 − 1 = (k − 1)(k + 1) chia hết cho 8 với mọi số tự nhiên k lẻ, bởi vì đồng thời cả hai số (k−1) và (k+1) chia hết cho 2 và một trong chúng chia hết cho 4. Bước quy nạp: Giả sử k2n−1... 2n+2, ta phải chứng minh k2n+1−1... 2n+3. Thật vậy, vì k2n+1−1 = (k2n−1)(k2n+1), theo giả thiết quy nạp k2n−1 chia hết cho 2n+2, ta chỉ cần chứng minh k2n+1 chia hết cho 2. Nhưng điều đó là hiển nhiên đúng (có thể phân tích ra thừa số), vì k2nlà một số lẻ, tạo ra k2n+1 là một số chẵn. Theo nguyên lý quy nạp mệnh đề suy ra kết luận đúng với mọi n ≥ 1. J Bài toán 1.11 (Mĩ 1978). Một số nguyên n được gọi là số đẹp nếu ta có thể viết n = a1 +a2 +···+ak, ở đây a1,a2,...,ak là những số nguyên dương (có thể không khác nhau) thỏa mãn1 a1+1a2+···+1ak= 1. Biết rằng những số nguyên từ 33 đến 73 đều là những số đẹp, chứng minh rằng với mọi số nguyên lớn hơn hoặc bằng 33 cũng đều là những số đẹp. Lời giải. Trước tiên ta chứng minh rằng nếu n là số đẹp, thì 2n + 8 và 2n + 9 cũng là những số đẹp. Thật vậy, từ giả thiết ta có 1.2. Nguyên lý quy nạp toán học 19 n = a1 +a2 +···+ak và 1 a1+1a2+···+1ak= 1. Khi đó 2n+8 = 2a1 +2a2 +···+2ak +4+4 và 2a1+12a2+···+12ak+14+14=12+14+14= 1. 1 Tương tự, ta có 2n+9 = 2a1 +2a2 +···+2ak +3+6 và 2a1+12a2+···+12ak+13+16=12+13+16= 1. 1 Do đó nếu n là số đẹp thì đồng thời 2n+8 và 2n+9 đều là số đẹp. Đặt P(n) = {Tất cả các số n,n+1,n+2,...,2n+7 là số đẹp}. Ta chứng minh mệnh đề này bằng phương pháp quy nạp theo n. Bước cơ sở: Theo giả thiết thì với n = 33, P(33) là đúng. Bước quy nạp: Từ mệnh đề chứng minh ở phần đầu nếu P(n) đúng suy ra P(n+1) cũng đúng. Theo nguyên lý quy nạp mệnh đề P(n) đúng cho mọi số nguyên n lớn hơn hoặc bằng 33. J Bài toán 1.12. Tìm các hàm số f : N∗ → N∗sao cho (a) f(2) = 2; (b) f(n+1) = 1+1 f(1) +2 f(2) +···+n f(n) với mọi n ∈ N∗. Lời giải. Nếu n = 1 thì từ (b) ta nhận được f(2) = 1+1 f(1). Do đó f(1) = 1. Nếu n = 2, thì ta nhận được f(3) = 1+1 f(1) +2 f(2) = 1+1+4 = 6. Tương tự, ta tính được f(4) = 24 và f(5) = 120. Vậy ta có nhận xét f(1) = 1!, f(2) = 2!, f(3) = 3!, f(4) = 4!, f(5) = 5!. 20 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Ta có dự đoán: f(n) = n! với mọi n ∈ N∗. Ta chứng minh dự đoán bằng phương pháp quy nạp. Bước cơ sở: Với n = 1, mệnh đề đúng như kiểm tra ở trên. Bước quy nạp: Giả sử mệnh đề đúng với mọi n ≤ k, tức là f(1) = 1!,..., f(k) = k!, ta phải chứng minh nó cũng đúng với n = k +1, nghĩa là f(k +1) = (k +1)!. Thật vậy, từ (b) ta có f(k +1) = 1+1.1!+2.2!+···+k.k!. Mặt khác, ta luôn có đẳng thức 1+1.1!+2.2!+···+n.n! = (n+1)!. đúng với mọi n ∈ N∗(điều này cũng có thể chứng minh bằng phương pháp quy nạp). Do đó f(k +1) = (k +1)!. Từ chứng minh trên suy ra chỉ có hàm số f : N∗ → N∗thỏa mãn (a) và (b) là f(n) = n!. J Bài toán 1.13. Ta xét những tập con của tập hợp {1,2,...,n} mà chúng không chứa bất kì hai số tự nhiên liên tiếp nào. Chứng minh rằng tổng bình phương các tích của tất cả các số trong những tập con này là (n+1)!−1 (ví dụ: Nếu n = 3 thì những tập con là {1},{2},{3},{1,3} và tổng bình phương các tích của chúng là 12 + 22 + 32 + (1.3)2 = 4!−1). Lời giải. Ta chứng minh bằng phương pháp quy nạp theo n. Bước cơ sở: Với n = 1, mệnh đề đúng. Bước quy nạp: Giả sử mệnh đề đúng với n ≤ k và ta phải chứng minh rằng mệnh đề cũng đúng với n = k + 1. Thật vậy, ta lấy tất cả tập con của tập hợp {1,2,..., k, k +1} mà nó không chứa hai số tự nhiên 1.2. Nguyên lý quy nạp toán học 21 liên tiếp. Ta chia những tập hợp con theo hai tiêu chuẩn: (1) những tập hợp con chứa số k+1, và (2) những tập hợp con không chứa số k +1. Theo giả thiết quy nạp, tổng bình phương các tích cho loại tập hợp con thứ nhất là (k+1)2(k!−1) + (k+1)2 và cho loại tập thứ hai là (k +1)!−1. Vì thế tổng cần tìm là (k +1)2(k!−1) + (k +1)2 + (k +1)!−1 = (k +2)!−1. Do đó mệnh đề vẫn đúng với n = k+1. Vậy nó đúng cho mọi n ∈ N∗. J Bài toán 1.14. Cho x, y là hai số thực khác 0 sao cho x+1x, y+1yvà xy+1xylà những số nguyên. Chứng minh rằng xnym +1 xnymcũng là số nguyên với m và n là hai số nguyên dương bất kì. Lời giải. Ta dùng phương pháp quy nạp chứng minh rằng ym +1ym là số nguyên với mọi số nguyên dương m. Bước cơ sở: Với m = 1, mệnh đề đúng (do giả thiết đã cho). Bước quy nạp: Giả sử mệnh đề đúng với mọi m = i,1 ≤ i ≤ k, ta phải chứng minh mệnh đề cũng đúng với m = k +1. Thật vậy, dễ thấy có đẳng thức sau: yk+1 +1 yk+1= Vì y+1y, yk−1 +1 y+1y yk +1yk − yk−1 +1 yk−1 . yk−1, yk +1yklà những số nguyên (theo giả thiết quy nạp), từ đó suy ra yk+1 +1 yk+1là số nguyên. Do đó ym +1ymlà số nguyên với mọi số nguyên dương m. 22 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Ta chứng minh rằng xym +1xymlà số nguyên với mọi số nguyên dương m. Ta lại chứng minh bằng phương pháp quy nạp theo m. Bước cơ sở: Với m = 1 mệnh đề đúng, do giả thiết đã cho. Bước quy nạp: Giả sử mệnh đề đúng với m = i,1 ≤ i ≤ k, ta sẽ chứng minh nó cũng đúng với m = k +1. Thật vậy, dễ thấy đẳng thức sau đúng: y+1y xyk +1xyk − xyk−1 +1 xyk+1 +1 xyk+1= xyk−1 . Cuối cùng ta chứng minh xnym +1 xnymlà số nguyên. Ta dùng phương pháp quy nạp theo n. Bước cơ sở: Với n = 1, mệnh đề đúng (theo chứng minh phần trước). Bước quy nạp: Giả sử mệnh đề đúng với mọi n = i,1 ≤ i ≤ k, ta phải chứng minh mệnh đề cũng đúng với n = k + 1. Thật vậy, dễ thấy đẳng thức sau đúng: x+1x xkym +1 xk+1ym +1 xk+1ym= Vì x+1x, xkym +1 xkym − xk−1ym +1 xk−1ym . xkym, xk−1ym +1 xk−1ymlà những số nguyên (theo giả thiết quy nạp), từ đó suy ra xk+1ym +1 xnym +1 xk+1ymlà số nguyên. Do đó xnymlà số nguyên với mọi số nguyên dương m,n. J Nhiều vấn đề khác về nguyên lý quy nạp loại này được trình bày trong cuốn sách [12]. Mục đích của cuốn sách này không phải nói về vấn đề này nên ta dừng lại đây. 1.3. Sự tương đương giữa hai nguyên lý 23 1.3. SỰ TƯƠNG ĐƯƠNG GIỮA HAI NGUYÊN LÝ Định lý 1.2 đã chỉ ra rằng từ nguyên lý thứ tự suy ra nguyên lý quy nạp toán học. Sau đây ta sẽ chứng minh ngược lại, nếu ta có nguyên lý quy nạp thì suy ra nguyên lý thứ tự. Định lý 1.4. Nguyên lý quy nạp toán học kéo theo nguyên lý thứ tự. Chứng minh. Giả thiết đã cho nguyên lý quy nạp toán học đúng. Ta phải chứng minh rằng nếu S là tập con khác rỗng những số tự nhiên, thì S có phần tử nhỏ nhất. Tức là ta phải chứng minh: Nếu S không có phần tử nhỏ nhất, thì S = /0. Thật vậy, giả sử S không có phần tử nhỏ nhất. Ký hiệu S là phần bù của S . Nếu 0 nằm trong S thì 0 là phần tử nhỏ nhất của S , điều này vô lý với giả thiết đã cho về S . Do đó 0 ∈ S . Giả sử n là số tự nhiên, n ≥ 1 và 0,1,2,...,n − 1 nằm trong S . Nếu n nằm trong S , thì n là phần tử nhỏ nhất của S , điều này trái với giả thiết về S . Do đó n nằm trong S . Theo nguyên lý quy nạp toán học suy ra S = N, như vậy S = /0. J Thực chất hai nguyên lý ta đang nghiên cứu tương đương nhau. Nghĩa là một bài toán sử dụng một nguyên lý này để giải thì có thể sử dụng nguyên lý kia cũng giải được. Ta xét một số ví dụ để thấy hai cách chứng minh dùng hai nguyên lý khác nhau có mối liên quan như thế nào. Bài toán 1.15. Chứng minh rằng tập hợp những miền xác định bởi n đường thẳng trên mặt phẳng có thể tô chỉ bằng hai màu sao cho hai miền chung cạnh có màu khác nhau. Lời giải. Cách thứ 1: Chứng minh theo phương pháp quy nạp. Ta chứng minh bằng quy nạp theo số đường thẳng trong mặt phẳng. 24 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Với n = 1 thì mặt phẳng được chia ra thành hai miền nên ta có thể tô bằng hai màu khác nhau. Giả sử mệnh đề đúng với n đường thẳng (n ∈ N∗). L Hình 1.1 L Hình 1.2 Cho n + 1 đường thẳng trong mặt phẳng. Ta bỏ đi một đường thẳng L (Hình 1.1) và tô màu những miền do n đường thẳng còn lại tạo ra bằng hai màu sao cho hai miền chung cạnh có màu khác nhau (điều này có thể làm được do giả thiết quy nạp là đúng). Đặt trả lại đường thẳng L và đổi màu tất cả các miền nằm về một phía của đường thẳng L (Hình 1.2). Ta xét hai miền có một đường thẳng chung. Nếu đường thẳng không phải là L thì theo giả thiết quy nạp hai miền có màu khác nhau (hoặc như cũ hoặc là ngược lại). Nếu đường thẳng là L thì hai miền được tạo ra từ một miền trước khi có L sẽ có màu khác nhau, vì ta đã đổi màu ở một bên đường thẳng L. Cách thứ 2: Chứng minh theo phương pháp nguyên lý thứ tự. Giả sử khẳng định của bài toán không đúng và có những bộ đường thẳng trên mặt phẳng chia mặt phẳng thành những miền không thể tô mầu như điều kiện bài ra. Nói chung những bộ đường thẳng có tính chất như vậy có thể có rất nhiều và số lượng đường thẳng trong các bộ có thể khác nhau. Ta xét một trong các bộ đường thẳng có số 1.3. Sự tương đương giữa hai nguyên lý 25 đường thẳng nhỏ nhất (nguyên lý thứ tự) và cho đó là n. Ở đây n không thể là 1, vì với một đường thẳng sẽ chia mặt phẳng thành hai miền nên ta có thể tô hai màu khác nhau. Trong bộ n đường thẳng nhỏ nhất trên, ta lấy đi một đường thẳng bất kì và ta xét n−1 đường thẳng còn lại. Ta sẽ nhận được bộ n−1 đường thẳng chia mặt phẳng thành những miền mà có thể tô được bằng hai màu với hai miền có chung cạnh thì có hai màu khác nhau (vì bộ n đường thẳng là nhỏ nhất không tô màu được). Sau đó ta trả lại đường thẳng vừa lấy đi và ta tô màu được theo cách chứng minh ở phần quy nạp trên cho n đường thẳng. Điều này vô lý, vì bộ n đường thẳng này không thể chia mặt phẳng thành những miền mà tô bằng hai màu như cách chọn trên. Như vậy không thể có bộ đường thẳng nào mà không thỏa mãn giả thiết bài toán. Đó là điều cần chứng minh. J Bài toán 1.16. Chứng minh rằng với mọi số nguyên nghìn đồng (tiền Việt Nam) lớn hơn 6 nghìn có thể đổi bằng những đồng tiền gồm những tờ 2 nghìn đồng và 5 nghìn đồng. Lời giải. Cách thứ 1: Chứng minh theo phương pháp quy nạp. Bước cơ sở: Đẳng thức sau đây nói lên với n = 7 nghìn đồng, n = 8 nghìn đồng thì đổi bằng những tờ 2 nghìn đồng và 5 nghìn đồng như thế nào: 7 = 5+2; 8 = 2+2+2+2. Nếu ta thêm vào hai vế của các đẳng thức trên tờ 2 nghìn đồng, thì 9 = 7+2; 10 = 8+2. 26 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Tiếp tục thêm 2 nghìn đồng vào hai đẳng thức sau cùng, ta có 11 = 9+2; 12 = 10+2. Bước quy nạp: Ta thấy rằng ở bước trước có hai đẳng thức và suy ra bước sau có hai đẳng thức. Như vậy với mọi số n(n ≥ 7) nguyên nghìn đồng nào dù là số chẵn hoặc số lẻ thì n−2 cũng rơi vào một trong hai trường hợp trước đó đã đổi được ra hai loại tiền 2 nghìn đồng và 5 nghìn đồng. Suy ra nó cũng đổi thành các tờ 2 nghìn đồng và 5 nghìn đồng. Như vậy, khẳng định của mệnh đề là đúng với mọi n ≥ 7. Cách thứ 2: Chứng minh theo nguyên lý thứ tự. Giả sử có số tiền (số nguyên nghìn đồng và không nhỏ hơn 7 nghìn đồng) mà nó không thể thanh toán được bằng các tờ 2 nghìn đồng và 5 nghìn đồng. Có thể có nhiều tổng như vậy, ta lấy số nhỏ nhất trong chúng (theo nguyên lý thứ tự). Ta cho đó là số n nghìn đồng. Theo giả thiết n ≥ 7 vì thế giá trị n < 7 ta không xem xét. Ta cũng biết rằng n không thể là 7 nghìn đồng và 8 nghìn đồng, vì những số tiền này đều thanh toán được bằng các tờ 2 nghìn đồng và 5 nghìn đồng. Nghĩa là n ≥ 9. Khi đó n−2 ≥ 7 và ngoài ra n−2 < n. Nghĩa là số n−2 có thể thanh toán được bằng các tờ 2 nghìn đồng và 5 nghìn đồng (vì ta chọn n là nhỏ nhất, số tiền mà không thể thành toán được). Nếu ta thêm vào tờ 2 nghìn đồng, thì ta nhận được n nghìn đồng, như vậy số tiền này có thể thanh toán bằng các tờ 2 nghìn đồng và 5 nghìn đồng. Điều này vô lý vì ta đã chọn n nghìn đồng là số tiền nhỏ nhất không thể thanh toán được bằng tờ 2 nghìn đồng và 5 nghìn đồng. J Bài toán 1.17. Cho dãy số Fibonacci 1,1,2,3,5,8,13,21,34,55,... 1.3. Sự tương đương giữa hai nguyên lý 27 trong đó hai phần tử đầu bằng 1, bắt đầu từ phần tử thứ ba mỗi phần tử bằng hai phần tử ngay trước đó cộng lại. Chứng minh rằng hai số hạng kề nhau không cùng chia hết cho 7. Chứng minh. Cách thứ 1: Chứng minh theo phương pháp nguyên lý thứ tự. Giả sử ngược lại tồn tại hai số hạng của dãy Fibonacci kề nhau đầu tiên cùng chia hết cho 7 là 7k,7`. Vì hai số đầu tiên của dãy Fibonacci là hai số 1, nên những số này không thể là những số đầu tiên. Nghĩa là trước những số này tồn tại số hạng a. Theo điều kiện bài toán có 7` = a+7k, nên a = 7`−7k = 7(`−k) và vì thế a cũng chia hết cho 7. Nghĩa là 7k,7` không phải là hai số hạng kề nhau đầu tiên trong dãy chia hết cho 7 như điều giả sử trên. Điều vô lý này suy ra không thể có hai số hạng kề nhau trong dãy Fibonacci cùng chia hết cho 7. Cách thứ 2: Chứng minh theo phương pháp quy nạp. Ta chứng minh bằng quy nạp theo n mệnh đề sau: Một trong hai số hạng Fn và Fn+1 của dãy Fibonacci không chia hết cho 7 với mọi n = 1,2,... Bước cơ sở: Với n = 1 ta dễ thấy F1 và F2 không chia hết cho 7. Bước quy nạp: Giả sử một trong hai số hạng Fn−1 và Fn (với n ≥ 2) không chia hết cho 7, ta phải chứng minh rằng một trong hai số hạng Fn và Fn+1 cũng không chia hết cho 7. Giả sử ngược lại Fn và Fn+1 đều chia hết cho 7, thì Fn−1 = Fn+1 − Fn cũng chia hết cho 7. Như vậy Fn−1 và Fn đều chia hết cho 7 trái với giả thiết quy nạp. J Theo cách làm của những bài trên, nhiều bài toán chứng minh bằng phương pháp quy nạp ta cũng có thể chứng minh được khi áp dụng nguyên lý thứ tự. Ta xét một số ví dụ sau đây. Bài toán 1.18. Cho số thực x khác 0 thỏa mãn x +1xlà số nguyên. 28 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Chứng minh rằng xn +1xncũng là một số nguyên với mọi n ∈ N∗. Lời giải. Bài toán này là trường hợp đặc biệt của Bài toán 1.14, Ta trình bày hai cách chứng minh khác nhau sau đây. 1) Phương pháp quy nạp. Đặt B(n) = xn +1xnvới n ∈ N∗. Bước cơ sở: Với n = 1, ta có B(1) = x+1xlà số nguyên (theo giả thiết). Với n = 2, ta có B(2) = x2+1x2= x+1x 2−2 cũng là một số nguyên. Bước quy nạp: Giả sử B(n) và B(n+1) với n ∈ N∗là các số nguyên. Ta chứng minh B(n + 2) cũng là số nguyên. Thật vậy, dễ dàng có đẳng thức B(n + 2) = B(n + 1)B(1) − B(n), suy ra điều cần chứng minh. Như vậy, với mọi n ∈ N∗, B(n) là số nguyên. 2) Phương pháp phần tử cực biên. Giả sử có một số giá trị n ∈ N∗ nào đó mà B(n) không là số nguyên. Ta chọn n là số tự nhiên nhỏ nhất mà B(n) không phải là số nguyên. n không thể là 1 và 2, vì theo giả thiết và tính toán đơn giản như ở phương pháp quy nạp. Vậy n−2 > 0. Dễ dàng kiểm tra được B(n) = B(n−1)B(1)−B(n−2), mà n−1 < n và n−2 < n nên B(n−1) và B(n−2) là những số nguyên, suy ra B(n) cũng là số nguyên. Điều này trái với cách chọn n là số tự nhiên nhỏ nhất sao cho B(n) là số nguyên. Điều vô lý này cũng chỉ ra không thể có số tự nhiên n nào mà B(n) không là số nguyên. J Bài toán 1.19. Chứng minh rằng S(n) = 10n +18n−1 chia hết cho 27 với mọi số tự nhiên n. Lời giải. 1) Phương pháp quy nạp toán học. Bước cơ sở: Với n = 0, ta có S(0) = 0 chia hết 27, mệnh đề đúng. Bước quy nạp: Giả sử mệnh đề đúng với n = k ∈ N nghĩa là S(k)... 27. 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ 29 Ta cần chứng minh mệnh đề đúng với n = k +1, nghĩa là cần chứng minh S(k +1)... 27. Ta có S(k +1) = 10k+1 +18(k +1)−1 = 10.10k +18k +18−1 = 10(10k +18k −1)−27(6k −1). Do S(k) = 10k + 18k − 1... 27 (theo giả thiết quy nạp), nên S(k +1)... 27, ta có điều phải chứng minh. 2) Phương pháp phần tử cực biên. Giả sử có một số số tự nhiên n mà S(n) không chia hết cho 27. Ta chọn n nhỏ nhất trong các số đó (điều này thực hiện được theo nguyên lý thứ tự). Số n không thể là 0, khi đó S(n−1) chia hết cho 27. Nhưng ta có S(n) = 10n +18n−1 = 10.10n−1 +18(n−1) +18−1 = 10(10n−1 +18(n−1)−1)−27(6n−7). Từ đẳng thức trên suy ra S(n) chia hết cho 27, điều này vô lý với cách chọn n. Như vậy mệnh đề khẳng định đúng. J 1.4. CHUYÊN ĐỀ TẬP HỢP SẮP THỨ TỰ ĐẦY ĐỦ Chuyên đề này nghiên cứu các tập sắp thứ tự theo một cách nào đó. Cho một tập hợp các đối tượng (không nhất thiết phải là các số nguyên), ta định nghĩa một thứ tự theo quan hệ giữa các đối tượng trong tập hợp, thứ tự đưa vào có những tính chất có ích để giải toán (như thứ tự trong các số nguyên). Nhờ các định nghĩa thứ tự này mà ta có thể giải các bài toán đặt ra với các đối tượng trong tập hợp. 30 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên 1.4.1. Thứ tự của một tập hợp bất kì Phần đầu của chương này ta xét nguyên lý thứ tự và nguyên lý quy nạp cho tập số tự nhiên. Câu hỏi đặt ra là: Cho một tập bất kì những đối tượng, có cách nào đó ta sắp xếp các đối tượng theo một thứ tự quy định được không? Như vậy giữa hai phần tử của một tập hợp phải xác định quan hệ như kiểu "lớn hơn" hoặc "nhỏ hơn". Trong lý thuyết tập hợp người ta đã nghiên cứu kĩ vấn đề này. Ta nhắc lại những định nghĩa cơ bản ở đây. Định nghĩa 1.1. Một quan hệ hai ngôi trong tập hợp X là một tập hợp con R ⊂ X ×X . Đáng lẽ viết (x1, x2) ∈ R người ta thường viết x1Rx2. Định nghĩa 1.2. Một quan hệ hai ngôi R trên tập hợp X được gọi là quan hệ tương đương, nếu nó có các tính chất sau: • xRx với mọi x ∈ X (tính phản xạ); • Từ xRy suy ra yRx với mọi x, y ∈ X (tính đối xứng); • Từ xRy và yRz suy ra xRz với mọi x, y,z ∈ X (tính bắc cầu). Ta có định lý rất hay dùng sau đây. Định lý 1.5. (a) Nếu một tập hợp X là hợp của những tập hợp con không giao nhau, thì quan hệ "thuộc vào một tập hợp con" là một quan hệ tương đương. (b) Mỗi quan hệ tương đương trên X chia X thành những tập hợp con không giao nhau. Chứng minh. Ta chỉ chứng minh (b), vì (a) chứng minh được từ định nghĩa quan hệ tương đương. Cho R là một quan hệ tương đương trên X . Với mỗi phần tử x ∈ X ta xét lớp tương đương của nó, nghĩa là tập hợp tất cả y ∈ X sao cho xRy. 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ 31 Ta sẽ chứng minh rằng với hai phần tử khác nhau x1, x2 thì hai lớp tương đương tương ứng của chúng hoặc là không giao nhau hoặc là trùng nhau. Giả sử hai lớp đó giao nhau, khi đó chúng có phần tử chung z. Từ x1Rz và x2Rz suy ra zRx2 (tính đối xứng) và x1Rx2 (tính bắc cầu), cũng tương tự cho x2Rx1 (tính đối xứng). Vì thế từ x1Rv suy ra x2Rv với mọi v (tính bắc cầu) và ngược lại, nên hai lớp tương đương chứa x1 và x2 trùng nhau. Theo tính chất phản xạ mỗi phần tử x ∈ X nằm trong lớp tương đương với x, do đó tập hợp X được chia thành những tập hợp con (lớp) không giao nhau. J Tập hợp những lớp tương đương được gọi là tập hợp thương của X theo quan hệ tương đương R. Định nghĩa 1.3. Một quan hệ hai ngôi (ký hiệu là ≤) của tập hợp X gọi là quan hệ thứ tự từng phần, nếu nó có những tính chất: • x ≤ x với mọi x ∈ X (tính phản xạ); • x ≤ y và y ≤ x suy ra x = y với mọi x, y ∈ X (tính phản đối xứng); • x ≤ y và y ≤ z suy ra x ≤ z với mọi x, y,z ∈ X (tính bắc cầu). Chú ý: Do truyền thống ta ký hiệu quan hệ thứ tự từng phần là ≤, ta có thể dùng bất cứ một ký hiệu nào khác đều được. Định nghĩa 1.4. Một tập hợp với quan hệ thứ tự từng phần gọi là tập hợp sắp thứ tự từng phần. Định nghĩa 1.5. Ta nói rằng hai phần tử x, y của một tập hợp sắp thứ tự từng phần là so sánh được, nếu x ≤ y hoặc là y ≤ x. Định nghĩa 1.6. Nếu hai phần tử bất kì của tập hợp sắp thứ tự từng 32 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên phần đều so sánh được, thì tập hợp đó gọi là tập hợp sắp thứ tự toàn phần. Ta chỉ ra một số ví dụ về tập hợp sắp thứ tự từng phần: 1. Tập hợp số thực với quan hệ thứ tự bình thường (chú ý đây là tập hợp sắp thứ tự toàn phần). 2. Trên tập hợp R×R, với tất cả các cặp số thực có thể đưa vào thứ tự từng phần: (x1, x2) ≤ (y1, y2) nếu x1 ≤ y1 và x2 ≤ y2. Tập hợp với thứ tự này không sắp thứ tự toàn phần, vì (0,1) và (1,0) không so sánh được theo thứ tự đưa vào. 3. Trên tập hợp tất cả các hàm với đối số thực và có giá trị thực, ta có thể đưa vào quan hệ thứ tự: f ≤ g, nếu f(x) ≤ g(x) với mọi x ∈ R. Tập hợp này không sắp thứ tự toàn phần. 4. Trên tập hợp tất cả những số nguyên dương có thể đưa vào quan hệ thứ tự: x ≤ y nếu x chia hết cho y. Tập hợp này không sắp thứ tự toàn phần. 5. Cho U là tập hợp bất kì. Khi đó tập hợp P(U) gồm tất cả những tập hợp con của U, với quan hệ "bao hàm" ⊂, là một tập hợp sắp thứ tự từng phần. 6. Bảng chữ cái tiếng Việt sắp xếp theo truyền thống từ điển: a ≤ b ≤ ... ≤ y. Quan hệ sắp xếp này cũng là sắp thứ tự từng phần. Với thứ tự này tập hợp các từ tiếng Việt là sắp thứ tự toàn phần. 7. Tập hợp các từ tiếng Việt sắp xếp theo thứ tự từ điển lần lượt theo thứ tự chữ cái của một từ. Ví dụ từ Ang xếp trước từ Anh. Nó là tập hợp sắp thứ tự toàn phần. Trong thực tế rất nhiều ví dụ cho tập hợp với thứ tự từng phần bằng một cách định nghĩa thích hợp nào đó. 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ 33 Cho x, y là hai phần tử của tập hợp sắp thứ tự từng phần X . Ta định nghĩa quan hệ x < y nếu x ≤ y và x 6= y. Quan hệ này có tính chất sau: (a) x 6< x: Không có phần tử nhỏ hơn chính nó. (b) x < y và y < z suy ra x < z. Thật vậy, nếu x < y và y < z, thì x ≤ y, x 6= y và y ≤ z, y 6= z, do đó x ≤ z (theo tính bắc cầu); nếu x = z, thì ta có x ≤ y ≤ x và suy ra x = y (theo tính phản đối xứng) điều này trái với giả thiết x 6= y. Định nghĩa 1.7. Phần tử của một tập hợp sắp thứ tự từng phần gọi là lớn nhất nếu nó lớn hơn mọi phần tử bất kì khác trong tập hợp này. Tương tự ta cũng định nghĩa phần tử nhỏ nhất cho tập hợp sắp thứ tự từng phần. Từ những định nghĩa sắp thứ tự của một tập hợp, ta có thể áp dụng giải những bài toán tương đối khó. Bài toán 1.20. Mười người lính tân binh đứng theo hàng ngang quay mặt ra phía trước hàng (Hình 1.3). Hình 1.3 Một sĩ quan chỉ huy ra lệnh "bên trái quay". Những người tân binh mới này một số quay bên phải, một số quay bên trái (Hình 1.4). Sau đó mỗi phút khi hai người lính đối diện với nhau nghĩ là mình lầm và đều quay về phía sau (Hình 1.5). 34 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên P T P T T P P T P T Hình 1.4 P P T T P T P P T T Hình 1.5 Những người lính này nếu đối diện với người lính khác thì họ lại thực hiện đằng sau quay và cứ tiếp tục như vậy. Chứng minh rằng sớm hay muộn trong hàng không còn ai phải thực hiện đằng sau quay nữa và hàng được xếp theo thứ tự mong muốn. Lời giải. Ta đánh dấu vị trí của các người lính bằng những chữ cái liên tiếp P (mặt quay bên phải) và T (mặt quay bên trái). Như vậy vị trí của hàng được sắp xếp như P T P T T P P T P T Sau một phút thì các vị trí lại có cấu hình P P T T P T P P T T Sau hai phút thì các vị trí lại có cấu hình P P T P T P T P T T và tiếp tục... Số cặp T P sau mỗi bước thay đổi thế nào ? Theo giả thiết của bài 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ 35 toán những người đối mặt với nhau phải thực hiện đằng sau quay (trong trường hợp này chúng ta ký hiệu bằng T P, nghĩa là người có mặt quay bên phải và người có mặt quay bên trái. Vậy sau phép quay những chữ cái T P đổi thành P T). Mỗi bước có một số sự đổi chỗ ký tự, mà số lượng đổi chỗ bằng số nhóm T P. Bây giờ ta quan sát đơn giản sau đây: "Ta coi những ký tự được ký hiệu cả hàng lính là một từ. Khi đó với những thay đổi các cặp ký tự như trên thì từ này giảm theo cách sắp xếp thứ tự chữ cái của tiếng Việt". Thật vậy, nhóm bên trái nhất T P đổi thành P T, chữ cái P đứng trước chữ cái T trong thứ tự chữ cái (những thay đổi của các nhóm khác không ảnh hưởng đến thứ tự). Vì thế, sau mỗi lần đổi nhóm T P càng ngày càng nhỏ và sớm hay muộn quá trình này cũng đến lúc dừng, bởi vì tồn tại hữu hạn độ dài của từ đã cho (n = 10) các chữ cái T và P (nhiều nhất có 210 thay đổi). Vậy bài toán đã được giải. J Trong khi giải bài toán trên ta đã dùng tính chất: Không tồn tại một dãy giảm đến vô cùng (theo thứ tự của bảng chữ cái) từ một từ có n chữ cái T và P. Một cách tổng quát hơn, nếu sau mỗi bước ta giảm phần tử của tập hợp thứ tự tuyến tính, thì sớm hay muộn quá trình giảm này cũng phải dừng. 1.4.2. Tập hợp sắp thứ tự đầy đủ và ứng dụng Tương tự nguyên lý quy nạp trong tập số nguyên, trong các tập hợp sắp thứ tự cũng có khẳng định sau: Định lý 1.6. Trong một tập hợp sắp thứ tự từng phần X , ba tính chất sau đây tương đương: (a) Mọi tập con khác rỗng của X có phần tử nhỏ nhất; 36 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên (b) Không tồn tại dãy vô hạn giảm thực sự x0 > x1 > x2 > ··· những phần tử của tập X ; (c) Với tập hợp X , nguyên lý quy nạp đúng dưới dạng sau đây : Cho mệnh đề A(x) có nghĩa đối với mọi x ∈ X . Nếu (với mọi x ∈ X ) từ A(y) đúng với mọi y < x suy ra A(x) cũng đúng, thì tính chất A(x) đúng với mọi x ∈ X . Chứng minh. 1. Ta chứng minh hai tính chất đầu tương đương: Giả sử (a) đúng, nếu x0 > x1 > x2 > ··· là dãy giảm vô hạn, thì hiển nhiên tập hợp dãy này không có phần tử nhỏ nhất (vì mỗi phần tử có phần tử sau nhỏ hơn), điều này mâu thuẫn với (a). Vì thế từ (a) suy ra (b). Ngược lại, nếu một tập hợp con khác rỗng B nào đó không có phần tử nhỏ nhất, thì dãy vô hạn giảm có thể xây dựng được như sau: Lấy một phần tử bất kì b0 ∈ B. Theo giả thiết tập này không có phần tử nhỏ nhất nên có thể tìm được b1 ∈ B sao cho b0 > b1. Cũng như vậy ta có thể tìm được b2 ∈ B sao cho b1 > b2 và ... Ta nhận được dãy giảm vô hạn, điều này vô lý vì ta đã có giả thiết (b). 2. Ta chứng minh (a) và (c) tương đương: Ta giả sử (a) đúng, nghĩa là mọi tập con của X đều có phần tử nhỏ nhất, ta sẽ chứng minh có nguyên lý quy nạp (c). Giả sử A(x) không đúng với tất cả phần tử x ∈ X . Ta xét tập hợp khác rỗng B những phần tử x ∈ X mà A(x) không đúng. Giả sử x là phần tử nhỏ nhất của B (ta tìm được x vì (a) đúng). Theo giả thiết những phần tử nhỏ hơn trong B không có nữa, vì thế mọi y < x tính chất A(y) đúng suy ra A(x) cũng đúng, điều này vô lý với cách chọn x. Ngược lại, giả sử (c) đúng, ta phải chứng minh rằng mọi tập con khác rỗng của X đều có phần tử nhỏ nhất. Tức là ta phải chứng 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ 37 minh nếu B là một tập con không có phần tử nhỏ nhất, thì B = /0. Nói cách khác, cần chứng minh A(x) đúng với mọi x 6∈ B. Thật vậy, Giả sử B không có phần tử nhỏ nhất. Ký hiệu B là phần bù của B. Giả sử x ∈ X và A(y) đúng với mọi y < x, mà mọi y đều thuộc B. Nếu x nằm trong B, thì nó là phần tử nhỏ nhất, điều này vô lý. Suy ra x ∈ B, theo (c), A(x) đúng với mọi x ∈ B. Đó là điều ta cần chứng minh. J Định nghĩa 1.8. Tập hợp sắp thứ tự toàn phần A được gọi là tập hợp sắp thứ tự đầy đủ nếu không tồn tại dãy giảm vô hạn x0 > x1 > x2 > x3 > ··· ở đây x0, x1, x2,... ∈ A . Ví dụ về tập hợp sắp thứ tự đầy đủ là: 1. Tập hợp tất cả các số tự nhiên với thứ tự bình thường. 2. Trong tập hợp N×N các cặp số tự nhiên, ta đưa vào định nghĩa sắp thứ tự như sau: Cặp số (a1,a2) nhỏ hơn cặp số (b1,b2), ký hiệu là (a1,a2) ≤ (b1,b2), nếu a2 < b2; trường hợp a2 = b2 thì a1 < b1 (thứ tự lớn hơn thì ngược lại). Với cách sắp thứ tự này thì tập hợp N×N là tập hợp sắp thứ tự đầy đủ. Thật vậy, ta kiểm tra (b) theo mệnh đề tương đương: Mỗi dãy u0 ≥ u1 ≥ u2 ≥ ··· những phần tử của tập hợp sớm hay muộn rồi cũng dừng (tất cả các phần tử đến một lúc nào đó trở đi đều bằng nhau). Mệnh đề này tương đương với (b). Giả sử cho dãy cặp số bất kì (x0, y0) ≥ (x1, y1) ≥ (x2, y2) ≥ ··· Theo định nghĩa về thứ tự trong N×N như đã nói thì y0 ≥ y1 ≥ y2 ≥ ··· và vì thế dãy số tự nhiên yi từ một chỗ nào đó trở đi sẽ không đổi. Sau đó xi phải giảm và đến một lúc nào đó nó cũng dừng lại. Ta có thể chứng minh khẳng định tổng quát hơn. 38 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên Định lý 1.7. Nếu A và B là hai tập hợp sắp thứ tự đầy đủ, thì tích của chúng A ×B, trong đó xác định thứ tự (a1,b1) ≤ (a2,b2) ⇔ [(b1 < b2) hoặc (b1 = b2 và a1 ≤ a2)], cũng là một tập hợp sắp thứ tự đầy đủ. Chú ý: Hoàn toàn tương tự tích hữu hạn k tập hợp sắp thứ tự đầy đủ cũng là tập hợp sắp thứ tự đầy đủ. Sử dụng những định lý trên để giải những bài toán có giả thiết thao tác lặp lại như một quá trình (giống như phương pháp xuống thang ở chương 4 phần sau). Bài toán với giả thiết như một quá trình lặp vô hạn lần. Nhưng thực chất quá trình đó không thể lặp lại vô hạn lần. Ta có thể tiến hành như sau: Đưa vào một thông số tự nhiên nào đó và khẳng định rằng tại mỗi bước của quy trình thông số này giảm. Khi đó nếu xuất phát của thông số này là N, thì có thể đảm bảo được quy trình kết thúc sau N bước. Bài toán 1.21. Hai người A và B chơi một trò chơi như sau: Người A có trong tay số tiền được sắp thành từng loại. Mỗi lần chơi người A đưa cho người B một đồng tiền với điều kiện A được nhận lại một số loại đồng tiền, nhưng tổng số tiền nhận lại này có giá trị nhỏ hơn giá trị đồng tiền đã đưa. Khi những đồng tiền lớn của A không còn nữa, thì A thua cuộc. Chứng minh rằng sớm hay muộn thì B cũng thắng dù bất cứ bộ các loại tiền của A có là như thế nào. Lời giải. Giả sử A có k loại đồng tiền. Thông số cần xác định như sau: Tính tổng có bao nhiêu đồng tiền mỗi loại ở người A (n1 là số đồng tiền có giá trị nhỏ nhất, n2 là số đồng tiền có giá trị tiếp theo, ..., nk là số đồng tiền có giá trị lớn nhất). Ta chú ý rằng kết quả mỗi lần chơi bộ số (n1,n2,...,nk) giảm (theo nghĩa đưa vào thứ tự, khi ta 1.4. Chuyên đề tập hợp sắp thứ tự đầy đủ 39 so sánh bắt đầu từ phần tử cuối cùng, sau đó là phần tử trước sau cùng, ...). Vì tập hợp Nklà tập sắp thứ tự đầy đủ, nên quá trình này phải kết thúc. J Bài toán 1.22. Trên bảng ta viết dãy gồm các số 0 và 1 tùy ý. Từ dãy số này cho phép thực hiện: Thay tại vị trí nhóm 10 bằng nhóm 000...0001 (với bao nhiêu số 0 cũng được và một số 1). Chứng minh rằng cách thực hiện trên có thể thực hiện chỉ một số hữu hạn lần (nghĩa là sớm hay muộn thì ta cũng nhận được dãy số mà trong đó các số 1 đều ở bên phải và ta không thể thực hiện được nữa). Lời giải. Ta giả thiết rằng trong dãy có hai số 1. Vì những số 1 không xuất hiện thêm và cũng không biến mất trong quá trình biến đổi, nên khi xét từ phải sang trái ta ghi nhận vị trí thứ mấy của các số 1 này và ta lập ra cặp hai số tự nhiên (số thứ hai của cặp số được ghi nhận là vị trí của số 1 đầu tiên từ phải qua trái). Ví dụ: Nếu dãy ban đầu là 01010, thì lập được cặp số (4,2) (tức là số 1 ở vị trí thứ tư và số 1 ở vị trí thứ hai tính từ bên phải), còn dãy số 0100000001 là kết quả thay nhóm 10 ở cuối bằng nhóm 0000001. Khi đó ta lập được cặp số (9,1) (tức là số 1 đứng ở vị trí thứ chín và số 1 đứng ở vị trí thứ nhất tính từ bên phải). Để giải bài toán chỉ còn chứng minh hai điều: (a) Với mỗi lần biến đổi cặp số xác định như ở trên sẽ nhỏ đi (ở đây (x1, y1) < (x2, y2) ⇔ y1 < y2 hoặc y1 = y2 và x1 < x2). (b) Tập hợp những cặp số tự nhiên với cách sắp thứ tự như trên là tập hợp sắp thứ tự đầy đủ. Điều này chứng minh không khó. Nếu sự biến đổi vị trí số 1 bên phải (như ví dụ đã chỉ ra ở trên), thì số 1 này tiến dần đến đầu bên phải dù có chọn bao nhiêu số 0 đi chăng nữa. Như vậy, số thứ hai 40 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên của cặp số giảm một đơn vị, còn số thứ nhất của cặp số có thể tăng (tăng bao nhiêu đơn vị phụ thuộc vào ta cho thêm bao nhiêu số 0 vào). Nhưng theo định nghĩa thứ tự của cặp số (ta so sánh số thứ hai rồi mới so sánh số thứ nhất) sự tăng của số thứ nhất trong mỗi cặp không ảnh hưởng gì đến thứ tự. Suy ra giảm số thứ hai dẫn đến giảm thứ tự của cặp số. Nếu ta thực hiện biến đổi với số 1 bên trái, thì số 1 bên phải không thay đổi vị trí và vì thế số hạng thứ hai của cặp không thay đổi, còn số hạng thứ nhất giảm đi. Khi đó số 1 bên trái dịch về bên phải. Như vậy, khẳng định (a) được chứng minh. Bây giờ ta chứng minh tập hợp các cặp số là tập hợp sắp thứ tự đầy đủ, nghĩa là không tồn tại dãy vô hạn (a1,b1) > (a2,b2) > (a3,b3) > ··· Giả sử dãy như vậy tồn tại. Khi đó những số hạng thứ hai của cặp số tạo thành một dãy không tăng b1 ≥ b2 ≥ b3 ≥ ··· Trong dãy không tăng những số tự nhiên có phần tử nhỏ nhất. Nghĩa là đến một chỗ nào đó, chẳng hạn N, số hạng thứ hai của các cặp số đều bằng nhau: bN = bN+1 = bN+2 = ... Khi đó thứ tự của các cặp số hoàn toàn xác định theo số hạng thứ nhất và vì thế từ đó trở đi số thứ nhất phải giảm. Dãy các số tự nhiên thứ nhất giảm cũng có phần tử nhỏ nhất và đến một bước nào đó trở đi các số này đều bằng nhau. Từ đó suy ra không tồn tại dãy các cặp số giảm vô hạn. Đó là điều cần chứng minh. J 1.5. Bài tập 41 Nhiều bài toán giải bằng áp dụng nguyên lý thứ tự có thể tìm thấy trong [18] của tác giả, chương 1, ở mục: Các bài toán đơn điệu bất biến. Bạn đọc có thể kiểm tra và dùng phương pháp này để giải những bài toán đó. Vấn đề tập hợp sắp thứ tự đầy đủ có liên quan đến siêu quy nạp và siêu hồi quy trong lý thuyết tập hợp. Nội dung của các vấn đề này quá dài và cũng không nói hết được trong chủ đề này, chúng tôi dừng vấn đề này ở đây và hẹn một cuốn sách khác sẽ nói cụ thể hơn. 1.5. BÀI TẬP . 1.23. Dùng nguyên lý quy nạp toán học như định lý 1.2 để chứng minh những khẳng định sau: (a) 7n +3n−1... 9 với n ∈ N; (b) 32n+2 +8n−9... 16 với n ∈ N. . 1.24. Chứng minh bằng hai cách những khẳng định sau: (a) 4n +15n−1... 9 với n ∈ N; (b) 5n(5n +1)−6n(2n +3n)... 91 với n ∈ N∗. . 1.25. Chứng minh bằng phương pháp quy nạp theo mệnh đề các khẳng định sau: (a) (b) q 1+p2+···+√n < 3 với số nguyên dương n bất kì. q 1p2···√n < 3 với số nguyên dương n bất kì. . 1.26. Nếu k (với k > 1) không phải là số chính phương thì √k là một số vô tỉ. 42 Chương 1. Nguyên lý thứ tự trong tập số tự nhiên . 1.27. Cho M là tập khác rỗng những số nguyên dương sao cho 4x và [√x] đều nằm trong M khi mà x cũng nằm trong tập này. Chứng minh rằng M là tập số tự nhiên. . 1.28. Một tập những số nguyên khác rỗng J mà thỏa mãn hai điều kiện sau đây: (i) Nếu n và m thuộc J , thì n+m và n−m cũng nằm trong J ; (ii) Nếu n thuộc J và r là một số nguyên thì rn cũng nằm trong J . được gọi là ideal nguyên. Đặt Fm là tập hợp tất cả số nguyên mà chúng là bội nguyên của số nguyên cố định m. Chứng minh rằng Fm là một ideal nguyên. . 1.29. Cho S là tập khác rỗng những số nguyên sao cho: (i) Nếu x và y thuộc S , thì x−y cũng thuộc S ; (ii) Nếu x thuộc S , thì tất cả các bội của x cũng thuộc S . (a) Chứng minh rằng tồn tại một số nguyên d thuộc S sao cho S gồm tất cả bội số của d. (b) Chứng minh rằng d là UCLN(a,b). CHƯƠNG 2 KĨ THUẬT DÙNG PHƯƠNG PHÁP ĐẠI LƯỢNG CỰC BIÊN 2.1. Phương pháp phản chứng và đại lượng cực biên . . . . . . . . . 44 2.2. Tính toán với đại lượng cực biên . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.3. Sắp xếp phần tử theo thứ tự . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.4. Chuyên đề phương pháp xuống thang. . . . . . . . . . . . . . . . . . . . . . 66 2.4.1. Lịch sử của phương pháp . . . . . . . . . . . . . . . . . . . . 66 2.4.2. Phương pháp xuống thang trong số học . . . . . . 68 2.4.3. Phương pháp xuống thang trong hình học. . . . 72 2.5. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Chương trước ta đã sử dụng nguyên lý thứ tự và nguyên lý quy nạp toán học để giải toán. Chương này ta điểm lại các kĩ thuật sử dụng đại lượng cực biên làm mấu chốt trong khi giải. Đó là phương pháp phản chứng, phương pháp tính toán với đại lượng cực biên, phương pháp sắp xếp thứ tự các đại lượng đã cho trong bài toán. 44 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên 2.1. PHƯƠNG PHÁP PHẢN CHỨNG VÀ ĐẠI LƯỢNG CỰC BIÊN Phương pháp chứng minh bằng phản chứng là lý luận dựa vào mệnh đề phủ định của mệnh đề đã cho và sau đó tìm ra sự mâu thuẫn với giả thiết hoặc các định lý đã biết. Những đại lượng cực biên là mấu chốt của lý luận phản chứng và dẫn tới sự mâu thuẫn. Do đó đại lượng cực biên và phương pháp phản chứng được ứng dụng rất nhiều để giải các bài toán khó. Trong [13] tác giả có bàn đến vấn đề này. Trong tiết này ta xét nhiều bài toán khác nữa. Bài toán 2.1. Trên một đường thẳng cho tập điểm M sao cho mỗi điểm của M là trung điểm của một đoạn thẳng được nối bởi hai điểm cũng thuộc M. Chứng minh rằng M có vô hạn điểm. Lời giải. Ta sử dụng phương pháp đại lượng cực biên bằng cách chọn các phần tử cực biên theo hai cách sau: 1. Cách thứ nhất: Giả sử tập hợp M là hữu hạn, thì trong số những điểm của tập M có hai điểm cuối về bên trái và cuối về bên phải. Ta xét một trong những điểm cuối này, ví dụ xét điểm A là điểm cuối về phía bên trái. Khi đó điểm A không thể là trung điểm của đoạn thẳng nối hai điểm khác thuộc M; nghĩa là A không thuộc M, điều này mâu thuẫn với cách chọn A. Suy ra M không thể là tập hữu hạn. 2. Cách thứ hai: Giả sử tập M là hữu hạn. Ta xét tất cả những đoạn thẳng nối hai điểm thuộc M. Số những đoạn thẳng được nối là hữu hạn, nên ta có thể chọn được đoạn thẳng BC có độ dài lớn nhất. Rõ ràng phía ngoài đoạn thẳng BC không có điểm nào thuộc M, nếu ngược lại thì tồn tại một đoạn thẳng lớn hơn đoạn thẳng đã chọn BC. Như vậy tất cả các điểm của tập M nằm trong đoạn BC, 2.1. Phương pháp phản chứng và đại lượng cực biên 45 điều này có nghĩa là B và C không thỏa mãn điều kiện của những điểm thuộc M. Điều vô lý này chỉ ra rằng tập M không thể là tập hữu hạn. Đó là điều cần chứng minh. J Có thể áp dụng ý tưởng trên cho bài toán trong mặt phẳng. Bài toán 2.2. Trên mặt phẳng cho tập điểm M sao cho mỗi điểm của M đều là trung điểm của một đoạn thẳng nối hai điểm nào đó cũng thuộc M. Chứng minh rằng M có vô hạn điểm. Lời giải. Tương tự như bài trước ta có thể chứng minh bằng hai cách. Nhưng ở đây d ta chỉ thể hiện cách thứ hai và cũng có đôi chút khác C A′ m B d m biệt. Giả sử M là tập hữu hạn điểm. Khi đó những đoạn thẳng nối hai điểm A c Hình 2.1 D bất kì thuộc M là hữu hạn. Vậy ta có thể chọn được đoạn thẳng có độ dài lớn nhất. Giả sử đoạn thẳng có độ dài lớn nhất đó được nối bởi hai điểm A và B thuộc M. Nhưng điểm B là trung điểm của đoạn thẳng CD nào đó mà C và D đều thuộc M (Hình 2.1). Khi đó dễ chứng minh được rằng hoặc là AD hoặc là AC lớn hơn AB (như gợi ý của hình vẽ ta chứng minh được trong một tam giác thì đường trung tuyến m nhỏ hơn trung bình cộng hai cạnh kề nó là c và d). Điều này mâu thuẫn với cách chọn đoạn thẳng AB có độ dài lớn nhất. Suy ra M là tập vô hạn điểm. J Bài toán 2.3. Trên mỗi ô của bàn cờ có vô hạn ô người ta viết một số nguyên dương sao cho mỗi số này là trung bình cộng của các số ở bốn 46 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên ô bên cạnh: phía trên, phía dưới, bên phải và bên trái. Chứng minh rằng tất cả các số được viết trên bàn cờ đều bằng nhau. Lời giải. Theo nguyên lý thứ tự thì mọi tập con khác rỗng của tập số tự nhiên đều có số nhỏ nhất, nên trong các số được viết trên bàn cờ có một số nhỏ nhất m. Nếu các số a,b, c,d là những số ở các ô bên cạnh ô số m thì m =a+b+c+d 4, nghĩa là a+b+c+d = 4m. Mặt khác, vì m là số nhỏ nhất nên a ≥ m, b ≥ m, c ≥ m, d ≥ m. Giả sử ít nhất có một trong các số a,b, c,d thật sự lớn hơn m. Khi đó a + b + c + d > 4m, điều này trái với đẳng thức trên. Như vậy a = b = c = d = m. Như vậy nếu một ô người ta viết số m, thì những ô bên cạnh nó cũng được viết số m. Từ đó suy ra các ô nằm trên hàng ngang chứa ô viết số m, đều viết số m. Nhưng mọi cột đều giao với hàng ngang này nên tất cả các ô trên các cột đều viết số m. Do đó suy ra tất cả các ô trên bàn cờ đều viết số m. J Bài toán 2.4. Trên một bàn cờ vuông cỡ n×n ô vuông, người ta đặt những quân cờ theo nguyên tắc sau: Nếu một ô nào đó còn trống, thì tổng những quân cờ, đứng cùng hàng và đứng cùng cột với ô đó không nhỏ hơn n. Chứng minh rằng trên bàn cờ đó có không ít hơn n2 2quân cờ. Lời giải. Trên bàn cờ gồm n hàng và n cột. Ta chọn hàng hoặc cột có số quân cờ ít nhất. Giả sử ta chọn là hàng (trong trường hợp ngược lại thì ta xoay bàn cờ 90◦sẽ thành hàng). Số quân cờ trong hàng này ta ký hiệu là k. Nếu k ≥n2, thì trên mỗi hàng trong số n hàng số quân cờ đều không nhỏ hơn n2, như 2.1. Phương pháp phản chứng và đại lượng cực biên 47 vậy thì trên bàn cờ sẽ có số quân cờ không nhỏ hơn n22. Giả sử k 260. J Bài toán 2.12. Trong một lớp học có ít nhất hai bạn quen nhau. Biết rằng nếu hai bạn có cùng một số lượng người quen thì không có người quen chung. Chứng minh rằng trong lớp có bạn chỉ quen đúng một người. Lời giải. Vì số người trong lớp hữu hạn nên có thể tìm được một bạn A có số người quen nhiều nhất. Giả sử A quen A1,A2,...,Ak. Giả sử mỗi Ailại quen ni người khác (1 ≤ i ≤ k). Theo giả thiết đã cho hai người có số lượng người quen bằng nhau thì không có người quen chung, mà ở đây Ai,Aj (1 ≤ i < j ≤ k) cùng quen A, nên suy ra các số n1,n2,...,nk đôi một khác nhau. 54 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên Mặt khác 1 ≤ ni ≤ k với mọi 1 ≤ i ≤ k, suy ra tồn tại ni = 1. J Bài toán 2.13. Có một số người đến dự cuộc họp. Người ta nhận thấy rằng nếu hai người nào đó trong họ mà quen với nhau thì hai người này không cùng quen với một người thứ ba. Còn nếu hai người trong họ mà không quen nhau thì họ cùng quen với đúng hai người khác. Chứng minh rằng trong cuộc họp này tất cả mọi người đều có số người quen bằng nhau. A1 Lời giải. Vì số người là hữu hạn nên ta có thể chọn ra một người A A quen nhiều người nhất. Ta chứng minh mọi người quen A cũng có số người quen như A. Giả sử các người quen của A là A1,A2,...,An. Suy ra các Ai (1 ≤ i ≤ n) đôi một không quen nhau. Vì A1,A2 cùng A2 A3 Hình 2.4 B1 B2 quen A nên A1,A2 cùng quen B1 khác A (Hình 2.4). Vì A1,A3 cùng quen A nên A1,A3 cùng quen B2 khác A. Do A,B1 không quen nhau nên B1 và A có đúng hai người quen chung là A1 và A2. Do A,B2 không quen nhau nên B2 và A có đúng hai người quen chung là A1 và A3 suy ra B2 khác B1. Tương tự A1,A4 cùng quen B3 (B3 khác B1 và B2), . . . , A1,An cùng quen Bn−1 (Bn−1 khác B1,B2,...,Bn−2). Vậy A1 có n người quen là A,B1,...,Bn−1. Tương tự ta chứng minh cho mọi người trong cuộc họp đều có n người quen. J Bài toán 2.14. Sau một giải đấu bóng bàn theo thể thức vòng tròn (một đấu thủ chơi với mọi đấu thủ khác), mỗi đấu thủ được gọi tên những người thua mình và những người thua những người thua 2.2. Tính toán với đại lượng cực biên 55 mình. Chứng minh rằng tồn tại ít nhất một đấu thủ được gọi tên tất cả các đấu thủ còn lại. Lời giải. Xét đấu thủ A được gọi tên nhiều đấu thủ nhất. Ta chứng minh A được gọi tên tất cả các đấu thủ còn lại. Giả sử ngược lại A được gọi tên các đấu thủ A1,A2,...,An và tồn tại đấu thủ B không được A gọi tên. Khi đó đấu thủ B được gọi tên tất cả A,A1,...,An (mọi đấu thủ đều giao đấu với nhau) trái với cách chọn A được gọi tên nhiều đấu thủ nhất. J Bài toán 2.15. Một đất nước có 100 sân bay mà khoảng cách giữa hai sân bay đều khác nhau. Mỗi máy bay cất cánh từ một sân bay và bay đến sân bay gần nhất. Chứng minh rằng trên bất kì sân bay nào cũng không thể có quá 5 máy bay bay đến. Lời giải. Giả sử có các máy bay bay từ các sân bay A1,A2,...,An (n ≤ 99) đến sân bay O thì một trong các góc A\iOAj không lớn hơn 360◦ nvới i, j ∈ {1,2,...,99}. Mặt khác, nếu các máy bay bay từ sân bay Ai và Aj đến sân bay O thì AiAjlà cạnh lớn nhất trong các cạnh của tam giác AiOAj, do đó A\iOAj > 60◦. Từ đó suy ra 360◦ n≥ A\iOAj > 60◦. Vì vậy n < 6. J Bài toán 2.16. Trên một đường tròn có ba mươi số, mỗi số bằng giá trị tuyệt đối của hiệu hai số đứng sau nó theo chiều kim đồng hồ. Biết rằng tổng của tất cả các số bằng 1. Hãy tìm các số trên đường tròn. Lời giải. Vì mỗi số là giá trị tuyệt đối của hiệu hai số nên tất cả các số không âm. Giả sử số lớn nhất (hoặc một trong những số lớn 56 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên nhất) trong các số này là A và ký hiệu những số trên đường tròn là a1,a2,...,a30 theo chiều kim đồng hồ bắt đầu bằng số lớn nhất này (Hình 2.5). Như vậy, a1 = A. Theo giả thiết a1 = |a2 − a3|. Vì các số a2 và a3 không âm và không lớn hơn A, nên đẳng thức a1 = |a2 − a3| chỉ xảy ra khi một trong hai số a2, a3 bằng A và số còn lại bằng 0. Do đó ta có hai trường hợp hoặc là a2 = A hoặc là a2 = 0. Trường hợp thứ nhất: Đã biết a30 a1 = A a2 a3 Hình 2.5 a1 = a2 = A, ta tính được a3 = 0, a4 = A,a5 = A,a6 = 0,... các số lặp lại theo chu kì 3 số hạng. Trường hợp thứ hai: Đã biết a1 = A,a2 = 0, ta tính được a3 = A,a4 = A,a5 = 0,a6 = A,... các số cũng lặp lại theo chu kì 3 số hạng. Như vậy, cả hai trường hợp trên đường tròn các số lặp lại theo chu kì 3 số hạng với A,A,0. Do đó trong ba mươi số có mười số 0, còn hai mươi số bằng nhau và đều bằng A. Theo giả thiết của bài toán thì tổng tất cả các số trên đường tròn bằng 1. Ta có 20.A = 1, từ đó suy ra A =120. Kết quả, trên đường tròn có mười số 0 và hai mươi số bằng 120. J Bài toán 2.17. Trên mặt phẳng cho n điểm không thẳng hàng. Chứng minh rằng tồn tại một đường tròn đi qua ba trong số n điểm đã cho, mà đường tròn này không chứa bất kì điểm nào trong số những điểm còn lại. 2.2. Tính toán với đại lượng cực biên 57 Lời giải. Nối hai điểm bất kì trong số n điểm đã cho bằng một đoạn thẳng. Vì có hữu hạn điểm nên các đoạn thẳng tạo ra là hữu hạn. Gọi AB là đoạn thẳng có độ dài nhỏ nhất với A và B là hai điểm đã cho. Gọi C là điểm trong số các điểm còn lại thỏa mãn góc ACB lớn nhất trong số các góc nhìn từ n − 2 điểm khác đối với hai điểm A và B. Xét tam giác ABC. Ta có đường tròn ngoại tiếp tam giác ABC không chứa điểm nào trong số những điểm đã cho còn lại. J Bài toán 2.18. Trong mặt phẳng kẻ 1992 đường thẳng đôi một cắt nhau sao cho không có ba đường nào đồng quy. Tam giác tạo bởi ba đường thẳng trong số các đường thẳng đã cho gọi là "tam giác xanh" nếu nó không bị đường thẳng nào trong số các đường thẳng còn lại cắt ngang. a) Chứng minh rằng số tam giác xanh không ít hơn 664; b) Chứng minh rằng số tam giác xanh không ít hơn 1328. Lời giải. a) Lấy đường thẳng d bất kì trong số các đường thẳng đã cho. Trong các khoảng cách từ giao điểm của các đường thẳng còn lại đến đường thẳng d luôn tồn tại một giao điểm gần d nhất, đó chính là đỉnh của một tam giác xanh (hai đỉnh còn lại nằm trên d). Như vậy ứng với mỗi đường thẳng ta có ít nhất một tam giác xanh, suy ra ứng với 1992 đường thẳng, ta có ít nhất 1992 tam giác xanh. Mỗi tam giác xanh trong số đó được tính nhiều nhất 3 lần. Vậy có ít nhất 1992 : 3 = 664 tam giác xanh khác nhau. b) Từ nhận xét câu a) ta suy ra nếu về hai phía của d đều có các giao điểm của các đường thẳng khác thì có ít nhất hai tam giác xanh về hai phía của d. Ta sẽ chứng minh có nhiều nhất hai đường thẳng mà tất cả các 58 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên giao điểm của các đường thẳng khác nằm về cùng một phía so với đường thẳng đó. Giả sử trái lại có ít nhất ba đường thẳng d1,d2,d3 như vậy. Xét d4, gọi các điểm M1,M2,M3 thứ tự là giao điểm của d4 với d1,d2,d3. Giả sử M2 nằm giữa M1,M3 suy ra M1 và M3 nằm ở hai phía của d2, điều này mâu thuẫn với giả sử. Như vậy ứng với 1992 đường thẳng thì có ít nhất 1990.2+2 = 3982 tam giác xanh. Mỗi tam giác xanh được tính nhiều nhất 3 lần. Vậy có ít nhất 3982 3 = 1328 tam giác xanh khác nhau. J Bài toán 2.19. Trong một buổi dạ hội, mỗi nữ sinh đều nhảy với ít nhất một nam sinh và không có nam sinh nào nhảy với tất cả nữ sinh. Chứng minh rằng có thể tìm được một nhóm gồm 2 nam sinh và 2 nữ sinh sao cho mỗi người trong bọn họ chỉ nhảy với một người khác giới cùng nhóm. Lời giải. Ta chia tất cả nam sinh thành những nhóm theo tiêu chuẩn họ đã có thể nhảy với cùng số lượng nữ sinh (nghĩa là mỗi người trong nhóm đều có số bạn nhảy nữ sinh bằng nhau). Giả sử F1 là một trong những nam sinh đã nhảy với nhiều nữ sinh nhất. Vì theo giả thiết F1 không nhảy với tất cả nữ sinh, nên tồn tại hữu hạn số nữ sinh không nhảy với F1, ta chọn trong đó một nữ sinh L1. Nhưng vì mỗi nữ sinh đều nhảy với ít nhất một nam sinh, vì thế tồn tại một nam sinh F2 nhảy với L1. Nam sinh F1 đã được chọn sao cho số nữ sinh không nhảy với F2 không nhỏ hơn số nữ sinh nhảy với F1. Từ đây suy ra F2 không nhảy với tất cả số nữ sinh nhảy với F1: Trường hợp ngược lại, số nữ sinh nhảy với F2 sẽ lớn hơn số nữ sinh nhảy với F1; vì F2 nhảy với L1, còn F1 không nhảy với L1. Như vậy tồn tại nữ sinh L2 nhảy với F1, nhưng 2.2. Tính toán với đại lượng cực biên 59 không nhảy với F2. Cặp nam sinh F1,F2 và cặp nữ sinh L1,L2 tạo thành một bộ bốn tham gia dạ hội, thỏa mãn các điều kiện của bài toán, vì cặp F1,L1, cũng như cặp F2,L2 không nhảy với nhau mà chỉ có F1 nhảy với L2 và F2 nhảy với L1. J Cuối cùng dựa vào tính toán trên các đại lượng cực biên ta có thể chứng minh "bất đẳng thức giữa trung bình cộng và trung bình nhân" của một dãy số không âm. Định lý này cũng được chứng minh như một hệ quả ở chương 6 về hàm lồi. Định lý 2.1 (Bất đẳng thức giữa trung bình cộng và trung bình nhân). Nếu x1, x2,..., xn là các số không âm, thì n≥√n x1x2 ... xn, x1 +x2 +···+xn đẳng thức xảy ra khi và chỉ khi x1 = x2 = ... = xn. Chứng minh. Ta có thể giả thiết rằng xi > 0 với mọi i = 1,2,...,n, vì nếu có một số nào đó trong chúng bằng 0 thì bất đẳng thức hiển nhiên đúng. Ta xét trung bình nhân (x1x2 ... xn)1n và trung bình cộng x1 +x2 +···+xn n. Nếu tất cả xi không bằng nhau thì ta thay số lớn nhất xM và số nhỏ nhất xm bằng cùng một số 12(xM +xm). Khi đó tổng của hai số mới thay bằng 1 2(xM +xm) + 12(xM +xm) = xM +xm và tích của chúng là 1 2(xM +xm) 2 > xMxm. Kết quả của sự thay thế này là trung bình nhân tăng trong khi trung bình cộng không thay đổi gì. Nếu tập hợp n số mới tất cả không bằng nhau, thì ta lại lặp 60 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên lại quá trình trên. Tại mỗi giai đoạn của quá trình, trung bình nhân đều tăng thực sự và trung bình cộng không thay đổi gì. Đến lúc tất cả các số trở thành bằng nhau, thì hai trung bình cộng và nhân này trùng nhau. Do đó trung bình nhân luôn nhỏ hơn hoặc bằng trung bình cộng, đẳng thức xảy ra khi và chỉ khi tất cả các số đều bằng nhau. Ta có thể lấy ví dụ về quá trình này, xét trường hợp x1 = 2, x2 = 3, x3 = 8, x4 = 11. Quá trình tiến hành được liệt kê theo dãy sau đây: {2,3,8,11} → 2,3,8,132 → 132,112,112,132 → {12,12,12,12}. 13 Trung bình nhân của tập số tương ứng tăng đến 12; trung bình cộng luôn luôn cố định là 12. J 2.3. SẮP XẾP PHẦN TỬ THEO THỨ TỰ Một kĩ thuật giải toán là sắp xếp thứ tự những phần tử trong bài toán. Khi sắp xếp thứ tự của hữu hạn các phần tử trong bài toán ta đã xác định được những phần tử nhỏ nhất hoặc lớn nhất. Nhờ phần tử nhỏ nhất và lớn nhất này ta có thể giải được bài toán. Bài toán 2.20. Cho 7 số nguyên dương khác nhau sao cho tổng của chúng bằng 100. Chứng minh rằng có ba số mà tổng của chúng ít nhất là 50. Lời giải. Giả sử 7 số nguyên dương được sắp xếp theo thứ tự a < b < c < d < e < f < g. Ta sẽ chứng minh rằng e+ f +g ≥ 50. Nếu e > 15, thì suy trực tiếp e + f + g ≥ 16 + 17 + 18 = 51, điều cần chứng minh. 2.3. Sắp xếp phần tử theo thứ tự 61 Nếu e ≤ 15 thì a+b+c+d ≤ 14+13+12+11 = 50, vì thế e+ f +g = 100−a−b−c−d ≥ 50, điều khẳng định cũng đúng. J Bài toán 2.21. Chứng minh rằng các chữ số của một số có sáu chữ số có thể hoán vị sao cho số nhận được có tính chất: Tổng ba chữ số đầu tiên của nó khác với tổng ba chữ số còn lại nhiều nhất là 9. Lời giải. Cho a,b, c,d, e, f là sáu chữ số của số đã cho sắp xếp theo thứ tự tăng. Chọn f, c,a làm ba chữ số đầu tiên của số mới và e,d,b làm ba chữ số cuối cùng. Khi đó f +c+a−e−d −b = (f −e) + (c−d) + (a−b) ≤ f −e ≤ 9, vì c−d và a−b là số âm hoặc bằng không. Tương tự, e+d +b− f −c−a = (e− f) + (b−c) + (d −a) ≤ d −a ≤ 9. Vì thế số f caedb thỏa mãn tính chất cần thiết. J Bài toán 2.22. Chứng minh rằng nếu 2n + 1 số thực có tính chất là tổng của n số bất kì trong chúng nhỏ hơn tổng của n+1 số còn lại, thì tất cả những số này là số dương. Lời giải. Ta sắp xếp 2n+1 số thực này theo thứ tự tăng a1 ≤ a2 ≤ ··· ≤ a2n+1. Theo giả thiết ta có an+2 +an+3 +···+a2n+1 < a1 +a2 +···+an+1. Điều này kéo theo a1 > (an+2 −a2) + (an+3 −a3) +···+ (a2n+1 −an+1). Vì tất cả hiệu trong dấu ngoặc tròn đều không âm, suy ra a1 > 0, đó là điều cần chứng minh. J Bài toán 2.23. Cho 7 số nguyên dương khác nhau mà mỗi số không vượt quá 1706. Chứng minh rằng tồn tại ba số trong chúng, giả sử là a,b, c, sao cho a < b+c < 4a. 62 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên Lời giải. Ta sắp xếp 7 số theo thứ tự tăng 1 ≤ a1 < a2 < ··· < a7 ≤ 1706. Nếu ai+1 < 4ai − a1 với một số i nào đó thuộc {2,3,...,6}, thì ai < a1 +ai+1 < 4ai và ta đã chứng minh xong. Giả sử ngược lại, ai+1 ≥ 4ai −a1 với mọi i = 2,3,...,6. Khi đó a3 ≥ 4a2 −a1 ≥ 4(a1 +1)−a1 = 3a1 +4, a4 ≥ 4a3 −a1 ≥ 4(3a1 +4)−a1 = 11a1 +16, a5 ≥ 4a4 −a1 ≥ 4(11a1 +16)−a1 = 43a1 +64, a6 ≥ 4a5 −a1 ≥ 4(43a1 +64)−a1 = 171a1 +256, a7 ≥ 4a6 −a1 ≥ 4(171a1 +256)−a1 = 683a1 +1024 ≥ 1707, điều này mâu thuẫn với giả thiết. J Bài toán 2.24. Cho a là số nhỏ nhất và A là số lớn nhất của n số nguyên dương khác nhau. Chứng minh rằng bội chung nhỏ nhất của những số này lớn hơn hoặc bằng na và ước chung lớn nhất của chúng nhỏ hơn hoặc bằng An. Lời giải. Ta sắp xếp n số nguyên dương khác nhau như sau: a = a1 < a2 < a3 < ··· < an = A và cho m là bội số chung nhỏ nhất của chúng, d là ước số chung lớn nhất của chúng. Khi đó an 2). Chứng minh rằng tồn tại ba hiệu ai −aj (i, j ∈ {1,2,...,2n} và i 6= j) bằng nhau. Lời giải. Ta có thể giả thiết rằng a1 < a2 < a3 < ··· < a2n. Ta xét hiệu a2 − a1,a3 − a2,...,a2n − a2n−1. Giả sử không có ba hiệu nào bằng nhau, thì chỉ có nhiều nhất hai hiệu bằng nhau và có bất đẳng thức (a2 −a1) + (a3 −a2) +···+ (a2n −a2n−1) ≥ 1+1+2+2+···+ (n−1) + (n−1) +n = n2. Nghĩa là a2n − a1 ≥ n2. Mặt khác, theo giả thiết của bài toán ta có đánh giá a2n −a1 ≤ n2 −1, hai điều này mâu thuẫn nhau. J Bài toán 2.26. Cho 4n điểm trên mặt phẳng trong đó không có ba điểm nào thẳng hàng. Chứng minh rằng người ta có thể tạo ra n tứ giác đôi một không giao nhau (không nhất thiết phải là tứ giác lồi) với các đỉnh là những điểm đã cho. Lời giải. Tồn tại hữu hạn những đường thẳng nối các cặp điểm đã cho. Ta chọn đường thẳng ` không song song với bất cứ đường thẳng nối giữa hai điểm nào sao cho tất cả các điểm nằm về một phía của `. Ta thực hiện di chuyển ` song song với chính nó. ` sẽ gặp mỗi điểm đã cho một lần. Ta gán nhãn cho những điểm này A1,A2,...,A4n theo thứ tự đếm được. Khi đó A1A2A3A4, A5A6A7A8, . . . , A4n−3A4n−2A4n−1A4n là n tứ giác đôi một không giao nhau. J Bài toán 2.27. Cho 2n + 3 điểm trong mặt phẳng trong đó không có ba điểm nào thẳng hàng và không có bốn điểm nào nằm trên cùng 64 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên đường tròn. Chứng minh rằng tồn tại đường tròn đi qua ba điểm trong đó sao cho đúng n điểm nằm trong đường tròn và n điểm nằm ngoài nó. Lời giải. Từ 2n + 3 điểm ta chọn hai điểm A và B sao cho đường thẳng đi qua hai điểm này là bờ của nửa mặt phẳng chứa tất cả những điểm còn lại. Ta vẽ 2n+1 đường tròn đi qua hai điểm đã chọn và điểm thứ ba trong 2n + 1 điểm còn lại. Gọi U1,U2,..., U2n+1 là A B U1 U2 U3 các hình viên phân chứa A,B và điểm thứ ba trong 2n + 1 điểm còn lại. Ta thấy các viên phân này lồng nhau (Hình 2.6). Hình 2.6 Giả sử U1 ⊂ U2 ⊂ ··· ⊂ U2n+1. Khi đó viên phân Un+1 chứa đúng n điểm ở bên trong nó. Đường tròn của viên phân Un+1 sẽ thỏa mãn yêu cầu bài toán. J Bài toán 2.28. Cho 69 số nguyên dương khác nhau, mỗi số không vượt quá 100. Chứng minh rằng người ta có thể chọn được 4 số a,b, c,d sao cho a < b < c và a+b+c = d. Mệnh đề còn đúng cho 68 số không? Lời giải. Những số đã cho có thể sắp xếp thành 1 ≤ a1 < a2 < ··· < a69 ≤ 100. Hiển nhiên a1 ≤ 32. Ta xét dãy a3 +a1 < a4 +a1 < ··· < a69 +a1 và a3 −a2 < a4 −a2 < ··· < a69 −a2. Mỗi số hạng của hai dãy trên là một số nguyên dương không vượt quá 100 + 32 = 132. Từ hai dãy này gộp lại có 67 + 67 = 134 số 2.3. Sắp xếp phần tử theo thứ tự 65 nguyên dương, do đó tồn tại hai chỉ số i, j ∈ {3,4,...,69} sao cho ai +a1 = aj −a2 (nguyên lý Dirichlet). Ta có a1 < a2 < ai và a1 +a2 +ai = aj. Vậy, ta chọn 4 số a1,a2,ai,aj thỏa mãn bài toán. Mệnh đề không còn đúng cho trường hợp 68 số nguyên dương khác nhau. Ví dụ: Tập hợp {33,34,35,...,100} có 33 + 34 + 35 > 100 nên không chọn được số nào thỏa mãn bài toán. J Bài toán 2.29. Chứng minh rằng từ 25 số nguyên dương khác nhau người ta có thể chọn được hai số mà tổng và hiệu của chúng không trùng với bất kì số nào trong 23 số còn lại. Lời giải. Giả sử tồn tại 25 số sao cho có thể chọn được hai số bất kì trong chúng có tổng hoặc hiệu trùng với một số trong 23 số còn lại. Ta sắp xếp chúng theo thứ tự tăng dần như sau: 0 < x1 < x2 < ··· < x25. Vì x25 là số lớn nhất nên tổng x25 +xk không nằm trong tập hợp số đã cho với k ∈ {1,2,...,12}. Như vậy hiệu của chúng phải trùng với một số trong 23 số còn lại và ta có thể chỉ có x25 −x1 = x24, x25 −x2 = x23, . . . , x25 −x12 = x13. Từ đó suy ra với k > 1 thì x24 +xk > x25, do đó x24 −xk nằm trong tập hợp các số còn lại. Vì x2 +x23 = x25 suy ra x24 −x2 < x23, nghĩa là x24 −x2 ≤ x22. Tương tự, ta thiết lập được các bất đẳng thức x24 −x2 ≤ x22, x24 −x3 ≤ x21,..., x24 −x12 ≤ x11,..., x24 −x22 ≤ x1. Suy ra tổng và hiệu của hai số x24 và x23 không trùng với số nào trong 23 số còn lại. Điều này mâu thuẫn với giả thiết ban đầu về những số này. J 66 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên 2.4. CHUYÊN ĐỀ PHƯƠNG PHÁP XUỐNG THANG Một phương pháp giải toán phát sinh từ nguyên lý thứ tự - đó là phương pháp xuống thang. 2.4.1. Lịch sử của phương pháp Nhà toán học lớn P. Fermat (1601 - 1655) viết rằng "Do những phương pháp bình thuờng đã có trong các sách không đủ để chứng minh những mệnh đề khó và quan trọng, vì thế tôi đã hoàn thiện một cách đặc biệt để giải quyết những bài toán này. Tôi gọi cách chứng minh đặc biệt này là xuống thang không xác định hoặc là xuống thang đến vô cùng"2. Ban đầu Fermat chỉ dùng phương pháp này chứng minh cho những mệnh đề phủ định. Ví dụ như "Không tồn tại một tam giác vuông có số đo các cạnh là những số tự nhiên, mà số đo diện tích của nó là một số chính phương". Để chứng minh mệnh đề này Fermat đã dùng phương pháp sau: Nếu tồn tại một tam giác có số đo các cạnh là những số tự nhiên mà số đo diện tích của nó là một số chính phương, thì tồn tại một tam giác khác nhỏ hơn tam giác ban đầu và có cùng tính chất. Nếu tam giác thứ hai nhỏ hơn tam giác ban đầu và có cùng tính chất, thì lý luận tương tự ta nhận được tam giác thứ ba nhỏ hơn tam giác thứ hai và cũng có cùng tính chất, quá trình này tiếp tục tìm được các tam giác thứ tư, thứ năm, ... giảm đến vô cùng. Số đo một cạnh của tam giác vuông xuất phát là một số tự nhiên, mỗi bước thực hiện trên số đo cạnh này giảm thành số tự nhiên nhỏ hơn, tạo ra một dãy số tự nhiên giảm, nhưng một dãy số tự nhiên giảm thực sự không thể giảm vô hạn lần. Từ đó suy ra 2trong cuốn Oeuvres, tập II, trang 431 của P. Fermat 2.4. Chuyên đề phương pháp xuống thang 67 không tồn tại một tam giác vuông có số đo các cạnh là những số tự nhiên, mà số đo diện tích của nó là một số chính phương. Sau đó Fermat có nói rằng (sau một thời gian dài suy nghĩ) đã có thể ứng dụng phương pháp này vào việc chứng minh những mệnh đề khẳng định. Ví dụ như: "Mọi số nguyên tố dạng 4n+1 đều biểu diễn thành tổng của hai số chính phương". Nhưng để ứng dụng phương pháp này vào việc chứng minh những mệnh đề khác như: "Mọi số có thể biểu diễn thành tổng của không quá bốn số chính phương", thì Fermat không để lại chi tiết áp dụng phương pháp này như thế nào. Hơn nữa, hàng loạt các định lý của Fermat được chứng minh bằng phương pháp này cũng không để lại tính toán chi tiết. Trong số đó có định lý lớn Fermat cho trường hợp n = 3. Sau này Euler đã áp dụng có kết quả phương pháp này vào bài toán giải phương trình vô định và từ đó việc chứng minh định lý lớn Fermat cho n = 3 được phục hồi. Fermat khẳng định rằng phương pháp này là của mình đưa ra lần đầu tiên và trước đó không ai biết phương pháp này. Nhưng ta nhớ lại rằng những cố gắng chứng minh không thể phân tích một lập phương của số nguyên thành tổng lập phương của hai số nguyên, được nghiên cứu khoảng năm 1000 ở phương đông với các nhà toán học Ả Rập đã có nói tới phương pháp này. Phương pháp xuống thang thời hiện đại giữ một vai trò quan trọng trong giải tích Diophant với những công trình của J. H. Poincaré3 và A. Baile. Ngày nay phương pháp này vẫn còn được ứng dụng trong lý thuyết số của toán học. 3Jules Henri Poincaré (1854-1912): Nhà toán học người Pháp 68 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên 2.4.2. Phương pháp xuống thang trong số học Nội dung cơ bản của phương pháp xuống thang thực hiện qua các bước: 1. Giả sử bài toán có nghiệm (hoặc những đại lượng đã thỏa mãn điều kiện bài toán); 2. Từ giả thiết đã cho của bài toán ta lại xây dựng được đại lượng giảm thực sự cũng thỏa mãn điều kiện bài toán đã cho. Một cách lặp lại như vậy ta xây dựng được một dãy đại lượng giảm thực sự. 3. Từ dãy giảm vô hạn trên suy ra điều vô lý vì dãy số của ta xây dựng không thể giảm vô hạn được, mà chỉ hữu hạn (có thể áp dụng nguyên lý thứ tự, các đại lượng bị chặn dưới, ...). Vậy điều giả sử là sai và suy ra kết luận của bài toán. Để hiểu phương pháp xuống thang ta chứng minh lại bài toán ở ngay đầu cuốn sách này, nhưng với nội dung mới. Bài toán 2.30. Chứng minh rằng √3 là một số vô tỉ. Lời giải. Giả sử √3 =rs, ở đây r và s là những số nguyên dương. Khi đó 3s2 = r2. (2.1) Như vậy vế phải của (2.1) là một số chia hết cho 3, suy ra r2chia hết cho 3. Điều này nghĩa là r chia hết cho 3 (vì r không chia hết cho 3, thì khi đó r2cũng không chia hết cho 3, điều này vô lý). Ta đặt r = 3r1 (r1 ∈ N∗) và thay vào (2.1) ta nhận được 3s2 = 9r21, nghĩa là s2 = 3r21. (2.2) Lý luận tương tự cho phương trình (2.2) tìm được s = 3s1 (s1 ∈ N∗), sau đó thay vào (2.2) cho kết quả 3s21 = r21. (2.3) 2.4. Chuyên đề phương pháp xuống thang 69 Từ r = 3r1,s = 3s1 ta suy ra đẳng thức r > r1. Phương trình (2.3) tương tự như phương trình (2.1). Ta lại sử dụng cùng lý luận cho phương trình (2.3) ta nhận được dãy số nguyên dương vô hạn r > r1 > r2 > ··· > rn > ··· > 0. (2.4) Điều kiện (2.4) là vô lý, vì tập hợp những số tự nhiên dương nhỏ hơn r là hữu hạn. Điều vô lý này chỉ ra rằng phương trình (2.1) không có nghiệm nguyên dương, vậy √3 là một số vô tỉ. J Bài toán 2.31. Chứng minh rằng phương trình 6(x2 +y2) = z2 +t2(2.5) không có nghiệm nguyên dương. Lời giải. Giả sử phương trình (2.5) có nghiệm nguyên dương, (x0, y0,z0,t0). Do đó 6(x20 +y20) = z20 +t20. (2.6) Vế phải của (2.6) chia hết cho 3, nghĩa là z20 +t20chia hết cho 3. Dễ chứng minh được rằng điều này xảy ra khi và chỉ khi z0 và t0 đều chia hết cho 3. Ta đặt z0 = 3z1 và t0 = 3t1 (t1,z1 ∈ N∗). Vì thế z0 > z1 và t0 > t1, suy ra z20 +t20 > z21 +t21. Thay những giá trị này vào phương trình (2.6), ta nhận được 2(x20 +y20) = 3(z21 +t21). Vế trái của phương trình trên chia hết cho 3, suy ra x20 +y20chia hết cho 3. Tương tự phần trên x0 và y0 đều chia hết cho 3. Ta đặt x0 = 3x1 và y0 = 3y1 (x1, y1 ∈ N∗). Khi đó ta nhận được phương trình 6(x21 +y21) = z21 +t21. Phương trình này giống như phương trình (2.6), chỉ có khác chỉ số. Như vậy ta lặp lại quy trình xây dựng nghiệm như phương trình 70 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên (2.6), cho nghiệm x1 =x03, y1 =y03, z1 =z03, t1 =t03và tạo ra dãy số nguyên dương vô hạn t0 > t1 > t2 > ··· > 0. Điều này vô lý vì dãy số tự nhiên nhỏ hơn t0 chỉ có hữu hạn. J Bài toán 2.32. Chứng minh rằng phương trình x2 +y2 +z2 = 2xyz (2.7) không có nghiệm nguyên dương. Lời giải. Giả sử phương trình (2.7) có nghiệm nguyên dương (x0, y0,z0). Nghĩa là x20 +y20 +z20 = 2x0y0z0. (2.8) Vế phải của phương trình (2.8) chia hết cho 2, suy ra vế trái của nó cũng chia hết cho 2. Điều này chỉ xảy ra khi và chỉ khi tất cả x0, y0,z0 đều chẵn hoặc một số trong đó là số chẵn còn hai số kia là số lẻ. Điều sau cùng không thể được, vì khi đó vế phải của (2.8) chia hết cho 4, còn vế trái của (2.8) chia hết cho 2. Như vậy chỉ còn khả năng tất cả x0, y0,z0 là số chẵn. Đặt x0 = 2x1, y0 = 2y1,z0 = 2z1 (x1, y1,z1 nguyên dương). Thay các giá trị này vào (2.8), ta nhận được x21 +y21 +z21 = 4x1y1z1. (2.9) Sử dụng lý luận tương tự của phương trình (2.8) cho phương trình (2.9), ta tìm được x1 = 2x2, y1 = 2y2,z1 = 2z2 (x2, y2,z2 nguyên dương) và lại có x22 +y22 +z22 = 8x2y2z2. Tiếp tục quá trình này ta nhận được một dãy vô hạn những bộ ba nguyên dương: (xk, yk,zk) có tính chất xk = 2xk+1, k = 0,1,... và x0 > x1 > x2 > ··· > xk > xk+1 > ··· > 0. 2.4. Chuyên đề phương pháp xuống thang 71 Điều này vô lý vì dãy số tự nhiên nhỏ hơn x0 chỉ có hữu hạn, suy ra phương trình không có nghiệm nguyên dương. J Bài toán 2.33. Hãy tìm tất cả các nghiệm nguyên dương của phương trình x2 −2y2 = 1. Lời giải. Hiển nhiên x1 = 3, y1 = 2 là một nghiệm của phương trình. Ta chứng minh rằng nếu x và y là một nghiệm của phương trình, thì cặp 3x+4y và 2x+3y cũng là nghiệm của phương trình. Thật vậy, (3x+4y)2 −2(2x+3y)2 = x2 −2y2 = 1. Như vậy x2 = 3.3+4.2 = 17, y2 = 2.3+3.2 = 12. Tương tự ta tính được x3 = 99, y3 = 70, ... Như vậy ta xây dựng được dãy nghiệm x1, y1; x2, y2;.... Ta sẽ chứng minh rằng phương trình không có nghiệm khác ngoài dãy số trên. Giả sử x0, y0 là một nghiệm nào đó. Trong trường hợp đó 3x0 −4y0,3y0 −2x0 cũng là nghiệm, vì (3x0 −4y0)2 −2(3y0 −2x0)2 = x20 −2y20 = 1. Từ phương trình ta có 9 = 9x20 − 18y20 > −2y20suy ra 3x0 > 4y0; với y0 > 2 và từ phương trình ta có 4 = 4x20 −8y20 < y20suy ra 3y0 > 2x0. Như vậy với y0 > 2 từ nghiệm x0, y0 ta nhận được nghiệm x1, y1 nguyên dương sao cho x1 < x0 và y1 < y0. Quá trình này không thể kéo dài vô tận (do tiên đề thứ tự), đến một lúc nào đó ta nhận được nghiệm xn, yn, ở đây yn ≤ 2. Bởi vì yn không thể bằng 1, nên suy ra yn = 2. Nghĩa là xn = 3. Điều này có nghĩa là số xn, yn nằm trong dãy đã dựng ở phần trước. J 72 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên 2.4.3. Phương pháp xuống thang trong hình học Trong hình học có khái niệm cùng đo được như sau: Hai đoạn thẳng có độ dài tương ứng a và b gọi là cùng đo được, nếu tồn tại một đoạn thẳng có độ dài d và những số nguyên dương m và n sao cho a = md và b = nd. Bài toán 2.34. Chứng minh rằng đường chéo của một hình vuông không cùng đo được với cạnh của nó. Lời giải. Cho hình vuông ABCD. Ta đặt trên đường A2 C D D3 chéo hình vuông một đoạn có độ dài bằng cạnh của nó BD1 = AB (Hình 2.7). Từ điểm nhận được D1 dựng đường thẳng vuông góc với đường chéo của hình vuông A1 B2D2 B1 D1 và cắt cạnh hình vuông tại B1 và nối B1 với B. Hai tam giác AB1B và D1B1B bằng A B Hình 2.7 nhau, vì chúng là những tam giác vuông có cạnh BB1 chung và BD1 = BA (theo cách dựng). Suy ra AB1 = D1B1. Trong tam giác vuông B1CD1 có B\1CD1 = 45◦(do BC là đường chéo của hình vuông). Suy ra CB\1D1 = 45◦ và vì thế B1D1 = D1C. Ta đã chứng minh được AB1 = B1D1 = D1C, từ đó suy ra D1C < CD. Ta lại vẽ đường vuông góc với đường chéo CB tại C và đặt đoạn thẳng CA1 = D1B1 rồi nối điểm A1 với B1. Tứ giác A1B1D1C là hình vuông có đường chéo là B1C. 2.4. Chuyên đề phương pháp xuống thang 73 Quá trình dựng những hình vuông như vậy lặp lại nhiều lần. Vì thế ta nhận được dãy vô hạn những đoạn thẳng CD1 > CD2 > CD3 > ··· > 0. Mỗi đoạn thẳng này là hiệu giữa đường chéo và cạnh của một và chỉ một hình vuông. Theo cách dựng trên, ta tính được CD1 = CB−AB, CD2 = CB1 −A1B1, CD3 = CB2 −A2B2,... Giả sử đường chéo và cạnh của hình vuông ban đầu cùng đo được, thì tồn tại một đoạn thẳng đơn vị e mà đường chéo BC và cạnh hình vuông AB đều biểu diễn được bằng những số nguyên lần đoạn thẳng đơn vị. Trong trường hợp như vậy CD1 = CB−AB cũng biểu diễn thành số nguyên lần đoạn thẳng đơn vị và đường chéo CB1 của hình vuông A1CD1B1 bằng hiệu AC−AB1 = AB−CD1 cũng là số nguyên lần đoạn thẳng đơn vị. Như vậy ta đã dựng được dãy vô hạn những số nguyên dương giảm CD > CD1 > CD2 > ··· > CDk > ··· > 0. (ở đây CDilà độ dài của đoạn CDi). Không thể có dãy số nguyên dương vô hạn giảm tới 0. Điều vô lý này chỉ ra rằng không cùng đo được đường chéo và cạnh của cùng một hình vuông. J Bài toán 2.35. Cho một lưới ô vuông với các nút lưới là giao của các đường ngang và các đường dọc trên giấy (ta coi các nút lưới là điểm có tọa độ nguyên). Chứng minh rằng với n 6= 4 không tồn tại một n-giác đều nào có các đỉnh là các nút lưới trong lưới đã cho. Lời giải. Trước tiên ta chứng minh rằng không tồn tại một tam giác đều với các đỉnh là các nút lưới. Thật vậy, giả sử tồn tại một tam giác đều với các đỉnh là các nút lưới và gọi a là độ dài của cạnh tam 74 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên giác này. Khi đó a2là một số nguyên. Diện tích của tam giác bằng a2√3 4nên nó là một số vô tỉ. Mặt khác, hiển nhiên diện tích của một tam giác bất kì có đỉnh là các nút lưới là một số hữu tỉ. Điều này vô lý. Vậy không thể có tam giác đều có các đỉnh là các nút lưới. Vì một lục giác đều có thể ghép bởi các tam giác đều, nên trường hợp n = 6 bài toán được chứng minh. Giả sử P1,P2,...,Pn là đỉnh của n-giác đều trên các nút lưới (với n 6= 3,4,6). Ta đặt từ các điểm P1,P2,...,Pn những vectơ bằng những vectơ tương ứng −−→P2P3,−−→P3P4, . . . , P1 P2P3 P4 P5 Hình 2.8 −−→P1P2 (Hình 2.8 chỉ là trường hợp n = 5). Những điểm mới cũng rơi vào nút lưới và tạo ra một n-giác đều nằm bên trong n-giác đều trước đó. Từ n-giác đều mới ta có thể tiếp tục như vậy. Bình phương độ dài của cạnh n-giác đều là một số nguyên dương, theo cách dựng trên thì độ dài cạnh của n-giác đều giảm thực sự. Quá trình dựng trên tạo ra một dãy số nguyên dương của bình phương độ dài cạnh giảm đến vô hạn, điều này vô lý. Vậy không thể có n-giác đều (n 6= 4)có đỉnh là các nút lưới. J Bài toán 2.36. Cho những số nguyên x1, x2, x3, x4, x5 với x1 + x2 + x3 + x4 + x5 > 0 và được đặt trên đường tròn. Nếu xi < 0, thì các số xi−1, xi, xi+1 được phép đổi thành xi−1 +xi,−xi, xi+1 +xi (ta quy ước xi+5 ≡ xi). Chứng minh rằng sau hữu hạn bước thực hiện như vậy tất cả các số trên đường tròn trở thành các số nguyên không âm. 2.5. Bài tập 75 Lời giải. Ta chú ý rằng với cách thực hiện như bài toán đã cho thì tổng của các số không đổi. Mỗi bộ số X = (x1, x2, x3, x4, x5) ta đặt F(X) =5∑ i=1 (xi −xi+2)2. Cho xi < 0 và Y = (xi−2, xi−1 +xi,−xi, xi+1 +xi, xi+2). Tính toán không phức tạp cho kết quả F(X)−F(Y) = −2xi(x1 +x2 +x3 +x4 +x5) > 0. Nghĩa là F(Y) < F(X). Điều này có nghĩa là sau mỗi lần thực hiện số nguyên không âm F(X) giảm thực sự. Quá trình như vậy không thể tiếp tục đến vô hạn. Như vậy sau hữu hạn bước các số trở thành các số nguyên không âm. J Những bài toán như Bài toán 2.36 đã được giải bằng phương pháp đại lượng bất biến trong [18]. Trong cuốn sách này bạn đọc có thể tìm thấy hàng loạt các bài toán có cách giải tương tự. 2.5. BÀI TẬP . 2.37. Tìm nghiệm nguyên của phương trình 7(x2 +y2) = z2 +t2. . 2.38. Cho n2số nguyên không âm được đặt vào các ô trong bảng bao gồm n hàng và n cột. Với việc thực hiện phân bố số vào ô phải thỏa mãn điều kiện sau đây: Nếu một ô nào đó trong bảng viết số 0, thì tổng những số trong cột và trong hàng chứa ô này, không nhỏ hơn n. Chứng minh rằng tổng tất cả n2số đã cho không nhỏ hơn n22. 76 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên . 2.39. Trong một mặt phẳng cho n điểm (n ≥ 5). Mỗi điểm là tâm một đường tròn đi qua một điểm cố định O. Chứng minh rằng từ những hình tròn được tạo ra bởi các đường tròn đó có thể chọn được 5 hình tròn mà chúng phủ tất cả n điểm. . 2.40. Giải phương trình tìm nghiệm nguyên x4 +4y4 = 2(z4 +4u4). (2.10) . 2.41. Bằng phương pháp của Bài toán 2.40 tìm nghiệm nguyên của các phương trình sau: (a) x3 +3y3 +9z3 = 0; (b) 8x4 +4y4 +2z4 = t4; (c) x3 = 2y3 +4z3. . 2.42. Cho 2n+2 điểm trên mặt phẳng trong đó không có ba điểm nào thẳng hàng. Chứng minh rằng tồn tại hai điểm trong chúng sao cho đường thẳng đi qua hai điểm này chia mặt phẳng thành hai miền mà mỗi miền chứa đúng n điểm đã cho. . 2.43. Trong một bảng cỡ 10 × 10 người ta viết các số nguyên từ 1 đến 100. Từ mỗi hàng ta chọn số lớn thứ ba. Chứng minh rằng tổng của những số này không nhỏ hơn tổng của những số thuộc một hàng nào đó của bảng. . 2.44. Cho n số nguyên dương, ta xét tất cả khả năng của tổng được tạo bởi một hoặc một vài số của n số này. Chứng minh rằng những tổng này có thể chia thành n nhóm sao cho trong mỗi nhóm tỉ số giữa số lớn nhất và số nhỏ nhất không vượt quá 2. Bài tập dành cho phần chuyên đề (bạn đọc tự giải) 2.5. Bài tập 77 . 2.45. Chứng minh rằng nếu một số tự nhiên p không phải là lũy thừa bậc n của một số tự nhiên, thì √n p là một số vô tỉ. . 2.46. Có sử dụng phương pháp xuống thang để chứng minh phương trình 5(x2 +y2) = z2 +t2 không có nghiệm nguyên dương hay không? . 2.47. Chứng minh rằng cạnh đáy và cạnh bên của một tam giác cân có góc ở đỉnh là 36◦ không cùng đo được cùng đơn vị. . 2.48. Chứng minh rằng số 7 không thể biểu diễn dưới dạng tổng các bình phương của ba số hữu tỉ. . 2.49. Chứng minh rằng phương trình x4 +y4 = z4 không có nghiệm nguyên dương. . 2.50. Giải phương trình sau trong tập số nguyên dương: a) x2 + (x+1)2 = y2 +1; b) 3x2 −7y2 +1 = 0; c) (x+1)3 −y3 = z3. . 2.51. Cho a1,a2,...,an là một bộ những số tự nhiên đôi một khác nhau (n > 2). Từ đó ta nhận được bộ số mới a1 +a2 2,a2 +a3 2,...,an−1 +an 2,an +a1 2. Từ bộ số này lại theo quy tắc trên tạo bộ số sau đó và quá trình tiếp tục như vậy... Chứng minh rằng sau một số bước chắc chắn nhận được bộ số, mà trong đó không phải tất cả các số đều là số tự nhiên. 78 Chương 2. Kĩ thuật dùng phương pháp đại lượng cực biên . 2.52. Giả sử a1,a2,...,a2n là bộ những số tự nhiên bất kì. Chứng minh rằng nếu tạo từ nó bộ số mới b1,b2,...,b2n theo nguyên tắc bk = |ak+1 −ak|, k = 1,2,...,2n, a2n+1 = a1, sau đó từ bộ b1,b2,...,b2n theo nguyên tắc trên tạo ra bộ số c1, c2,..., c2n quá trình tiếp tục như vậy. . . , thì sau một số bước ta đưa về bộ số gồm toàn số 0. CHƯƠNG 3 CÁC BÀI TOÁN HÌNH HỌC 3.1. Góc lớn nhất hoặc góc nhỏ nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.2. Khoảng cách lớn nhất hoặc nhỏ nhất . . . . . . . . . . . . . . . . . . . . . . . 84 3.3. Diện tích và chu vi lớn nhất hoặc nhỏ nhất. . . . . . . . . . . . . . . . . . 89 3.4. Bao lồi và đường thẳng tựa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.5. Chuyên đề về bài toán Sylvester-Gallai. . . . . . . . . . . . . . . . . . . . . . 97 3.5.1. Giới thiệu bài toán Sylvester-Gallai. . . . . . . . . . . 97 3.5.2. Tổng quát hóa bài toán Sylvester-Gallai . . . . . . 99 3.5.3. Số những đường thẳng trong định lý Gallai . 102 3.5.4. Tổng quát hóa định lý Gallai trong lý thuyết thiết kế khối . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.6. Bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Ta nhận thấy rằng nhiều bài toán được giải với việc xét các phần tử cực biên. Trong hình học thì những phần tử cực biên là gì ? Trong chương này ta xem xét các phần tử cực biên là các góc lớn nhất hoặc nhỏ nhất, độ dài các cạnh hoặc đoạn thẳng lớn nhất hoặc nhỏ nhất, diện tích của các hình lớn nhất hoặc nhỏ nhất, rồi các điểm đầu mút của đoạn thẳng, ... Việc xem xét bài toán với quan điểm của những đại lượng cực biên cho ta lời giải nhanh gọn và đẹp. Một số 80 Chương 3. Các bài toán hình học bài toán đã được mô tả trong [13] của tác giả. Chương này liệt kê thêm những bài toán khác có dùng phương pháp đại lượng cực biên để giải. 3.1. GÓC LỚN NHẤT HOẶC GÓC NHỎ NHẤT Bài toán 3.1. Chứng minh rằng nếu tất cả các cạnh của một tam giác nhỏ hơn 1 thì diện tích tam giác nhỏ hơn √3 4. Lời giải. Gọi A là góc nhỏ nhất của tam giác ABC, suy ra BAC d ≤ 60◦ (Hình 3.1). Ta có SABC =12BH.AC =12AB.sinBAC d.AC. Do đó SABC ≤12AB.ACsin 60◦ ≤12.1.1.√32=√34· Đó là điều ta cần chứng minh. J D B C H A Hình 3.1 A B M Hình 3.2 C Bài toán 3.2. Chứng minh rằng bốn hình tròn có đường kính là bốn cạnh của một tứ giác lồi ABCD phủ kín miền tứ giác đó. """