Bài giảng Toán rời rạc - Chương: Quy nạp - Trần Vĩnh Đức
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 2 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 2 N.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương: Quy nạp - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Toán rời rạc - Chương: Quy nạp - Trần Vĩnh Đức
order can change. For example, the column move in Figure 3.9 changes the relative order of the pairs .G; H / and .G; E/. Lemma 3.3.5. A column move changes the relative order of exactly two pairs of tiles. Proof. Sliding a tile down moves it after the next two tiles in the order. Sliding a tile up moves it before the previous two tiles in the order. Either way, the relative order changes between the moved tile and each of the two tiles it crosses. The relative order between any other pair of tiles does not change. ⌅ These observations suggest that there are limitations on how tiles can be swapped. Some such limitation may lead to the invariant we need. In order to reason about swaps more precisely, let’s define a term referring to a pair of items that are out of order: Chuyển cột “mcs-ftl” — 2010/9/8 — 0:40 — page 62 — #68 Bổ đề 62 ChapterMỗi 3 lần Induction chuyển theo cột làm thay đổi thứ tự của đúng hai cặp chữ. CB A CB A FD FD G EH G EH (a) (b) Figure 3.9 An example of a column move in which the G-tile is moved into the adjacent hole above. In this case, G changes order with E and H. 23 / 37 Definition 3.3.6. A pair of letters L1 and L2 is an inversion if L1 precedes L2 in the alphabet, but L1 appears after L2 in the puzzle order. For example, in the puzzle below, there are three inversions: .D; F /, .E; F /, .E; G/. CB A GD F HE There is exactly one inversion .G; H / in the start state: CB A FE D GH “mcs-ftl” — 2010/9/8 — 0:40 — page 62 — #68 62 Chapter 3 Induction CB A CB A FD FD G “mcs-ftl” — 2010/9/8 — 0:40 — page 62 — #68 EH G EH (a) (b) 62 Chapter 3 Induction Figure 3.9 An example of a column move in which the G-tile is moved into the adjacent hole above. In this case, G changes order with E and H. CB A CB A Definition 3.3.6. A pair of letters L1 and L2 is an inversion if L1 precedes L2 in the alphabet, but L1 appears after L2 in the puzzle order.FD FD G For example, in the puzzle below, there are three inversions: .D; F /, .E; F /, .E; G/. EH G EH Cặp ngược (a) (b) CB A Figure 3.9 An example of a column move in which the G-tile is moved into the “mcs-ftl” — 2010/9/8 — 0:40 — page 63 — #69adjacent hole above. In this case, G changes order with E and H. GD F Định nghĩa L L L L Definition 3.3.6.HE A pair of letters 1 and 2 is an inversion if 1 precedes 2 in 3.3. Invariants the alphabet, but L appears63 after L in the puzzle order. Cặp chữ L1 và L2 gọi là ngược nếu L11 đứng trước 2L2 trong bảng chữ cái nhưng L1 lại đứngFor sau example,L2 trong in the ô puzzle chữ. below, there are three inversions: .D; F /, .E; F /, There are no inversions in theThere end state: is exactly one inversion.E; G/.G;. H / in the start state: CB A CB A CB A FE D FE D GD F HG GH HE Let’s work out the effects of row and column moves in termsThere of is inversions. exactly one inversion .G; H / in the start state: Lemma 3.3.7. During a move, the number of inversions can only increase by 2, decrease by 2, or remain the same. CB A FE D Proof. By Lemma 3.3.4, a row move does not change the order of the tiles,24 / and 37 so a row move does not change the number of inversions. By Lemma 3.3.5, a column move changes the relative order of exactly 2 pairs GH of tiles. There are three cases: If both pairs were originally in order, then the number of inversions after the move goes up by 2. If both pairs were originally inverted, then the number of inversions after the move goes down by 2. If one pair was originally inverted and the other was originally in order, then the number of inversions stays the same (since changing the former pair makes the number of inversions smaller by 1, and changing the latter pair makes the number of inversions larger by 1). ⌅ We are almost there. If the number of inversions only changes by 2, then what about the parity of the number of inversions? (The “parity” of a number refers to whether the number is even or odd. For example, 7 and 5 have odd parity, and 18 and 0 have even parity.) Since adding or subtracting 2 from a number does not change its parity, we have the following corollary to Lemma 3.3.7: Corollary 3.3.8. Neither a row move nor a column move ever changes the parity of the number of inversions. Now we can bundle up all these observations and state an invariant, that is, a property of the puzzle that never changes, no matter how you slide the tiles around. Lemma 3.3.9. In every configuration reachable from the configuration shown in Figure 3.7(a), the parity of the number of inversions is odd. Bổ đề Mỗi bước di chuyển, số cặp ngược chỉ có thể tăng 2, hoặc giảm 2, hoặc giữ nguyên. Chứng minh. Chuyển hàng: không đổi vì không làm thay đổi thứ tự các chữ Chuyển cột: sẽ làm thay đổi thứ tự đúng 2 cặp chữ. ▶ Nếu cả hai cặp này không ngược: số cặp ngược tăng 2. ▶ Nếu cả hai cặp này ngược: số cặp ngược giảm 2. ▶ Nếu trong hay cặp này chỉ có một cặp ngược: số cặp ngược giữ nguyên. 25 / 37 Hệ quả Trong mọi bước di chuyển, tính chẵn lẻ của số cặp ngược là không đổi. 26 / 37 “mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66 Bổ đề 60 Chapter 3 Induction Số cặp ngược trong trong mọi cấu hình đạt được từ CB A CB A CB A FE D FE D D F GH H G H E G (a) (b) (c) luôn là lẻ. 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 adjacent to the blank square can27 / be37 slid into the blank. ⇥ For example, a sequence of two moves is illustrated in Figure 3.7. In the initial configuration shown in Figure 3.7(a), the G and H tiles are out of order. We can find a way of swapping G and H so that they are in the right order, but then other letters may be out of order. Can you find a sequence of moves that puts these two letters in correct order, but returns every other tile to its original position? Some experimentation suggests that the answer is probably “no,” and we will prove that is so by finding an invariant, namely, a property of the puzzle that is always maintained, no matter how you move the tiles around. If we can then show that putting all the tiles in the correct order would violate the invariant, then we can conclude that the puzzle cannot be solved. Theorem 3.3.3. No sequence of legal moves transforms the configuration in Fig- ure 3.7(a) into the configuration in Figure 3.8. We’ll build up a sequence of observations, stated as lemmas. Once we achieve a critical mass, we’ll assemble these observations into a complete proof of Theo- rem 3.3.3. Define a row move as a move in which a tile slides horizontally and a column move as one in which the tile slides vertically. Assume that tiles are read top- to-bottom and left-to-right like English text, that is, the natural order, defined as follows: So when we say that two tiles are “out of order”, we mean that the larger letter precedes the smaller letter in this natural order. Our difficulty is that one pair of tiles (the G and H) is out of order initially. An immediate observation is that row moves alone are of little value in addressing this “mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66 Chứng minh bằng quy nạp. 60 Chapter 3 Induction Đặt P(n) là mệnh đề : “ Số cặp ngược trong cấu hình đạt được từ CB A CB A CB A FE D FE D D F GH H G H E G (a) (b) (c) sau n bước chuyển luônFigure là 3.7 lẻ” The 8-Puzzle in its initial configuration (a) and after one (b) and ▶ Bước cơ sở: Ptwo(0) (c)đúng. possible Tại moves. sao? ▶ Bước quy nạp: Giả sử P(n) đúng, do hệ quả trước về tính chẵn lẻ không đổi3.3.4 của The số cặp 8-Puzzle ngược. Ta được P(n + 1) đúng. In the 8-Puzzle, there are 8 lettered tiles (A–H) and a blank square arranged in a 3 3 grid. Any lettered tile adjacent to the blank square can be slid into the blank. ⇥ For example, a sequence of two moves28 is / 37illustrated in Figure 3.7. In the initial configuration shown in Figure 3.7(a), the G and H tiles are out of order. We can find a way of swapping G and H so that they are in the right order, but then other letters may be out of order. Can you find a sequence of moves that puts these two letters in correct order, but returns every other tile to its original position? Some experimentation suggests that the answer is probably “no,” and we will prove that is so by finding an invariant, namely, a property of the puzzle that is always maintained, no matter how you move the tiles around. If we can then show that putting all the tiles in the correct order would violate the invariant, then we can conclude that the puzzle cannot be solved. Theorem 3.3.3. No sequence of legal moves transforms the configuration in Fig- ure 3.7(a) into the configuration in Figure 3.8. We’ll build up a sequence of observations, stated as lemmas. Once we achieve a critical mass, we’ll assemble these observations into a complete proof of Theo- rem 3.3.3. Define a row move as a move in which a tile slides horizontally and a column move as one in which the tile slides vertically. Assume that tiles are read top- to-bottom and left-to-right like English text, that is, the natural order, defined as follows: So when we say that two tiles are “out of order”, we mean that the larger letter precedes the smaller letter in this natural order. Our difficulty is that one pair of tiles (the G and H) is out of order initially. An immediate observation is that row moves alone are of little value in addressing this “mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66 “mcs-ftl” — 2010/9/8 — 0:40 — page 61 — #67 Định lý 60 Chapter 3 Induction Không tồn tại dãy3.3. Invariantschuyển hợp lệ để chuyển từ 61 CB A CB A CB A CB A FE D sang FE D FE D D F GH H G HG 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. 43 2 3.3.4 The 8-Puzzle 76 5 In the 8-Puzzle, there are 8 lettered tiles (A–H) and a blank square arranged in a 3 3 grid. Any lettered tile adjacent to the blank square can be slid into the blank. ⇥ 98 : 29 / 37 For example, a sequence of two moves is illustrated in Figure 3.7. In the initial configuration shown in Figure 3.7(a), the G and H tiles are out of order. We can find a way of swapping G and H so that they are in the right order, but then otherproblem: letters may be out of order. Can you find a sequence of moves that puts these two letters in correct order, but returns every other tile to its original Lemma 3.3.4. A row move does not change the order of the tiles. position? Some experimentation suggests that the answer is probably “no,” and we will proveProof. that is soA byrow finding move an moves invariant, a tile namely, from cell a propertyi to cell ofi the1 puzzleor vice that versa. is This tile C always maintained,does not change no matter its how order you with move respect the tilesto any around. other tile. If we Since can then no other show tile moves, that puttingthere all the is no tiles change in the in correct the order order of would any of violate the other the pairs invariant, of tiles. then we can ⌅ conclude that the puzzle cannot be solved. Let’s turn to column moves. This is the more interesting case, since here the Theoremorder 3.3.3. canNo change. sequence For of example, legal moves the columntransforms move the in configuration Figure 3.9 changes in Fig- the relative ure 3.7(a)order into the of configurationthe pairs .G; H in / Figureand .G;3.8 E/. . We’ll buildLemma up a 3.3.5. sequenceA column of observations, move changes stated the as relativelemmas. order Once of we exactly achieve two pairs of a critical mass,tiles. we’ll assemble these observations into a complete proof of Theo- rem 3.3.3.Proof. Sliding a tile down moves it after the next two tiles in the order. Sliding a Define atilerow up move movesas it a before movein the which previous a tile two slides tiles horizontally in the order. and Either a column way, the relative move as oneorder in changeswhich the between tile slides the vertically.moved tile Assume and each that of the tiles two are tiles read it top- crosses. The to-bottomrelative and left-to-right order between like English any other text, pair that of is, tiles the doesnatural not change. order, defined as ⌅ follows: So when we say that two tiles are “out of order”, we mean that the larger letter precedesThese the smaller observations lettersuggest in this natural that there order. are limitations on how tiles can be swapped. Our difficultySome suchis that limitation one pair mayof tiles lead (the to G the and invariant H) is out we of need. order In initially. order to An reason about immediateswaps observation more precisely, is that row let’s moves define alone a term are of referring little value to a in pair addressing of items thisthat are out of order: Nội dung Nguyên lý quy nạp Quy nạp mạnh Bài tập Hãy dùng quy nạp để chứng minh rằng mọi số nguyên dương đều phân tích được thành tích của các số nguyên tố. 31 / 37 Nguyên lý quy nạp mạnh Xét vị từ P(n) trên N. Nếu ▶ P(0) đúng, và ▶ với mọi n ∈ N, (P(0) ∧ P(1) ∧ · · · ∧ P(n)) ⇒ P(n + 1), thì P(n) đúng với mọi n ∈ N. 32 / 37 Ví dụ Ở nước Quy nạp, họ dùng đơn vị tiền Mạnh. Họ chỉ có hai loại tiền 3M (Mạnh) và 5M. Dù họ có vấn đề nhỏ với việc đổi tiền 4M hoặc 7M, nhưng họ nhận thấy rằng họ có thể đổi mọi số tiền ít nhất 8M. Hãy giải thích cho họ xem tại sao điều này đúng. 33 / 37 Unstacking Game ▶ Có một chồng hộp. Bạn sẽ thực hiện một dãy bước chuyển. ▶ Mỗi bước chuyển bạn chia một hộp kích thước (a + b) thành hai chồng khác rỗng kích thước a và b. Và bạn được ab điểm cho bước chuyển này. ▶ Trò chơi kết thúc khi mỗi chồng hộp chỉ còn một hộp. ▶ Điểm của bạn là tổng điểm bạn đạt được ở mỗi bước. ▶ Hãy tìm một chiến lược chơi để tối đa hoá điểm của bạn? 34 / 37 Một chiến lược kiểu “chia đôi” cho trò chơi với n = 10 đĩa Điểm 10 5 5 25 5 3 2 6 3 3 2 2 6 2 3 2 2 1 2 1 3 2 2 1 1 1 1 2 2 2 1 1 1 2 1 1 2 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 45 35 / 37 Định lý Mọi chiến lược của trò chơi gồm chồng n hộp đều cho cùng điểm n(n − 1) S(n) = . 2 36 / 37 Chứng minh. Ta gọi P(n) là mệnh đề S(n) = n(n − 1)/2. Bước cơ sở: P(0) đúng vì S(0) = 0. Bước quy nạp: Giả sử P(0) ∧ · · · ∧ P(n) đúng để chứng minh P(n + 1). Xét trò chơi với n + 1 đĩa. Ta chia n + 1 đĩa này tùy ý thành hai phần không rỗng a, b thỏa mãn a + b = n + 1. Theo giả thiết quy nạp, ta được a(a − 1) b(b − 1) S(a + b) = S(a) + S(b) + ab = + + ab 2 2 a2 − a + b2 − b + 2ab (a + b)2 − (a + b) = = 2 2 (a + b)(a + b − 1) (n + 1)n = = 2 2 37 / 37
File đính kèm:
- bai_giang_toan_roi_rac_chuong_quy_nap_tran_vinh_duc.pdf