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

Phương pháp chứng minh Trần Vĩnh Đức HUST Ngày 6 tháng 9 năm 2018 1 / 37 Bài tập ▶ GS Mc Brain và vợ là bà April tới một bữa tiệc ở đó có 4 đôi vợ chồng khác. ▶ Có một vài cặp bắt tay nhau nhưng không ai bắt tay với vợ hoặc chồng mình. ▶ GS hỏi mọi người khác xem họ bắt tay bao nhiêu người và ông ấy nhận được 9 con số khác nhau. ▶ Hỏi có bao nhiêu người đã bắt tay April? 2 / 37 Tài liệu tham khảo ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch Tiếng Việt) 3 / 37 Định nghĩa Chứng minh toán học của một mệnh đề là một dãy suy luận logic dẫn đến mệnh đề này từ một tập tiên đề. 4 / 37 Nội dung Mệnh đề, tiên đề, và suy luận logic Phương pháp chứng minh Nguyên lý sắp thứ tự tốt Định nghĩa Mệnh đề là một khẳng định hoặc đúng hoặc sai. ▶ Mệnh đề 2 + 3 = 5 3 ▶ Mệnh đề 1 + 1 = 3 7 6 / 37 Khẳng định không phải mệnh đề ▶ “Đưa tôi cái bánh!” ▶ “Bây giờ là 5 giờ” 7 / 37 Mệnh đề Với mọi số nguyên dương n, giá trị p(n) ::= n2 + n+ 41 là số nguyên tố. ▶ p(0) = 41 ✓ ▶ p(1) = 43 ✓ ▶ p(2) = 47 ✓ ▶ p(3) = 53 ✓ ▶ · · · ▶ p(39) = 1601 ✓ nhưng p(40) = 402 + 40 + 41 = 41× 41 7 8 / 37 Mệnh đề (Giả thuyết Euler, 1769) Phương trình a4 + b4 + c4 = d4 không có nghiệm khi a, b, c, d là số nguyên dương. Năm 1988, Noam Eikies đã chứng minh là sai với phản ví dụ a = 95800, b = 217519, c = 414560, d = 422481 9 / 37 Mệnh đề Phương trình 313(x3 + y3) = z3 không có nghiệm nguyên dương. Mệnh đề này cũng sai nhưng phản ví dụ nhỏ nhất có nhiều hơn 1000 chữ số. 10 / 37 Mệnh đề (Định lý bốn màu) Mọi bản đồ đều có thể tô được chỉ bằng bốn màu sao cho hai vùng kề nhau có màu khác nhau. Hình: Bản đồ tô 5 màu 11 / 37 Mệnh đề (Định lý bốn màu) Mọi bản đồ đều có thể tô được chỉ bằng bốn màu sao cho hai vùng kề nhau có màu khác nhau. Appel & Hakel đã phân loại các bản đồ và dùng máy tính để kiểm tra xem chúng có tô được bằng 4 màu. Họ đã hoàn tất chứng minh năm 1976. Tuy nhiên ▶ Chứng minh quá dài để có thể kiểm tra mà không dùng máy tính. ▶ Không ai đảm bảo rằng chương trình máy tính này chạy đúng. ▶ Không ai đủ nhiệt tình để kiểm tra hết hàng nghìn trường hợp đã được chứng minh. 12 / 37 Mệnh đề (Định lý cuối cùng của Fermat) Phương trình xn + yn = zn không có nghiệm nguyên với n ≥ 3. ▶ Bài toán được viết trong một quyển sách Fermat đọc năm 1630. ▶ Andrew Wiles chứng minh là đúng năm 1994. 13 / 37 Mệnh đề (Giả thuyết Goldbach) Mọi số nguyên chẵn lớn hơn 2 đều là tổng của hai số nguyên tố. ▶ Được giả thuyết năm 1742 ▶ Đã được khẳng định là đúng với mọi số không lớn hơn 1016. ▶ 3 hay 7 ? 14 / 37 Định nghĩa Vị từ là một mệnh đề mà giá trị chân lý phụ thuộc vào một hoặc nhiều biến. p(n) :: = “n là số bình phương hoàn hảo” p(4) = “4 là số bình phương hoàn hảo” p(4) = 3 p(5) = 7 15 / 37 Phương pháp tiên đề ▶ Thủ tục chuẩn để thiết lập các giá trị chân lý trong toán học đã được phát triển khoảng từ 300 BC bởi Euclid. ▶ Bắt đầu từ 5 “giả sử” để xây dựng hình học Euclid. Ví dụ: Qua một điểm nằm ngoài một đường thẳng ta vẽ được một và chỉ một đường thẳng song song với đường thẳng đã cho. ▶ Các mệnh đề như thế này được thừa nhận là đúng được gọi là tiên đề. ▶ Bắt đầu từ các tiên đề này, Euclid thiết lập giá trị chân lý của các mệnh đề khác bằng cách đưa ra “chứng minh”. ▶ Chứng minh là một dãy các lập luận logic từ tập tiên đề dẫn đến mệnh đề cần chứng minh. 16 / 37 Một số thuật ngữ cho mệnh đề ▶ Mệnh đề đúng và quan trọng gọi là định lý. ▶ Bổ đề là mệnh đề chuẩn bị có ích để chứng minh các mệnh đề khác. ▶ Hệ quả là một mệnh đề mà chứng minh nó chỉ cần vài bước từ một định lý. 17 / 37 Hệ tiên đề của chúng ta ▶ Về cơ bản, toán học hiện đại dựa trên hệ tiên đề ZFC (Zermelo-Fraekel with Choice) cùng với một vài quy tắc suy luận logic. ▶ Tuy nhiên, chúng quá tối giản. Ví dụ, một chứng minh hình thức trong ZFC cho 2 + 2 = 4 cần nhiều hơn 20, 000 bước lập luận! ▶ Trong môn học này, ta thừa nhận mọi sự kiện trong toán “phổ thông” như tiên đề. 18 / 37 Suy luận logic ▶ Luật Modus Ponens: P, P⇒ Q Q (Một chứng minh của P và một chứng minh P suy ra Q là một chứng minh của Q) ▶ Luật P⇒ Q, Q⇒ R P⇒ R ▶ Luật ¬P⇒ ¬Q Q⇒ P 19 / 37 Không phải luật ¬P⇒ ¬Q P⇒ Q 7 Ví dụ ▶ Nếu 4 là số nguyên tố, thì “tôi không biết bay”. 3 ▶ Nếu 4 không phải số nguyên tố, thì “tôi biết bay”. 7. 20 / 37 Nội dung Mệnh đề, tiên đề, và suy luận logic Phương pháp chứng minh Nguyên lý sắp thứ tự tốt Chứng minh mệnh đề “Nếu ... thì” Để chứng minh mệnh đề P⇒ Q: 1. Viết, “Giả sử P”. 2. Chỉ ra bằng lập luận logic rằng Q đúng. 22 / 37 Định lý Nếu 0 ≤ x ≤ 2 thì −x3 + 4x+ 1 > 0. Chứng minh. Giả sử 0 ≤ x ≤ 2. Vậy các số x, 2 + x, 2− x đều lớn hơn hoặc bằng 0. Vậy x(2− x)(2 + x) ≥ 0 Thêm 1 vào tích trên ta được x(2− x)(2 + x) + 1 > 0 Khai triển tích ta được −x3 + 4x+ 1 > 0. 23 / 37 Chứng minh bằng phản đảo ▶ Phản đảo của mệnh đề P⇒ Q là mệnh đề ¬Q⇒ ¬P. ▶ Ta chứng minh như sau: 1. Viết “Ta chứng minh mệnh đề phản đảo:” và đưa ra mệnh đề phản đảo. 2. Làm như phương pháp chứng minh “Nếu ... thì”. 24 / 37 Định lý Nếu r là số vô tỷ, vậy √r cũng là số vô tỷ. Chứng minh. ▶ Ta chứng minh mệnh đề phản đảo: Nếu √r là số hữu tỉ, vậy r là số hữu tỉ. ▶ Giả sử rằng √r là số hữu tỉ. Có nghĩa rằng có hai số nguyên p, q sao cho √r = p/q. ▶ Bình phương hai vế ta được p2 q2 = r ▶ Vì p2, q2 đều là số nguyên nên r là số hữu tỉ. 25 / 37 Chứng minh mệnh đề “Nếu và chỉ nếu” Có hai cách chứng minh: 1. Chứng minh P⇔ Q tương đương với hai chứng minh { P⇒ Q Q⇒ P 2. Xây dựng dãy “nếu và chỉ nếu”. 26 / 37 Chứng minh bằng cách chia trường hợp Định lý Mọi nhóm gồm 6 người đều có 3 người hoặc đôi một quen nhau, hoặc đôi một lạ nhau. Chứng minh. Xét x là một trong 6 người. Có hai trường hợp tương tự nhau: 1. Trong 5 người khác x, có ít nhất 3 người đều quen x. 2. Trong 5 người khác x, có ít nhất 3 người đều lạ x. Tại sao? 27 / 37 Chứng minh bằng cách chia trường hợp Định lý Mọi nhóm gồm 6 người đều có 3 người hoặc đôi một quen nhau, hoặc đôi một lạ nhau. Chứng minh trường hợp 1. Trong 5 người khác x, có ít nhất 3 người đều quen x. Có hai trường hợp con: 1. Không có cặp nào trong số 3 người này quen nhau. 3 2. Có một cặp trong 3 người này quen nhau. Vậy cặp này cùng với x tạo thành 3 người quen nhau từng đôi một. 3 28 / 37 Chứng minh phản chứng Để chứng minh mệnh đề P bằng phản chứng: 1. Viết “Ta chứng minh dùng phản chứng”. 2. Viết “Giả sử P sai.” 3. Dẫn ra một sự kiện đã biết là sai (một phản chứng). 4. Viết “Điều này mâu thuẫn. Vậy P phải đúng.” 29 / 37 Định lý√ 2 là số vô tỉ. Chứng minh. ▶ Ta chứng minh dùng phản chứng. ▶ Giả sử √ 2 là số hữu tỉ. ▶ Vậy ta có thể viết √ 2 = p/q ở dạng phân số tối giản. ▶ Ta có √ 2 = p q ⇒ 2 = p2 q2 ⇒ 2q 2 = p2 ▶ Vậy p chia hết cho 2. Tại sao? Nên p2 chia hết cho 4. ▶ Vậy q2 chia hết cho 2. Nên q chia hết cho 2. ▶ Vậy p/q không tối giản. 7 30 / 37 Nội dung Mệnh đề, tiên đề, và suy luận logic Phương pháp chứng minh Nguyên lý sắp thứ tự tốt Nguyên lý sắp thứ tự tốt (STTT) Mọi tập số nguyên không âm khác rỗng đều có phần tử nhỏ nhất. ▶ Tập rỗng không có phần tử nhỏ nhất. ▶ Không đúng với tập số âm. Ví dụ tập {· · · ,−3,−2,−1} ▶ Không đúng với mọi tập số hữu tỉ. Ví dụ tập{ 1 1 , 1 2 , 1 3 , · · · } 32 / 37 Định lý Mọi số hữu tỉ m/n đều viết được dưới dạng x/y sao cho x, y không có ước chung nguyên tố. Chứng minh. ▶ Giả sử ngược lại có m,n không viết được như trên. ▶ Xét C là tập tử số của các phân số như vậy. Vậy C 6= ∅ vì m ∈ C. ▶ Theo nguyên lý STTT, có số nhỏ nhất m0 ∈ C. ▶ Theo định nghĩa của tập C, có số n0 để m0/n0 không viết được ở dạng trên. 33 / 37 Chứng minh (tiếp). ▶ Có nghĩa rằng m0,n0 có ước chung nguyên tố p > 0. Vậy m0/p n0/p = m0 n0 ▶ Vì m0/n0 không thể viết ở dạng trên. Vậy m0/pn0/p cũng không viết được ở dạng trên. ▶ Vậy ta có m0 p ∈ C và m0 p < m0 7 34 / 37 Chứng minh dùng STTT Để chứng minh P(n) đúng với mọi số nguyên không âm n, ta làm như sau ▶ Định nghĩa tập phản ví dụ của P : C ::= {n ∈ N | ¬P(n) đúng } ▶ Giả sử phản chứng rằng C 6= ∅. ▶ Bởi nguyên lý STTT có phần tử nhỏ nhất c ∈ C. ▶ Đưa ra phản chứng: thường bằng cách chỉ ra P(c) đúng hoặc chỉ ra một phần tử d ∈ C và d < c. ▶ Kết luận rằng C rỗng, có nghĩa rằng không có phản ví dụ. 35 / 37 Định lý Mọi số nguyên dương lớn hơn một đều phân tích được thành tích các số nguyên tố. Chứng minh bằng STTT. ▶ Giả sử tập phản ví dụ của định lý C 6= ∅. ▶ Có phần tử n nhỏ nhất thuộc C. Vậy n không nguyên tố. Có nghĩa rằng n = a · b với a, b > 1 ▶ Hơn nữa a, b phải phân tích được thành tích các số nguyên tố. Tại sao? a = p1 · · · pk và b = q1 · · · qm ▶ Vậy n = p1 · · · pk · q1 · · · qm. 7 36 / 37 Định lý Mọi số nguyên dương đều thú vị. Chứng minh. ▶ Xét S là tập các số nguyên dương không thú vị. ▶ Nếu S khác rỗng, S chứa phần tử nhỏ nhất n. ▶ Nhưng là phần tử nhỏ nhất của một tập phải là một tính chất thú vị. ▶ Vậy n không thuộc S. 7 37 / 37 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 24 26 25 : 21 22 23 687 9 243 5 (a) 24 26 25 : 21 22 23 687 9 243 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). 24 25 26 : 21 22 23 687 9 243 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 24 26 25 : 21 22 23 687 9 243 5 (a) 24 26 25 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). 24 25 26 : 21 22 23 687 9 243 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 awa