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. ▶ 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?
37 trang |
Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 565 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh Đức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Quy nạp
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
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)
2 / 37
Nội dung
Nguyên lý quy nạp
Quy nạp mạnh
Nguyên lý quy nạp
Xét vị từ P(n) trên N. Nếu
▶ P(0) đúng, và
▶ với mọi n ∈ N, (P(n)⇒ P(n+ 1))
cũng đúng,
thì P(n) đúng với mọi n ∈ N.
88
878685848382107978777675747372717069686766656463626160595875655545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321
4 / 37
Ví dụ
Định lý
Với mọi n ∈ N,
1 + 2 + · · ·+ n = n(n+ 1)
2
Đặt P(n) là mệnh đề
n∑
i=1
i = n(n+ 1)
2
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)
2
+ (n+ 1)
=
(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.
6 / 37
Ví dụ
Chứng minh rằng
1
2
+
1
4
+
1
8
+ · · ·+ 1
2n
< 1
với mọi n ≥ 1.
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.”
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.
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.”
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.
11 / 37
Bài tập
1. Chứng minh rằng
n∑
i=1
i2 = n(n+ 1)(2n+ 1)
6
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.
12 / 37
Ví dụ lát gạch
Induction I 31
2.6 Courtyard Tiling
Induction served purely as a proof technique in the preceding examples. But induction
sometimes can serve as a more genera reasoning tool.
MIT recently constructed a new computer science building. As the project went further
and further over budget, there were some radical fundraising ideas. One plan was to
install a big courtyard with dimensions 2n ⇥ 2n:
2n
2n
One of the central squares would be occupied by a statue of a wealthy potential donor.
Let’s call him “Bill”. (In the special case n = 0, the whole courtyard consists of a single
central square; otherwise, there are four central squares.) A complication was that the
building’s unconventional architect, Frank Gehry, insisted that only special L-shaped tiles
be used:
A courtyard meeting these constraints exsists, at least for n = 2:
B
For larger values of n, is there a way to tile a 2n ⇥ 2n courtyard with L-shaped tiles and a
statue in the center? Let’s try to prove that this is so.
Theorem 15. For all n 0 there exists a tiling of a 2n ⇥ 2n courtyard with Bill in a central
square.
Hình: Sân
Induction I 31
2.6 Courtyard Tiling
Induction served purely as a proof technique in the preceding examples. But induction
sometimes can serve as a more general reasoning tool.
MIT recently constructed a new computer science building. As the project went further
and further over budget, there were some radical fundraising ideas. One plan was to
install a big courtyard with dimensions 2n ⇥ 2n:
2n
2n
One of the central squares would be occupied by a statue of a wealthy potential donor.
Let’s call him “Bill”. (In the special case n = 0, the whole courtyard consists of a single
central square; otherwise, there are four central squares.) A complication was that the
building’s un nventional archit t, Frank Gehry, insis ed that only special L-shaped tiles
be used:
A courtyard meeting these constraints exsists, at least for n = 2:
B
For larger values of n, is there a way to tile a 2n ⇥ 2n courtyard with L-shaped tiles and a
statue in the center? Let’s try to prove that this is so.
Theorem 15. For all n 0 there exists a tiling of a 2n ⇥ 2n courtyard with Bill in a central
square.
Hình: Gạch
Induction I 31
2.6 Courtyard Tiling
Induction served purely as a proof technique in the preceding examples. But induction
sometimes can serve as a more general reasoning tool.
MIT recently constructed a new computer science building. As the project went further
and further over budget, there were some radical fundraising ideas. One plan was to
install a big courtyard with dimensions 2n ⇥ 2n:
2n
2n
One of the central squares would be occupied by a statue of a wealthy potential donor.
Let’s call him “Bill”. (In the special case n = 0, the whole courtyard consists of a single
central square; otherwise, there are four central squares.) A complication was that the
building’s unconventional architect, Frank Gehry, insisted that only special L-shaped tiles
be used:
A courtyard meeting these constraints exsists, at least for n = 2:
B
For larger values of n, is there a way to tile a 2n ⇥ 2n courtyard with L-shaped tiles and a
statue in the center? Let’s try to prove that this is so.
Theorem 15. For all n 0 there exist a tiling of a 2n ⇥ 2n courtyard with Bill in a central
square.
Hình: Lát gạch và đặt
tượng Bill
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).
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: !
15 / 37
Chứng minh.
Xét P(n) là mệnh đề
”Với mỗi vị trí đặt tượng Bill trong sân 2n×2n, ta đều
có cách lát gạch kín sân.”
▶ Bước cơ sở: P(0) đúng vì chỉ có
một ô dành cho Bill.
▶ Bước quy nạp: Giả sử P(n) đúng,
ta chứng minh P(n+ 1) đúng.
32 Induction I
Proof. (doomed attempt) The proof is by induction. Let P (n) be the proposition that there
exists a tiling of a 2n ⇥ 2n courtyard with Bill in the center.
Base case: P (0) is true because Bill fills the whole courtyard.
Inductive step: Assume that there is a tiling of a 2n ⇥ 2n courtyard with Bill in the center
for some n 0. We must prove that there is a way to tile a 2n+1⇥ 2n+1 courtyard with Bill
in the center...
Nowwe’re in trouble! The ability to tile a smaller courtyard with Bill in the center does
not help tile a larger courtyard with Bill in the center. We can not bridge the gap between
P (n) and P (n+ 1). The usual recipe for finding an inductive proof will not work!
When this happens, your first fallback should be to look for a stronger induction hy-
pothesis; that is, one which implies your previous hypothesis. For example, we could
make P (n) the proposition that for every location of Bill in a 2n⇥2n courtyard, there exists
a tiling of the remainder.
This advice may sound bizzare: “If you can’t prove something, try to prove something
more grand!” But for induction arguments, this makes sense. In the inductive step, where
you have to prove P (n)) P (n+ 1), you’re in better shape because you can assume P (n),
which is now a more general, more useful statement. Let’s see how this plays out in the
case of courtyard tiling.
Proof. (successful attempt) The proof is by induction. Let P (n) be the proposition that for
every location of Bill in a 2n ⇥ 2n courtyard, there exists a tiling of the remainder.
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 location of Bill in
a 2n⇥2n courtyard, there exists a tiling of the remainder. Divide the 2n+1⇥2n+1 courtyard
into four quadrants, each 2n ⇥ 2n. One quadrant contains Bill (B in the diagram below).
Place a temporary Bill (X in the diagram) in each of the three central squares lying outside
this quadrant:
X
X X
B
2n 2n
2n
2n
Theo quy nạp ta có P(n) đúng với mọi số n ∈ N.
16 / 37
15-Puzzle“mcs-ftl” — 2010/9/8 — 0:40 — page 59 — #65
3.3. Invariants 59
252624
2221: 23
876 9
432 5
(a)
252624
2221:
23
876 9
432 5
(b)
Figure 3.5 The 15-puzzle in its starting configuration (a) and after the 12-block
is moved into the hole below (b).
262524
2221: 23
876 9
432 5
Figure 3.6 The desired final configuration for the 15-puzzle. Can it be achieved
by only moving one block at a time into an adjacent hole?
get all 15 blocks into their natural order. A picture of the 15-puzzle is shown in
Figure 3.5 along with the configuration after the 12-block is moved into the hole
below. The desired final configuration is shown in Figure 3.6.
The 15-puzzle became 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 that they were ever awarded, since it is impossible to get from the
configuration in Figure 3.5(a) to the configuration in Figure 3.6 by only moving
one block at a time into an adjacent hole. The proof of this fact is a little tricky so
we have left it for you to figure out on your own! Instead, we will prove that the
analogous task for the much easier 8-puzzle cannot be performed. Both proofs, of
course, make use of the Invariant Method.
⇒
“mcs-ftl” — 2010/9/8 0:40 page 59 #65
3. . Invariants 59
252624
2221: 23
876 9
432 5
(a)
252624 23
(b)
Figure 3.5 The 15-puzzle in its starting configuration (a) and after the 12-block
is moved into the hole below (b).
262524
2221: 23
876 9
432 5
Figure 3.6 The desired final configuration for the 15-puzzle. Can it be achieved
by only moving one block at a time into an adjacent hole?
get all 15 blocks into their natural order. A picture of the 15-puzzle is shown in
Figure 3.5 along with the configuration after the 12-block is moved into the hole
below. The desired final configuration is shown in Figure 3.6.
The 15-puzzle became 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 that they were ever awarded, since it is impossible to get from the
configuration in Figure 3.5(a) to the configuration in Figure 3.6 by only moving
one block at a time into an adjacent hole. The proof of this fact is a little tricky so
we have left it for you to figure out on your own! Instead, we will prove that the
analogous task for the much easier 8-puzzle cannot be performed. Both proofs, of
course, make use of the Invariant Method.
Chuyển hợp lệ: di chuyể một số sang ô trố g cạ h nó.
17 / 37
15-Puzzle
Có thể chuyển từ
“mcs-ftl” — 2010/9/8 — 0:40 — page 59 — #65
3.3. Invariants 59
252624
2221: 23
876 9
432 5
(a)
252624
2221:
23
876 9
432 5
(b)
Figure 3.5 The 15-puzzle in its starting configuration (a) and after the 12-block
is moved into the hole below (b).
262524
2221: 23
876 9
432 5
Figure 3.6 The desired final configuration for the 15-puzzle. Can it be achieved
by only moving one block at a time into an adjacent hole?
get all 15 blocks into their natural order. A picture of the 15-puzzle is shown in
Figure 3.5 along with the configuration after the 12-block is moved into the hole
below. The desired final configuration is shown in Figure 3.6.
The 15-puzzle became 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 that they were ever awarded, since it is impossible to get from the
configuration in Figure 3.5(a) to the configuration in Figure 3.6 by only moving
one block at a time into an adjacent hole. The proof of this fact is a little tricky so
we have left it for you to figure out on your own! Instead, we will prove that the
analogous task for the much easier 8-puzzle cannot be performed. Both proofs, of
course, make use of the Invariant Method.
sang
“mcs-ftl” — 2010/9/8 — 0:40 — page 59 — #65
3.3. Invariants 59
252624
2221: 23
876 9
432 5
(a)
252624
2221:
23
876 9
432 5
(b)
Figure 3.5 The 15-puzzle in its starting configuration (a) and after the 12-block
is moved into the hole below (b).
262524
221: 23
876 9
432 5
Figure 3.6 The desired final configuration for the 15-puzzle. Can it be achieved
by only moving one block at a time into an adjacent hole?
get all 15 blocks into their natural order. A picture of the 15-puzzle is shown in
Figure 3.5 along with the configuration after the 12-block is moved into the hole
below. The desired final configuration is shown in Figure 3.6.
The 15-puzzle became 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 that they were ever awarded, since it is impossible to get from the
configuration in Figure 3.5(a) to the configuration in Figure 3.6 by only moving
one block at a time into an adjacent hole. The proof of this fact is a little tricky so
we have left it for you to figure out on your own! Instead, we will prove that the
analogous task for the much easier 8-puzzle cannot be performed. Both proofs, of
course, make use o the Invariant Method.
không?
18 / 37
8-Puzzle“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
Chapter 3 Induction60
GH
FED
CBA
(a)
GH
FED
CBA
(b)
GEH
FD
CBA
(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 adjacent to the blank square can be 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
19 / 37
8-Puzzle
Bài tập
Liệu có thể tìm được một dãy chuyển hợp lệ để chuyển từ
“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
Chapter 3 Induction60
GH
FED
CBA
(a)
GH
FED
CBA
(b)
GEH
FD
CBA
(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 adjacent to the blank square can be 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
sang
“mcs-ftl” — 2010/9/8 — 0:40 — page 61 — #67
3.3. Invariants 61
HG
FED
CBA
Figure 3.8 The desired final configuration of the 8-puzzle.
98 :
765
432
problem:
Lemma 3.3.4. A row move does not change the order of the tiles.
Proof. A row move moves a tile from cell i to cell i C 1 or vice versa. This tile
does not change its order with respect to any ther tile. Since no ot er tile moves,
there is no change in the order of any of the other pairs of tiles. ⌅
Let’s turn to column moves. This is the more interesting case, since here the
order can change. For example, the column ove 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:
20 / 37
Định lý
Không tồn tại dãy chuyển cho bài toán trên.
21 / 37
Chuyển hàng
Thứ tự tự nhiên của các chữ trên ô:
“mcs-ftl” — 2010/9/8 — 0:40 — page 61 — #67
3.3. Invariants 61
HG
FED
CBA
Figure 3.8 The desired final configuration of the 8-puzzle.
98 :
765
432
problem:
Lemma 3.3.4. A row move does not change the order of the tiles.
Proof. A row move moves a tile from cell i to cell i C 1 or vice versa. This tile
does not change its order with respect to any other tile. Since no other tile moves,
there is no change in the order of any of the other pairs of tiles. ⌅
Let’s turn to column moves. This is the more interesting case, since here the
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:
Bổ đề
Mỗi lần chuyển hàng không làm thay đổi thứ tự các chữ.
22 / 37
Chuyển cột
Bổ đề
Mỗi lần chuyển theo cột làm thay đổi thứ tự của đúng hai cặp chữ.
“mcs-ftl” — 2010/9/8 — 0:40 — page 62 — #68
Chapter 3 Induction62
EH G
FD
CBA
(a)
EH
GFD
CBA
(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 andH .
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/.
HE
GDF
CBA
There is exactly one inversion .G;H/ in the start state:
GH
FED
CBA
23 / 37
Cặp ngược
Định nghĩa
Cặp chữ L1 và L2 gọi là ngược nếu L1 đứng trước L2 trong bảng
chữ cái nhưng L1 lại đứng sau L2 trong ô chữ.
“mcs-ftl” — 2010/9/8 — 0:40 — page 63 — #69
3.3. Invariants 63
There are no inversions in the end state:
HG
FED
CBA
Let’s work out the effects of row and column moves in terms of inversions.
Lemma 3.3.7. During a move, the number of inversions can only increase by 2,
decrease by 2, or remain the same.
Proof. By Lemma 3.3.4, a row move does not change the order of the tiles, and 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
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.
“mcs-ftl” — 2010/9/8 — 0:40 — page 62 — #68
Chapter 3 Induction62
EH G
FD
CBA
(a)
EH
GFD
CBA
(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 andH .
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/.
HE
GDF
CBA
There is xactly one inversion .G;H/ in the start state:
GH
FED
CBA
“mcs-ftl” — 2010/9/8 — 0:40 — page 62 — #68
Chapter 3 Induction62
EH G
FD
CBA
(a)
EH
GFD
CBA
(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 andH .
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, i the puzzle below, there are three inversions: .D; F /, .E; F /,
.E;G/.
HE
GDF
CBA
There is exactly one inversion .G;H/ in the start state:
GH
FED
CBA
24 / 37
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
Bổ đề
Số cặp ngược trong trong mọi cấu hình đạt được từ
“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
Chapter 3 Induction60
GH
FED
CBA
(a)
GH
FED
CBA
(b)
GEH
FD
CBA
(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 adjacent to the blank square can be 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
luôn là lẻ.
27 / 37
Chứng minh bằng quy nạp.
Đặt P(n) là mệnh đề : “ Số cặp ngược trong cấu hình đạt được từ
“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
Chapter 3 Induction60
GH
FED
CBA
(a)
GH
FED
CBA
(b)
GEH
FD
CBA
(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 adjacent to the blank square can be 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
sau n bước chuyển luôn là lẻ”
▶ Bước cơ sở: P(0) đúng. Tại sao?
▶ Bước quy nạp: Giả sử P(n) đúng, do hệ quả trước về tính
chẵn lẻ không đổi của số cặp ngược. Ta được P(n+ 1) đúng.
28 / 37
Định lý
Không tồn tại dãy chuyển hợp lệ để chuyển từ
“mcs-ftl” — 2010/9/8 — 0:40 — page 60 — #66
Chapter 3 Induction60
GH
FED
CBA
(a)
GH
FED
CBA
(b)
GEH
FD
CBA
(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 adjacent to the blank square can be 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
sang
“mcs-ftl” — 2010/9/8 — 0:40 — page 61 — #67
3.3. Invariants 61
HG
FED
CBA
Figure 3.8 The desired final configuration of the 8-puzzle.
98 :
765
432
problem:
Lemma 3.3.4. A row move does not change the order of the tiles.
Proof. A row move moves a tile from cell i to cell i C 1 or vice versa. This tile
does not change its order with respect to any ther tile. Since no ot er tile moves,
there is no change in the order of any of the other pairs of tiles. ⌅
Let’s turn to column moves. This is the more interesting case, since here the
order can change. For example, the column ove 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:
29 / 37
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
S(n) = n(n− 1)
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
S(a+ b) = S(a) + S(b) + ab = a(a− 1)
2
+
b(b− 1)
2
+ ab
=
a2 − a+ b2 − b+ 2ab
2
=
(a+ b)2 − (a+ b)
2
=
(a+ b)(a+ b− 1)
2
=
(n+ 1)n
2
3
37 / 37
Các file đính kèm theo tài liệu này:
- bai_giang_toan_roi_rac_bai_2_quy_nap_tran_vinh_duc.pdf