Luận văn Thạc sĩ Khoa học: Một số phương pháp giải bài toán không mẫu mực

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

Thêm vào BST

Báo xấu

87
lượt xem 17
download

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

Luận văn được chia làm sáu chương. Chương 1 trình bày về phương pháp quy nạp toán học. Chương 2 trình bày về phương pháp phản chứng. Chương 3 trình bày về phương pháp suy luận. Chương 4 trình bày về phương pháp bảng. Chương 5 trình bày về phương pháp sơ đồ. Chương 6 trình bày về phương pháp đồ thị.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một số phương pháp giải bài toán không mẫu mực

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- ĐINH THỊ BÍCH NGỌC ĐỀ TÀI MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN KHÔNG MẪU MỰC Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: GS.TS Đặng Huy Ruận HÀ NỘI - 2015
Mục lục Lời nói đầu 3 1 Phương pháp quy nạp toán học 4 1.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . . 4 1.2 Phương pháp chứng minh bằng quy nạp . . . . . . . . . 4 1.2.1 Cơ sở quy nạp . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Quy nạp . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Vận dụng phương pháp quy nạp để giải bài toán không mẫu mực . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . 23 2 Phương pháp phản chứng 25 2.1 Phép suy luận phản chứng . . . . . . . . . . . . . . . . . 25 2.2 Phương pháp chứng minh bằng phản chứng . . . . . . . 25 2.3 Các bước suy luận trong chứng minh phản chứng . . . . 26 2.4 Vận dụng phương pháp phản chứng để giải các bài toán không mẫu mực . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Phương pháp suy luận 39 3.1 Vài nét về phương pháp suy luận . . . . . . . . . . . . . 39 3.2 Các ví dụ về vận dụng phương pháp suy luận. . . . . . . 40 3.3 Bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . 46 4 Phương pháp bảng 50 4.1 Vài nét về phương pháp bảng . . . . . . . . . . . . . . . 50 4.2 Vận dụng phương pháp bảng để giải bài toán không mẫu mực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 Bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . 59 1
5 Phương pháp sơ đồ 63 5.1 Giới thiệu về phương pháp sơ đồ . . . . . . . . . . . . . 63 5.2 Vận dụng phương pháp sơ đồ để giải các bài toán không mẫu mực. . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.3 Bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . 69 6 Phương pháp đồ thị 73 6.1 Một số khái niệm và kết quả cơ bản của lý thuyết đồ thị 73 6.2 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . 74 6.3 Vận dụng phương pháp đồ thị để giải bài toán không mẫu mực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.4 Bài tập tự giải . . . . . . . . . . . . . . . . . . . . . . . . 87 Kết luận 91 Tài liệu tham khảo 92 2
LỜI NÓI ĐẦU Các bài toán không mẫu mực là các bài toán mà việc giải chúng đòi hỏi suy luận, tư duy độc đáo. Việc giải các bài toán không mẫu mực giúp người thực hiện nâng cao nhanh chóng khả năng tư duy, suy luận và nhiều khi phát hiện ra những phương pháp giải toán độc đáo không ngờ. Bởi vậy rất nhiều em học sinh, đặc biệt là học sinh trường chuyên, lớp chọn thích làm quen với các bài toán này. Luận văn "Một số phương pháp giải bài toán không mẫu mực" trình bày sáu phương pháp chủ yếu để giải các bài toán không mẫu mực. Nhưng do một bài toán không mẫu mực có thể giải đồng thời bằng nhiều phương pháp khác nhau và một vài phương pháp có phần "tương tự" nên việc phân loại phương pháp, ví dụ và bài tập chỉ là tương đối. Các bài toán không mẫu mực là mảng khá lý thú trong toán học nói chung cũng như toán phổ thông nói riêng. Vì vậy, tác giả hi vọng luận văn sẽ trở thành tài liệu có ích cho các em học sinh phổ thông, đặc biệt các em học sinh trường chuyên, lớp chọn, các thầy cô giáo dạy ở cuối cấp tiểu học, các thầy cô giáo dạy toán ở trường phổ thông, các bạn sinh viên và những ai quan tâm đến mảng toán lý thú này. Luận văn được chia làm sáu chương: Chương 1 trình bày về phương pháp quy nạp toán học. Chương 2 trình bày về phương pháp phản chứng. Chương 3 trình bày về phương pháp suy luận. Chương 4 trình bày về phương pháp bảng. Chương 5 trình bày về phương pháp sơ đồ. Chương 6 trình bày về phương pháp đồ thị. Luận văn được hoàn thành dưới sự hướng dẫn, giúp đỡ tận tình của GS.TS Đặng Huy Ruận, em xin gửi tới thầy lòng biết ơn sâu sắc. Em xin gửi lời cảm ơn chân thành đến Ban chủ nhiệm khoa cùng các thầy cô giáo khoa Toán - Cơ - Tin học, Trường Đại học Khoa Học Tự Nhiên - Đại Học Quốc Gia Hà Nội đã tạo điều kiện, dạy bảo và dìu dắt em trong những năm học vừa qua. Xin chân thành cảm ơn sự giúp đỡ của bạn bè, người thân trong thời gian học tập và làm luận văn. Do khả năng nhận thức của bản thân tác giả, luận văn còn nhiều hạn chế, thiếu sót. Kính mong nhận được các ý kiến đóng góp của thầy cô cùng các bạn đọc. Xin chân thành cảm ơn! Hà Nội, tháng 7 năm 2015 3
Chương 1 Phương pháp quy nạp toán học Phương pháp quy nạp toán học là một công cụ rất có hiệu lực trong việc chứng minh nhiều bài toán thuộc các lĩnh vực khác nhau của toán học như: số học, đại số, hình học... và đặc biệt là các bài toán không mẫu mực. Đây là một phương pháp chứng minh toán học đặc biệt cho phép ta rút ra những quy luật tổng quát dựa trên cơ sở những trường hợp riêng. Quá trình quy nạp ngược với quá trình suy diễn. Từ "tính chất" của một số cá thể suy ra "tính chất" của tập thể, nên không phải lúc nào cũng đúng. Nó chỉ đúng khi thỏa mãn nguyên lý quy nạp. 1.1 Nguyên lý quy nạp Cho n0 là một số nguyên dương và P (n) là một mệnh đề có nghĩa với mọi số tự nhiên n ≥ n0 . Nếu 1.P (n0 ) đúng và 2. Nếu P (k) đúng từ đó suy ra được P (k + 1) cũng đúng với mọi số tự nhiên k ≥ n0 thì P (n) đúng với mọi số tự nhiên n ≥ n0 . 1.2 Phương pháp chứng minh bằng quy nạp Giả sử khẳng định P (n) xác định ∀n ≥ n0 . Để chứng minh P (n) đúng ∀n ≥ n0 bằng quy nạp, ta cần thực hiện 2 bước 1.2.1 Cơ sở quy nạp Kiểm tra sự đúng đắn của P (n) với n = n0 , nghĩa là xét P (n0 ) có đúng không. 4
1.2.2 Quy nạp Chứng minh rằng: Nếu với mỗi k ≥ n0 , P (k) là mệnh đề đúng, thì suy ra P (k + 1) cũng đúng. Nếu cả 2 bước trên đều thỏa mãn, thì theo nguyên lý quy nạp P (n) đúng với mọi n ≥ n0 . Chú ý Trong quá trình quy nạp, nếu không thực hiện đầy đủ cả 2 bước: Cơ sở quy nạp và quy nạp thì có thể dẫn đến kết luận sai lầm. Một số ví dụ sau sẽ chứng tỏ điều này. - Do bỏ qua bước cơ sở quy nạp, ta đưa ra kết luận không đúng: Mọi số tự nhiên đều bằng nhau! Bằng cách quy nạp như sau: Giả sử các số tự nhiên không vượt quá k + 1 đã bằng nhau. Khi đó ta có: k =k+1 Thêm vào mỗi vế của đẳng thức trên 1 đơn vị sẽ có: k+1=k+1+1=k+2 Cứ như vậy suy ra mọi số tự nhiên không nhỏ hơn k đều bằng nhau. Kết hợp với giả thiết quy nạp: Mọi số tự nhiên không vượt quá k đều bằng nhau, đi đến kết luận sai lầm: Tất cả các số tự nhiên đều bằng nhau! - Do bỏ qua bước quy nạp nên nhà toán học Pháp P.Fermat (1601 - n 1665) đã cho rằng số dạng 22 + 1 đều là số nguyên tố. P.Fermat xét 5 số đầu tiên: 0 Với n = 0 cho 22 + 1 = 21 + 1 = 3 là số nguyên tố. 1 Với n = 1 cho 22 + 1 = 22 + 1 = 5 là số nguyên tố. 2 Với n = 2 cho 22 + 1 = 24 + 1 = 17 là số nguyên tố. 3 Với n = 3 cho 22 + 1 = 28 + 1 = 257 là số nguyên tố. 4 Với n = 4 cho 22 + 1 = 216 + 1 = 65537 là số nguyên tố. Nhưng vào thế kỷ XVIII, L.Euler (1707 - 1783) đã phát hiện với n = 5 khẳng định trên không đúng, bởi vì: 5 22 + 1 = 4294967297 = 641.6700417 là hợp số. 5
1.3 Vận dụng phương pháp quy nạp để giải bài toán không mẫu mực Phương pháp quy nạp được sử dụng trong tính toán, trong chứng minh và suy luận dưới nhiều dạng khác nhau, nhưng trong phần này chỉ trình bày việc vận dụng phương pháp quy nạp để giải bài toán không mẫu mực. Bài toán 1.3.1. (IMO 1998) Với mọi số nguyên dương n, ta kí hiệu d(n) là số tất cả các ước dương của n (kể cả 1 và n). Hãy xác định tất cả các số nguyên dương k, sao cho d(n2 ) = kd(n), với n là số nguyên dương nào đó. Chứng minh. Giả sử khi phân tích ra thừa số nguyên tố, số n có dạng: n = pa11 .pa22 ...par r Ta có: d(n) = (a1 + 1)(a2 + 1)...(ar + 1) d(n2 ) = (2a1 + 1)(2a2 + 1)...(2ar + 1) Để d(n2 ) = kd(n) thì ta phải chọn các số ai sao cho: (2a1 + 1)(2a2 + 1)...(2ar + 1) = k(a1 + 1)(a2 + 1)...(ar + 1) (∗) Do (2ai + 1)(1 ≤ i ≤ r) đều là các số lẻ nên k phải là các số lẻ. Ta sẽ chứng minh mệnh đề đảo lại rằng: "Với số lẻ k bất kỳ, ta có thể tìm được các số ai thỏa mãn (*) (tức là tìm được n)". Dùng phương pháp quy nạp theo k. 1. Với k = 1, mệnh đề đúng (n = 1, ai = 0) 2. Giả sử mệnh đề đúng với số k nào đó, ta chứng minh nó cũng đúng cho (2m .k − 1)(m ≥ 1). Lúc đó mệnh đề đúng cho mọi số lẻ vì mọi số lẻ l đều viết được dưới dạng: (2m .l0 − 1) (với l0 là số nhỏ hơn l). Đặt ai = 2i−1 [(2m − 1).k − 1], với i = 1, 2, ..., m. Khi đó: 2ai + 1 = 2i (2m − 1)k − (2i − 1) ai + 1 = 2i−1 (2m − 1)k − (2i−1 − 1) = 2ai−1 + 1 Do vậy, tích của các số (2ai + 1) chia hết cho tích các số (ai + 1) với i = 1, m khi (2am + 1) chia hết cho (a1 + 1) hay: [2m (2m − 1)k − (2m − 1)] = (2m − 1).(2m .k − 1) 6
chia hết cho (2m − 1)k có nghĩa là: (2m .k − 1) chia hết cho k. Vậy nếu ta chọn các ai như trên với k đã cho, thì mệnh đề trên đúng cho (2m .k − 1). Ta có điều phải chứng minh! Bài toán 1.3.2. (USAMTS, 2000 - 2001, Cuộc thi tài năng toán học Mỹ) Hãy tìm số dư khi chia số 17761492! cho 2000. Chứng minh. Trước hết ta chứng minh bổ đề: "Với mọi số nguyên dương n, ta có: 1376n ≡ 1376(mod 2000)" Dùng phương pháp quy nạp: 1. Với n = 1, hiển nhiên có: 13761 ≡ 1376(mod 2000) Với n = 2, ta có: 13762 = 1893376 ≡ 1376(mod 2000) 2. Giả sử mệnh đề đúng với n = k(k ∈ N, k ≥ 1), tức là: 1376k ≡ 1376(mod 2000). Ta chứng minh bổ đề đúng với n = k + 1. Thật vậy, từ giả thiết quy nạp ta có: 1376k+1 ≡ 13762 (mod 2000), mà 13762 ≡ 1376(mod 2000), nên 1376k+1 ≡ 1376(mod 2000) Bổ đề được chứng minh! Quay lại bài toán, ta có: 17765 = 1376(mod 2000), nên 1492! 17761492! = (17765 ) 5 Vậy khi chia số 17761492! cho 2000 được số dư là 1376. n Bài toán 1.3.3. Hãy tìm chữ số tận cùng của số: An = 22 + 1 với mọi số nguyên n, n ≥ 2. Chứng minh. 2 1. Với n = 2, số A2 = 22 + 1 = 17, có chữ số tận cùng là 7. k 2. Giả sử với n = k, số Ak = 22 + 1 có chữ số tận cùng là 7. Ta sẽ chứng minh Ak+1 có chữ số tận cùng là 7. Thật vậy, do Ak có chữ số tận cùng là 7, nên tồn tại số nguyên dương m để: Ak = 10m + 7, hay: k 22 + 1 = 10m + 7 7
k Tức là: 22 = 10m + 6. Từ đó: k+1 Ak+1 = 22 +1 k = 22 .2 +1 k 2 = (22 ) + 1 = (10m + 6)2 + 1 = 100m2 + 120m + 37 = 10(10m2 + 12m + 3) + 7 nên Ak+1 cũng có chữ số tận cùng là 7. n Vậy với mọi số nguyên n, n ≥ 2, thì An = 22 + 1 có chữ số tận cùng là 7. Bài toán 1.3.4. (Vô địch toán Canada, 1982) Cho a, b và c là những nghiệm của phương trình: x3 − x2 − x − 1 = 0 Chứng minh rằng số: b1982 − c1982 c1982 − a1982 a1982 − b1982 + + b−c c−a a−b là một số nguyên. Chứng minh. n −cn n −an n −bn Đặt un = b b−c , vn = c c−a , wn = aa−b , với n nguyên, n ≥ 1. Ta sẽ chứng minh: un + vn + wn nguyên với mọi n nguyên, n ≥ 1(∗). Trước hết ta thấy rằng: un+3 = un+3 + un+3 + un , ∀n, n 6= 1. Thật vậy, do b, c là nghiệm của phương trình x3 − x2 − x − 1 = 0 nên: b3 = b2 + b + 1, c3 = c3 + c + 1 Do đó: bn+3 − cn+3 un+3 = b−c b .b − cn .c3 n 3 = b−c b (b + b + 1) − cn (c2 + c + 1) n 2 = b−c n+2 n+2 b −c bn+1 − cn+1 bn − cn = + + b−c b−c b−c = un+2 + un+1 + un 8
Tương tự ta có: vn+3 = vn+2 + vn+1 + vn wn+3 = wn+2 + wn+1 + wn Tiếp theo, ta sẽ dùng phương pháp quy nạp để chứng minh khẳng định (*) 1. Với n = 1, ta có: u1 + v1 + w1 = 1 + 1 + 1 = 3 ∈ Z Với n = 2, ta có: b2 − c2 c2 − a2 a2 − b2 u2 + v2 + w2 = + + b−c c−a a−b −1 = 2(a + b + c) = 2(− ) = 2 ∈ Z 1 Với n = 3 ta có: b3 − c3 c3 − a3 a3 − b3 u2 + v2 + w2 = + + b−c c−a a−b 2 2 2 = 2(a + b + c ) + (bc + ca + ab) = 2(a + b + c)2 − 3(bc + ca + ab) −1 −1 = 2(− )2 − 3( ) = 5 ∈ Z 1 1 Vậy khẳng định đúng với n = 1, 2, 3. 2. Giả sử khẳng định đúng với n = k, k + 1, k + 2(k ≥ 1). Ta chứng minh khẳng định đúng với n = k + 3. Thật vậy, ta có: uk+3 + vk+3 + wk+3 = (uk+2 + uk+1 + uk ) + (vk+2 + vk+1 + vk ) + (wk+2 + wk+1 + wk ) (uk+2 + vk+2 + wk+2 ) + ((uk+1 + vk+1 + wk+1 ) + (uk + vk + wk ) Theo giả thiết quy nạp, cả ba số hạng của tổng trên đều nguyên nên (uk+3 + vk+3 + wk+3 ) cũng nguyên. Khẳng định được chứng minh. Từ đó hiển nhiên tổng ở đề bài là số nguyên. −−→ −−→ −−−−→ Bài toán 1.3.5. (IMO 1973) Cho OP1 , OP2 , ..., OP2n+1 là các vecto đơn vị trong mặt phẳng. Các điểm P1 , P2 , P2n+1 đều cùng nằm về 1 phía của đường thẳng qua O. Chứng minh rằng: −−→ −−→ −−−−→ |OP1 + OP2 + ... + OP2n+1 | ≥ 1 Chứng minh. 9
1. Với n = 1, mệnh đề hiển nhiên đúng do: −−→ |OP1 | = 1 ≥ 1 2. Giả sử mệnh đề đúng với n = k − 1(k ≥ 2), tức là với hệ vecto −−→ −−→ −−−−→ đơn vị: OP1 , OP2 , ..., OP2k−1 cùng nằm về 1 phía của 1 đường thẳng qua O, ta đã có: −−→ −−→ −−−−→ |OP1 + OP2 + ... + OP2k−1 | ≥ 1 Ta chứng minh mệnh đề đúng với n = k, tức là với hệ (2k + 1) vecto −−→ −−→ −−−−→ OP1 , OP2 , ..., OP2k+1 thỏa mãn các điều kiện trên, ta cũng có: −−→ −−→ −−−−→ |OP1 + OP2 + ... + OP2k+1 | ≥ 1 −−→ Thật vậy, do vai trò của OPi (1 ≤ i ≤ 2k + 1) như nhau nên ta có thể −−→ −−−→ −−−−→ sắp xếp lại sao cho OPi (1 ≤ i ≤ 2k − 1) nằm giữa OP2k và OP2k+1 Đặt: → − −−−→ −−−−→ u = OP2k + OP2k+1 → − −−→ −−→ −−−−→ v = OP + OP + ... + OP 1 2 2k−1 Khi đó →−u có phương nằm trên tia phân giác góc P2k\ OP2k+1 . Áp dụng → − −−→ −−−−→ quy tắc hình bình hành nhiều lần, ta được v nằm giữa OP1 và OP2k−1 , −−−→ −−−−→ nên nó nằm giữa OP2k và OP2k+1 . π Vậy góc giữa →− u và → −v bé hơn hoặc bằng 2 Ta lại có: (→ − u +→−v )2 = → − u +→ − v + 2→ −u→ − 2 2 v =→ − u +→ − v + 2|→−u ||→ − v |cos(→ − u ,→ − 2 2 v) ≥→ − v (do cos(→ − u ,→ − 2 v ) ≥ 0) Do đó: |→ − u +→ −v | ≥ |→ − v| Mà theo giả thiết quy nạp ta có |→ − v | ≥ 1. → − → − Vậy | u + v | ≥ 1 hay −−→ −−→ −−−−→ |OP1 + OP2 + ... + OPn+1 | ≥ 1 Mệnh đề đúng với n = k + 1, ta có điều phải chứng minh! Bài toán 1.3.6. (Chứng minh tính chia hết bằng quy nạp) (Định lý Fermat nhỏ) Chứng minh rằng: Nếu p là số nguyên tố, thì với mọi số nguyên dương n, hiệu np − n chia hết cho p. 10
Chứng minh. 1. Với n = 1 ta có: 1p − 1 = 0 chia hết cho p. 2. Giả sử khẳng định đúng với số nguyên n = a ≥ 1, nghĩa là ap − a chia hết cho p. Ta chứng minh: (a + 1)p − (a + 1) cũng chia hết cho p. Theo khai triển nhị thức Newton ta có: (a + 1)p − (a + 1) = C0p .ap + C1p .ap−1 + C2p .ap−2 + ... + +Cp−1 p p .a + Cp − a − 1 = (ap − a) + C1p .ap−1 + C2p .ap−2 + ... + +Cp−1 p .a Ta có: p! p(p − 1)...(p − k − 1) Ckp = = (với 1 ≤ k ≤ p − 1) k!(p − k)! 1.2.3...k Do p là số nguyên tố nên (p, k) = 1; ∀k, 1 ≥ k ≥ p − 1, suy ra Ckp chia hết cho p với mọi k, 1 ≤ k ≤ p − 1. Mà ap − a cũng chia hết cho p (theo giả thiết quy nạp) Vậy (a + 1)p − (a + 1) cũng chia hết cho p, định lý được chứng minh! Bài toán 1.3.7. (Vô địch toán Hungari 1932) Chứng minh rằng nếu a, b, n là những số tự nhiên và b chia hết cho an , thì số (a + 1)b − 1 chia hết cho an+1 Chứng minh. (Quy nạp theo n) 1. Với n = 0, ta có (a + 1)0 − 1 luôn chia hết cho a0+1 = a, nên mệnh đề đúng với n = 0. 2. Giả sử mệnh đề đúng với số tự nhiên n = k nào đó, tức là nếu b chia hết cho ak thì (a + 1)b − 1 chia hết cho ak+1 . Ta chứng minh mệnh đề đúng với n = k + 1, tức là nếu b1 là số tự nhiên, b1 chia hết cho ak+1 thì (a + 1)b1 − 1 chia hết cho ak+2 . b1 Thật vậy, đặt c = , thì c chia hết cho ak . a Ta có: (a + 1)b1 − 1 = (a + 1)ca − 1 = [(a + 1)c ]a − 1 = [(a + 1)c − 1][(a + 1)c(a−1) + (a + 1)c(a−2) + ... + (a + 1)c + 1] Biểu thức trong dấu ngoặc vuông thứ nhất chia hết cho ak+1 (theo giả thiết quy nạp). 11
Biểu thức trong dấu ngoặc vuông thứ hai chia hết cho a vì ta có thể biểu diễn nó dưới dạng: [(a + 1)c(a−1) − 1] + [(a + 1)c(a−2) − 1] + ... + [(a + 1)c − 1] + a (Mỗi số hạng tổng này đều chia hết cho a) Vậy (a + 1)b1 − 1 chia hết cho ak+2 . Mệnh đề được chứng minh! Bài toán 1.3.8. (Chứng minh đẳng thức bằng quy nạp) (Công thức nhị thức Newton) Chứng minh rằng: n X n (a + b) = ckn .ak .bn−k k=0 Chứng minh. 1. Với n = 1, dễ thấy công thức đúng. 2. Giả sử công thức đúng với số nguyên dương n, tức là ta có: n X n (a + b) = Ckn .ak .bn−k k=0 Ta chứng minh công thức đúng với n + 1. Thật vậy, ta có: (a + b)n+1 = (a + b)n .(a + b) = (an + C1n .an−1 .b + ... + Ckn .an−k .bk + ... + bn )(a + b) = an+1 + C1n .an .b + ... + Ckn .an+1−k .bk + ... + a.bn + an .b + C1n .an−1 .b2 + ... + Ckn .an−k .bk+1 + ... + bn+1 = an+1 + (C0n + C1n ).an .b + (C1n + C2n ).an−1 .b2 + ... + (Ck−1 n + Ckn ).aa+1−k .bk + ... + bn+1 = an+1 + C1n+1 .an .b + C2n+1 .an−1 .b2 + Ckn+1 .an+1−k .bk + ... + bn−1 n+1 X = Ckn+1 .ak .bn+1−k k=0 Công thức được chứng minh! Bài toán 1.3.9. (Chứng minh bất đẳng thức bằng quy nạp) (Bất đẳng thức Bernoulli) Chứng minh rằng với mọi x > −1, x 6= 0 và mọi số tự nhiên n ≥ 2, ta có: (1 + x)n > 1 + nx 12
Chứng minh. 1. Với n = 2, bất đẳng thức có dạng: (1 + x)2 > 1 + 2x hay x2 > 0. Điều này đúng do x 6= 0. 2. Giả sử bất đẳng thức đúng với n = k(k ≥ 2), tức là đã có: (1+x)k > (1 + kx) Ta chứng minh nó cũng đúng với n = k + 1. Thật vậy, ta có: (1 + x)k+1 = (1 + x)k (1 + x) > (1 + kx)(1 + x) = 1 + (k + 1)x + kx2 > 1 + (k + 1)x (Vì k > 0 và x 6= 0) Vậy bất đẳng thức được chứng minh! Chú ý: Bất đẳng thức Bernoulli còn đúng cho mọi số thực α > 1: (1 + x)α > l + α; ∀x, x > −1, x 6= 0 Bài toán 1.3.10. (Vô địch toán Matxcova 1984) Cho x1 , x2 , ..., xn là n số không âm (n ≥ 4), tổng của chúng bằng 1. Chứng minh rằng: x1 x2 + x2 x3 + ... + xn x1 ≤ 4 Chứng minh. Ta sẽ chứng minh bất đẳng thức sau bằng phương pháp quy nạp: (x1 + x2 + .... + xn )2 ≥ 4(x1 x2 + x2 x3 + .... + xn x1 ) Với xi ≥ 0, i = 1, n và n ≥ 4 1. Với n = 4, ta có: (x1 − x2 + x3 − x4 )2 = x21 + x22 + x23 + x24 − 2x1 x2 + 2x1 x3 − 2x1 x4 − 2x2 x3 + 2x2 x4 − 2x3 x4 = (x1 + x2 + x3 + x4 )2 − 4(x1 x2 + x2 x3 + x3 x4 + x4 x1 ) ≥ 0 Do đó: (x1 + x2 + x3 + x4 )2 ≥ 4(x1 x2 + x2 x3 + x3 x4 + x4 x1 ) nên bất đẳng thức đúng với n = 4. 2. Giả sử bất đẳng thức đúng với n = k(k ≥ 4), tức là ta có: (x1 + x2 + ... + xk )2 ≥ 4(x1 x2 + x2 x3 + ... + xk x1 ) Ta chứng minh bất đẳng thức đúng với n = k + 1: (x1 + x2 + ... + xk + xk+1 )2 ≥ 4(x1 x2 + x2 x3 + ... + xk xk+1 + xk+1 x1 ) 13
Vì tổng 2 vế của bất đẳng thức này là vòng tròn theo chỉ số, ta có thể giả thiết xk+1 ≥ xi , i = 1, k. Khi đó, từ giả thiết quy nạp ta có: (x1 + x2 + ... + xk + xk+1 )2 = (x1 + x2 + ... + (xk + xk+1 ))2 ≥ 4[x1 x2 + x2 x3 + ... + xk−1 (xk + xk+1 ) + (xk + xk+1 )x1 ] Mà: [x1 x2 + x2 x3 + ... + xk−1 (xk + xk+1 ) + (xk + xk+1 )x1 ] = (x1 x2 + x2 x3 + ... + xk xk+1 + xk+1 x1 ) + xk−1 xk+1 + xk (x1 − xk+1 ) Vì xi ≥ 0 và x1 − xk+1 ≥ 0 nên ta có: [x1 x2 + x2 x3 + ... + xk−1 (xk + xk+1 ) + (xk + xk+1 )x1 ] ≥ (x1 x2 + x2 x3 + ... + xk−1 xk + xk xk+1 + xk+1 x1 ) Vậy (x1 + x2 + ... + xk + xk+1 )2 ≥ 4(x1 x2 + x2 x3 + ... + xk xk+1 + xk+1 x1 ) nên ta có điều phải chứng minh! Bài toán 1.3.11. (Tính toán bằng quy nạp) Tính bán kính rn , Rn của đường tròn nội tiếp và ngoại tiếp 2n - giác đều chu vi p cho trước (n ≥ 2). Chứng minh. 1. Với n = 2, ta có hình vuông chu vi p. Dễ dàng tính được: √ p p 2 r2 = ; R2 = 8 8 2. Giả sử biết bán kính rn , Rn của các đường tròn nội tiếp và ngoại tiếp 2n - giác đều chu vi p, ta tính các bán kính rn+1 , Rn+1 của các đường tròn nội tiếp và ngoại tiếp 2n+1 - giác đều chu vi p. Gọi AB là cạnh của 2n - giác đều chu vi p tâm O. Gọi C, D, E, F lần lượt là trung điểm của cung AB, dây AB, AC, BC, G là trung điểm của EF. Vì (OE, \ OF ) = (OE, \ OC) + (OF, \ OC) 1 \ 1 \ 1 \ = (OA, OC) + (OB, OC) = (OA, OB) 2 2 2 14
Hình 1.3.11 và EF bằng cạnh của 2n+1 - giác đều nội tiếp đường tròn bán kính OE, nên chu vi của 2n+1 - giác này là: AB 2n+1 .EF = 2n+1 = 2n .AB = p 2 Do đó rn+1 = OG và Rn+1 = OE Mặt khác, ta dễ thấy 1 OC − OG = OG − OD(= CD) 2 nên Rn − rn+1 = rn+1 − rn hay rn+1 = Rn2+rn Cuối cùng, từ tam giác vuông OEC ta có: OE 2 = OC.OG. Nghĩa là: 2 √ Rn+1 = Rn rn+1 , nên Rn+1 = Rn rn+1 . √ Vậy rn+1 = Rn2+rn , Rn+1 = Rn rn+1 . Bài toán 1.3.12. Trên một hình phẳng cho n đường tròn phân biệt, đôi một cắt nhau và không có ba đường tròn nào giao nhau tại 1 điểm. Các mặt phẳng này chia đường tròn thành các miền rời nhau. Tính số miền thu được. Chứng minh. Gọi số miền thu được bởi n đường tròn trong mặt phẳng thỏa mãn điều kiện đề bài là F (n). 1. Với n = 1, dễ thấy F (1) = 2. Với n = 2, ta có 2 đường tròn cắt nhau và F (2) = 4 2. Giả sử với k đường tròn thỏa mãn điều kiện đề bài, chúng chia mặt phẳng ra làm F (k) miền. Xét (k + 1) đường tròn thỏa mãn điều kiện đề bài. Ta tính F (k + 1). Gọi (k + 1) đường tròn đó là (C1 ), (C2 ), ..., (Ck+1 ). Bỏ đi 1 đường tròn bất kỳ trong (k + 1) đường tròn đó, chẳng hạn (Ck+1 ). Khi đó còn 15
Hình 1.3.12 k đường tròn, theo giả thiết quy nạp, số miền thu được là F (k). Bây giờ ta dựng lại Ck+1 . Khi đó đường tròn Ck+1 giao với cả k đường tròn ban đầu. Trên Ck+1 có k cặp giao điểm nên cho ta thêm 2k miền. Vậy F (k + 1) = F (k) + 2k. Do đó ta có: F (k) = F (k − 1) + 2(k − 1) F (k − 1) = F (k − 2) + 2(k − 2) ... F (2) = F (1) + 2.1 F (1) = 2 Cộng các đẳng thức trên lại ta được: F (k) = 2[1 + 1 + 2 + 3 + ... + (k − 2) + (k − 1)] k(k − 1) = 2[1 + ] 2 = k2 − k + 2 Vậy số miền thu được từ n đường tròn thỏa mãn đề bài là F (n) = n2 − n + 2. Bài toán 1.3.13. (Chứng minh bằng quy nạp) Chứng minh rằng mọi n - giác lồi(n ≥ 5) đều được chia thành 1 số hữu hạn các ngũ giác lồi. Chứng minh. 1. Với n = 5, mệnh đề hiển nhiên đúng. 2. Giả sử mệnh đề đúng với n = k(k ≥ 5), tức là mọi k - giác lồi đều chia được thành hữu hạn các ngũ giác lồi. Ta chứng minh mệnh đề đúng với n = k + 1, tức là mọi (k + 1) - giác lồi (H) đều chia được thành một số hữu hạn các ngũ giác lồi. 16
Thật vậy, xét (k + 1) - giác lồi (H) = A1 A2 ...Ak Ak+1 . Trên các cạnh A1 Ak+1 và A3 A4 lần lượt lấy các điểm M, N khác các đỉnh. Đoạn MN chia (H) thành 2 đa giác: (H1 ) = M A1 A2 A3 N và (H2 ) = M N A4 A5 ...Ak Ak+1 Rõ ràng (H1 ) là ngũ giác lồi, còn (H2 ) là k giác lồi. Theo giả thiết quy Hình 1.3.13 nạp, (H2 ) chia được thành 1 số hữu hạn các ngũ giác lồi. Mệnh đề được chứng minh! Bài toán 1.3.14. (Chắp hình bằng quy nạp) Cho n hình vuông bất kỳ. Chứng minh có thể cắt chúng (bằng nhát cắt thẳng) làm một số mảnh đa giác, để từ đó có thể ghép lại thành 1 hình vuông lớn. Chứng minh. 1. Với n = 1, mệnh đề hiển nhiên đúng. Với n = 2, gọi độ dài các cạnh 2 hình vuông A1 B1 C1 D1 và A2 B2 C2 D2 tương ứng là x1 và x2 . Giả sử x1 ≥ x2 . Trên các cạnh của hình vuông A1 B1 C1 D1 ta lấy các điểm M, N, P, Q sao cho x1 + x2 A1 M = B1 N = C1 P = D1 Q = 2 Cắt hình vuông này theo các đoạn MP và NQ thì MP và NQ cắt nhau tại tâm O của nó và chúng vuông góc với nhau. Các đường đó chia hình vuông thành 4 phần bằng nhau, ta ghép những phần đó vào hình vuông A2 B2 C2 D2 như hình bên. Hình nhận được sẽ là hình vuông vì giá trị tại các góc M, N, P, Q bù nhau; các góc A, B, C, D vuông và AB = BC = CD = DA. 2. Giả sử mệnh đề đúng với n(n ≥ 1) hình vuông. Ta chứng minh mệnh đề cũng đúng với (n + 1) hình vuông. 17
Thật vậy, giả sử ta có n + 1 hình vuông (H1 ), (H2 ), ..., (Hn ), (Hn+1 ). Ta lấy ra 2 hình vuông bất kỳ, chẳng hạn (Hn ), (Hn+1 ). Theo phần 1, ta có thể cắt một trong hai hình vuông này và ghép các mảnh với hình vuông còn lại để được 1 hình vuông mới (H’). Như vậy, ta có n hình vuông (H1 ), (H2 ), ..., (Hn−1 ), (H 0 ). Theo giả thiết quy nạp, có thể cắt và ghép chúng thành một hình vuông mới. Ta có điều phải chứng minh! Hình 1.3.14 Bài toán 1.3.15. (Tô màu bằng quy nạp) Trên mặt phẳng cho n(n ≥ 1) hình tròn. Chứng minh có thể với bất kỳ cách sắp đặt nào, thì hình nhận được cũng có thể tô bằng 2 màu, để cho 2 phần mặt phẳng kề nhau (có biên chung) cũng được tô bằng hai màu khác nhau. Chứng minh. 1. Cơ sở quy nạp. Với n = 1, trên mặt phẳng chỉ có 1 hình tròn. Ta tô hình tròn bằng màu đen. Khi đó phần mặt phẳng còn lại kề với hình tròn được để trắng, nên hai phần của mặt phẳng kề nhau có màu khác nhau. 2. Quy nạp. Giả sử khẳng định đã đúng với bức tranh n hình tròn. Giả sử trên mặt phẳng cho n + 1 hình tròn tùy ý. Xóa đi 1 trong những hình tròn, sẽ được bức tranh gồm n hình tròn. Theo giả thiết quy nạp, bức tranh này chỉ cần tô bằng hai màu, chẳng hạn, đen, trắng mà hai miền kề nhau đều có màu khác nhau. Khôi phục lại hình tròn đã xóa đi, tức là trở lại hình xuất phát gồm n + 1 hình tròn, rồi theo 1 phía đối với hình tròn vừa khôi phục, chẳng 18
Hình 1.5 hạn phía trong của hình tròn này thay đổi các màu đã tô bằng màu ngược lại, sẽ được: bức tranh gồm n + 1 hình tròn được tô bằng hai màu, mà hai miền kề nhau tùy ý đều có màu khác nhau. Bài toán 1.3.16. (Dựng hình bằng quy nạp) Trên mặt phẳng cho (2n + 1) điểm. Hãy dựng một (2n + 1) giác để các điểm đã cho là trung điểm các cạnh của đa giác. Chứng minh. 1. Với n = 1, ta dựng tam giác ABC khi biết 3 trung điểm M, N, P bằng cách qua M, N, P lần lượt dựng các đường thẳng song song với NP, MP, MN. Chúng cắt nhau cho ta tam giác ABC. 2. Giả sử đối với 2(n − 1) + 1 điểm tùy ý không thẳng hàng dựng được đa giác (2n − 1) đỉnh có các điểm đã cho là trung điểm các cạnh. Ta chứng minh có thể dựng được (2n + 1) - giác từ trung điểm các cạnh của nó. Xét 2n+1 điểm tùy ý không có ba điểm nào thẳng hàng A1 , A2 , ..., A2n+1 . Giả sử các điểm này là trung điểm các cạnh của (2n + 1) - giác cần dựng B1 , B2 , ..., B2n+1 Xét tứ giác B1 B2n−1 B2n B2n+1 có A2n−1 A2n A2n+1 lần lượt là trung điểm các cạnh B2n−1 B2n , B2n B2n+1 , B2n+1 B1 . Gọi A là trung điểm B1 B2n−1 thì AA2n−1 A2n A2n+1 là hình bình hành. Vì A2n−1 , A2n , A2n+1 cho trước nên ta dựng được A. 19