Bài giảng Toán rời rạc: Quy nạp - Trần Vĩnh Đức

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

Thêm vào BST

Báo xấu

72
lượt xem 2
download

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

Bài giảng Toán rời rạc: Quy nạp cung cấp cho người học những nội dung kiến thức như: Nguyên lý quy nạp, quy nạp mạnh, ví dụ chứng minh sai, 15-Puzzle, 8-Puzzle, chuyển hàng, chuyển cột,... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Quy nạp - Trần Vĩnh Đức

Quy nạp Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 37
Tài liệu tham khảo ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ Kenneth H. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch Tiếng Việt) CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 37
Nội dung Nguyên lý quy nạp Quy nạp mạnh CuuDuongThanCong.com https://fb.com/tailieudientucntt
Nguyên lý quy nạp 880 81 777879 82 3 84 73747576 88 87 8685 72 71 70 69 68 67 666564 63661 260 59 58 5354 557 556 505152 49 48 47 46 45 4443 2 4 4140 9 3 3387 35 34 36 Xét vị từ P(n) trên N. Nếu 2 3 33133 0 2 2 28 9 2256 7 ▶ P(0) đúng, và 24 23 22 22109 ▶ với mọi n ∈ N, (P(n) ⇒ P(n + 1)) 1 8 1 1716 cũng đúng, 151143 2 110 11 thì P(n) đúng với mọi n ∈ N. 789 56 4 3 2 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 37
Ví dụ Định lý Với mọi n ∈ N, n(n + 1) 1 + 2 + ··· + n = 2 Đặt P(n) là mệnh đề ∑ n n(n + 1) i= 2 i=1 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 37
Chứng minh. ▶ Bước cơ sở: P(0) đúng. ▶ Bước quy nạp: Ta sẽ chứng minh: với mọi n ≥ 0, mệnh đề P(n) ⇒ P(n + 1) đúng. Thật vậy, giả sử P(n) đúng, với n là một số nguyên bất kỳ. Vì 1 + 2 + · · · + n + (n + 1) = (1 + 2 + · · · + n) + (n + 1) n(n + 1) = + (n + 1) 2 (n + 1)(n + 2) = 2 nên P(n + 1) đúng. Theo quy nạp ta có P(n) đúng với mọi số n ∈ N. CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 37
Ví dụ Chứng minh rằng 1 1 1 1 + + + ··· + n < 1 2 4 8 2 với mọi n ≥ 1. CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 37
Ví dụ Định lý Với mọi n ∈ N, ta có n3 − n chia hết cho 3. Đặt P(n) là mệnh đề ”n3 − n chia hết cho 3.” CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 37
Chứng minh. ▶ Bước cơ sở: P(0) đúng vì 03 − 0 = 0 chia hết cho 3. ▶ Bước quy nạp: Ta sẽ chứng minh rằng, với mọi n ∈ N, mệnh đề P(n) ⇒ P(n + 1) đúng. Thật vậy, giả sử P(n) đúng, với n là một số nguyên bất kỳ. Vì (n + 1)3 − (n + 1) = n3 + 3n2 + 3n + 1 − n − 1 = n3 + 3n2 + 2n = n3 − n + 3n2 + 3n = (n3 − n) + 3(n2 + n) chia hết cho 3 nên P(n + 1) đúng. Theo quy nạp ta có P(n) đúng với mọi số n ∈ N. CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 37
Ví dụ chứng minh sai Định lý (Sai) Mọi con ngựa đều cùng màu. Đặt P(n) là mệnh đề ”Trong mọi tập gồm n con ngựa, các con ngựa đều cùng màu.” CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 37
Đặt P(n) là mệnh đề ”Trong mọi tập gồm n con ngựa, các con ngựa đều cùng màu.” Chứng minh Sai. ▶ Bước cơ sở: P(1) đúng vì chỉ có một con ngựa. ▶ Bước quy nạp: Giả sử P(n) đúng để chứng minh P(n + 1) đúng. Xét tập gồm n + 1 con ngựa {h1 , h2 , · · · , hn+1 } ▶ Các con h1 , h2 , . . . , hn có cùng màu (giả thiết quy nạp). ▶ Các con h2 , h3 , . . . , hn+1 có cùng màu (giả thiết quy nạp). Vậy màu(h1 ) = màu(h2 , . . . , hn ) = màu(hn+1 ). Vậy các con ngựa {h1 , h2 , · · · , hn+1 } đều cùng màu. Có nghĩa rằng P(n + 1) đúng. Theo quy nạp ta có P(n) đúng với mọi số n ∈ N. CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 37
Bài tập 1. Chứng minh rằng ∑ n n(n + 1)(2n + 1) i2 = 6 i=1 2. Chứng minh rằng 2n > n2 với n ≥ 5. 3. Chứng minh rằng với mọi n ≥ 1, F(n − 1)F(n + 1) − F(n2 ) = (−1)n với F(i) là số Fibonacci thứ i. CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 37
a proof technique in the preceding examples. But induction rwise, there are four central squares.) A complica Vígeneral more dụ lát gạch tool. reasoning ntional architect, d a new computer Frank science building. As Gehry, insisted the project went further that only spec here were some radical fundraising ideas. One plan was to dimensions 2n ⇥ 2n : A courtyard meeting these constraints exsists, at least for n = 2: B 2n 2n Hình:toLát For larger values of n, is there a way tile agạch 2n ⇥và2n đặt courtyard with L-s Hình: Let’s Hình: Sânstatue in the center? Gạchtry to prove tượngthat Billthis is so. would be occupied by a statue of a wealthy potential donor. g these constraints exsists, at least for n = 2: e special case n = 0, the whole15. Theorem courtyard For all n consists 0 thereof a single exists a tiling of a 2n ⇥ 2n courtyard wi there are four central square. squares.) A complication was that the architect, Frank Gehry, insisted that only special L-shaped tiles CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 37
Định lý Với mọi n, luôn có cách lát gạch một sân 2n × 2n chỉ để lại một ô trống ở giữa (để đặt tượng Bill). CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 37
Chứng minh thử. Xét P(n) là mệnh đề ”Có cách lát gạch sân 2n × 2n để lại một ô ở giữa.” ▶ Bước cơ sở: P(0) đúng vì chỉ có một ô dành cho Bill. ▶ Bước quy nạp: ! CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 37
Proof. (successful attempt) The proof is by induction. Let P (n) be the propo every location of Bill in a 2n ⇥ 2n courtyard, there exists a tiling of the rema Chứng minh. Base case: P (0) is true because Bill fills the whole courtyard. Inductive step: Asume that P (n) is true for some n 0; that is, for every loc Xét P(n) là mệnh đềa 2n ⇥ 2n courtyard, there exists a tiling of the remainder. Divide the 2n+1 ⇥ 2 into four quadrants, each 2n ⇥ 2n . One quadrant contains Bill (B in the dia ”Với mỗi vị Place trí đặt tượng Bill a temporary Bill(Xtrong sân 2nin×each in the diagram) 2n of , ta theđều three central squares this quadrant: có cách lát gạch kín sân.” B ▶ Bước cơ sở: P(0) đúng vì chỉ có 2n một ô dành cho Bill. X X X ▶ Bước quy nạp: Giả sử P(n) đúng, 2n ta chứng minh P(n + 1) đúng. 2n 2n Theo quy nạp ta có P(n) đúng với mọi số n ∈ N. CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 37
“mcs-ftl” “mcs-ftl” — — 2010/9/8 2010/9/8 — — 0:40 0:40 — — page page 59 59 — — #65 #65 15-Puzzle 3.3. 3.3.Invariants Invariants 59 59 22 33 44 55 2 3 4 55 66 77 88 99 6 7 8 99 ⇒ :: 21 21 22 22 23 23 : 21 22 24 24 26 26 25 25 24 24 26 26 25 25 23 23 (a) (a) (b) (b) Figure3.5 Chuyển Figure 3.5 The hợp The15-puzzle lệ: di15-puzzle chuyển in its in its starting một starting configuration số sang (a)cạnh ô trống(a) configuration and and after nó.the after the 12-block 12-block isismoved movedinto intothe thehole holebelow below(b). (b). 22 33 44 55 CuuDuongThanCong.com 6 7 8 https://fb.com/tailieudientucntt 6 7 8 99 17 / 37
6 7 8 9 6 7 8 9 15-Puzzle : 21 22 23 : 21 22 24 — 26 “mcs-ftl” — 2010/9/8 — 0:40 25 — #65 page 59 24 26 25 23 (a) (b) Có thể chuyển từ 3.3. Invariants Figure 3.5 The 15-puzzle in its starting configuration 59 (a) and after the 12-block is moved into the hole below (b). 2 3 4 5 2 23 34 45 5 6 7 8 9 6 67 78 89 9 sang : 21 22 23 : 21 : 22 21 22 23 24 26 25 24 26 24 25 25 23 26 (a) (b) Figure 3.6 The desired final configuration for the 15-puzzle. Can it be achieved không? Figure 3.5 The 15-puzzle in its starting configuration (a) and after the 12-block by only moving one block at a time into an adjacent hole? is moved into the hole below (b). get all 15 blocks into their natural order. A picture of the 15-puzzle is shown in Figure 2 3.5 along 3 4 the5 configuration after the 12-block is moved into the hole with below. The desired final configuration is shown in Figure 3.6. The6 15-puzzle 7 became 8 9 very popular in North America and Europe and is still sold in game and puzzle shops today. Prizes were offered for its solution, but it is doubtful : 21 that22they were 23 ever awarded, since it is impossible to get from the CuuDuongThanCong.com configuration in Figure 3.5(a) to the configuration in Figure 3.6 by only moving https://fb.com/tailieudientucntt 18 / 37 one block at a time into an adjacent hole. The proof of this fact is a little tricky so
8-Puzzle “mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66 Chapter 3 Induction A B C A B C A B C D E F D E F D F H G H G H E G (a) (b) (c) Figure 3.7 The 8-Puzzle in its initial configuration (a) and after one (b) and two (c) possible moves. 3.3.4 The 8-Puzzle In the 8-Puzzle, there are 8 lettered tiles (A–H) and a blank square arranged in a 3 ⇥ 3 grid. Any lettered tile CuuDuongThanCong.com adjacent to the blank square can be slid into the blank. https://fb.com/tailieudientucntt 19 / 37
8-Puzzle “mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66 “mcs-ftl” — 2010/9/8 — 0:40 — page 61 — #67 Bài tập 60 Chapter 3 Induction Liệu có thể tìm 3.3. được một dãy chuyển hợp lệ để chuyển từ Invariants A B C A B A C B CA B C D E F sang D E D F E FD F H G H G G H H E G (a) (b) (c) Figure 3.8 The desired final configuration of the 8-puzzle. Figure 3.7 The 8-Puzzle in its initial configuration (a) and after one (b) and two (c) possible moves. 2 3 4 3.3.4 The 8-Puzzle 5 6 7 CuuDuongThanCong.com In the 8-Puzzle, there are 8 lettered tiles (A–H) and a blank square arranged in20a/ 37 https://fb.com/tailieudientucntt