Tài liệu Một số bài toán trên bàn cờ.

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ HƯƠNG MAI MỘT SỐ BÀI TOÁN TRÊN BÀN CỜ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ HƯƠNG MAI MỘT SỐ BÀI TOÁN TRÊN BÀN CỜ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 Người hướng dẫn khoa học: PGS.TS. TẠ DUY PHƯỢNG Thái Nguyên - 2015 i Mục lục Lời cảm ơn i Lời cam đoan i Lời nói đầu 1 1 Một số bài toán trên bàn cờ 1.1 Bài toán tám quân hậu . . . 1.1.1 Giới thiệu bài toán . 1.1.2 Bài toán m quân hậu 1.2 Bài toán quân mã đi tuần . . 1.3 2 . . . . . . . . . . . . 3 3 3 3 12 1.2.1 Tìm hiểu về bài toán quân mã đi tuần . . . . . . . . . . . 1.2.2 Phương pháp Warnsdorff tìm lộ trình Hamilton . . . . . . 1.2.3 Một số phương pháp tìm chu trình Hamilton trong bàn cờ . Đôminô và Pôlyminô . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Khái niệm pôlyminô . . . . . . . . . . . . . . . . . . . . 1.3.2 Một số bài toán về đôminô và triminô . . . . . . . . . . . 1.3.3 Một số bài toán khác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 13 15 25 25 25 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đa thức xe 33 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2 Đa thức xe cho bàn cờ hai chiều . . . . . . . . . . . . . . . . . . . . 37 Kết luận 46 Tài liệu tham khảo 47 i Lời cảm ơn Luận văn được hoàn thành tại Khoa Sau đại học, Trường Đại học Khoa học-Đại học Thái Nguyên, dưới sự hướng dẫn của PGS. TS. Tạ Duy Phượng. Nhân dịp này, tôi xin gửi lời cảm ơn tới PGS.TS. Tạ Duy Phượng, người Thầy đã hướng dẫn tôi trong suốt quá trình tìm hiểu, nghiên cứu tài liệu và thực hiện luận văn. Tôi xin bày tỏ lòng biết ơn đến Khoa Toán-Tin, Trường Đại học Khoa học-Đại học Thái Nguyên đã trang bị cho tôi những kiến thức toán trong chương trình cao học. Xin được cám ơn gia đình, bạn bè đã động viên, giúp đỡ và tạo điều kiện cho tôi hoàn thành khoá học cao học và viết luận văn. i Lời cam đoan Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đa được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. 1 Lời nói đầu Cờ vua là một trò chơi gắn kết cuộc sống và hoạt động của con người từ thời cổ đại. Tuy nhiên các bài toán toán học trên bàn cờ có lẽ mới chỉ được hình thành và nghiên cứu khoảng vài trăm năm trở lại đây. Với sự phát triển của công nghệ thông tin, các bài toán trò chơi lại nhận được sự quan tâm mới, liên quan đến thuật toán, lập trình, lời giải tối ưu,... Nhiều bài toán trò chơi, trong đó có các bài toán trò chơi trên bàn cờ (đôminô, bài toán tám quân hậu, bài toán quân mã đi tuần,. . . ) đã khơi nguồn sáng tạo cho nhiều nhà khoa học để từ đó nhiều ngành toán học mới (xác suất, lý thuyết đồ thị, lý thuyết trò chơi, giải trí toán học,. . . ) ra đời và phát triển. Mục đích của luận văn là tìm hiểu một số bài toán trò chơi cổ điển trên bàn cờ, như bài toán tám quân hậu, bài toán quân mã đi tuần, bài toán đôminô, và tìm hiểu lý thuyết đa thức xe và áp dụng của lý thuyết này vào một số bài toán tổ hợp. Trong khuôn khổ của một luận văn chuyên ngành toán sơ cấp, chúng tôi giới hạn trình bày nội dung lý thuyết tương đối gần và có thể áp dụng được trong giảng dạy toán ở phổ thông. Các bài toán trên bàn cờ liên quan mật thiết đến nhiều dạng toán khác (toán tổ hợp, giải trí toán học, lý thuyết đồ thị,. . . ). Vì vậy việc nghiên cứu các bài toán trên bàn cờ cũng góp phần nghiên cứu các bài toán toán học khác. Luận văn cố gắng trình bày một cách có hệ thống những nội dung cơ bản của một số bài toán trên bàn cờ cũng như tìm hiểu về lịch sử và các phương pháp cơ bản giải các bài toán đó. Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận văn gồm hai chương. Chương 1: Một số bài toán trên bàn cờ Chương này trình bày một số bài toán cổ điển trên bàn cờ: Bài toán tám quân hậu, bài 2 toán con mã đi tuần, đôminô và pôlyminô. Chương 2: Đa thức xe Chương 2 trình bày một số vấn đề về đa thức xe (rook polynomial) và áp dụng vào một số bài toán tổ hợp. Thái Nguyên, ngày 18 tháng 04 năm 2015 Bùi Thị Hương Mai 3 Chương 1 Một số bài toán trên bàn cờ 1.1 Bài toán tám quân hậu Mục này trình bày Bài toán tám quân hậu và bài toán m quân hậu, dựa theo Tài liệu tham khảo [4]. 1.1.1 Giới thiệu bài toán Năm 1848, Max Bezzel đã đặt bài toán tám quân hậu như sau: Biết rằng quân hậu trên bàn cờ có thể ăn quân khác cùng nằm với nó trên các đường thẳng đứng, đường ngang hoặc đường chéo. Đặt 8 quân hậu trên bàn cờ 8 × 8 sao cho không có hai quân hậu nào ăn nhau, nghĩa là phải đặt tám quân hậu trên bàn cờ sao cho không có hai quân hậu nằm trên cùng một hàng, một cột, hoặc một đường chéo. Lời giải đầu tiên của bài toán tám quân hậu đã được Franz Nauck công bố vào năm 1850. Bài toán tám quân hậu cũng được Franz Nauck tổng quát hóa thành bài toán m quân hậu trên một bàn cờ m × m. Bài toán này có lời giải với tất cả các số tự nhiên m khác 2 và 3. Kể từ đó nhiều nhà toán học, cả "Ông hoàng toán học" Card Friedrich Gauss, đã nghiên cứu bài toán tám quân hậu và bài toán tổng quát m quân hậu. 1.1.2 Bài toán m quân hậu Bài toán m quân hậu, tổng quát hóa của bài toán tám quân hậu, được phát biểu như sau: Có thể đặt m quân hậu vào bàn cờ m × m ô để không có quân hậu nào có thể ăn 4 được nhau không? Bài toán này là một bài toán thú vị vì nó dẫn đến bài toán tìm tập ổn định trong lớn nhất S của một đồ thị đối xứng G = (X, Γ) . Các đỉnh của đồ thị tương đương với m2 phần tử của ma trận vuông m × m. (Xem [4]). Coi một bàn cờ như một ma trận m × m gồm các phần tử vuông (các ô vuông), chúng ta có thể đồng nhất một phần tử của ma trận (một ô vuông) như là một cặp sắp thứ tự (i, j), trong đó i và j tương ứng là vị trí hàng và cột (là số hàng và số cột). Đường chéo trội (major diagonal) của ma trận là tập gồm các phần tử (i, j) để m − j + i = CON ST AN T , CON ST AN T (hằng số) là số của đường chéo. Đường chéo thứ m được gọi là đường chéo chính. Rõ ràng, các điểm trên đường chéo chính có tính chất i = j. Đường chéo phụ (minor diagonal) của ma trận là tập các phần tử (i, j) để i + j − 1 = CON ST AN T, ở đó CON ST AN T là số của đường chéo. Thí dụ, trong hệ tọa độ thông thường, tức là gốc tọa độ nằm ở ô bên trái dưới cùng, thì đường chéo chính chính là đường chéo nối ô bên trái dưới cùng với ô bên phải trên cùng, các đường chéo trội song song với đường chéo chính, còn các đường chéo phụ vuông góc với đường chéo chính. Như vậy, bài toán m quân hậu có thể được phát biểu như sau: Đặt m quân hậu vào một ma trận vuông m × m để a) số hàng là duy nhất, b) số cột là duy nhất, c) số đường chéo trội là duy nhất, d) số đường chéo phụ là duy nhất. Dưới đây trình bày các Thiết kế (Construction) và các Định lý giải bài toán m quân hậu với m ≥ 4. Thiết kế A. Tạo ma trận m × m với các phần tử vuông m = 2n, trong đó n = 2, 3, 4, 5, ... 5 i) Đặt các quân hậu (ik , jk ), vào các ô ik = k và jk = 2k,, k = 1, 2, 3, ..., n. ii) Đặt các quân hậu (il , jl ), vào các ô il = 2n + 1 − l và jl = 2n + 1 − 2l, l = 1, 2, 3, ..., n. Thiết kế B. Tạo ma trận m × m của các phần tử vuông (các ô vuông) với m = 2n, trong đó n = 2, 3, 4, 5, ... i) Đặt quân hậu (ik , jk ), trong đó ik = k và jk = 1 + {[2(k − 1) + n − 1] modulom} , với k = 1, 2, 3, ..., n. ii) Đặt quân hậu (il , jl ), trong đó il = 2n+1−l và jl = 2n− {[2(l − 1) + n − 1] modulom} , với l = 1, 2, 3, ..., n. Thiết kế C. Thêm hàng thứ (m + 1) và cột thứ (m + 1) vào ma trận vuông m × m. Đặt một quân hậu vào phần tử (m + 1, m + 1). Định lý 1.1.1. Nếu áp dụng Thiết kế A vào ma trận m × m, m = 2n, trong đó n là một số nguyên dương, n 6= 3λ + 1, λ = 0, 1, 2, ... thì nhận được một lời giải bài toán m quân hậu. Chứng minh: Phần i) của Thiết kế A đặt các quân hậu vào các phần tử (k, 2k), trong khi đó phần ii) đặt các quân hậu vào các phần tử (2n + 1 − l, 2n + 1 − 2l), 1 ≤ (k, l) ≤ n. Rõ ràng, phần i) đặt mỗi quân hậu vào các phần tử của n hàng đầu tiên với cột được đánh số chẵn. Phần ii) đặt mỗi quân hậu vào các phần tử n hàng cuối với cột lẻ. Bởi vậy, mỗi hàng và cột có một và chỉ một quân hậu. Những đường chéo trội trong phần i) được đánh số 2n − 2k + k = 2n − k, 1 ≤ k ≤ n. Rõ ràng, chúng là duy nhất. Những đường chéo trội trong phần ii) được đánh số 2n − (2n + 1 − 2l) + 2n + 1 − l = 2n + l, 1 ≤ l ≤ n. Chúng cũng là duy nhất. 6 Giả sử một quân hậu ở phần i) có cùng đường chéo trội với quân hậu ở phần ii). Khi đó 2n − k = 2n + l hay −k = l. Vô lí. Vì vậy không xảy ra trường hợp hai quân hậu nằm trên cùng một đường chéo trội. Những đường chéo phụ được sử dụng trong phần i) được đánh số bởi k + 2k − 1 = 3k − 1, với 1 ≤ k ≤ n. Rõ ràng, chúng là duy nhất. Những đường chéo phụ sử dụng trong phần ii) được đánh số bởi 2n + 1 − l + 2n + 1 − 2l − 1 = 4n − 3l + 1, với 1 ≤ l ≤ n. Rõ ràng, chúng cũng là duy nhất. Giả sử có một quân hậu ở phần i) có cùng đường chéo phụ với quân hậu ở phần ii) sao cho 3k − 1 = 4n − 3l + 1 và 4n = 3(k + l) − 2. Vì n là số nguyên nên k + l phải là số chẵn. Do đó ta có thể viết  k+l 2n = 3 2  − 1. Suy ra (k + l)/2 phải là số lẻ, thí dụ, (k + l)/2 = 2α + 1, α = 0, 1, 2, ... và do đó ta có 2n = 3(2α + 1) − 1 = 6α + 2 hay n = 3α + 1, α = 0, 1, 2, ... Đây là những giá trị bị loại trong giả thiết của Định lý. Do đó, với giả thiết n 6= 3α + 1, α = 0, 1, 2, ... thì không có hai quân hậu có cùng đường chéo phụ. Định lý được chứng minh. Định lý 1.1.2. Nếu áp dụng Thiết kế B vào ma trận m × m, m = 2n, trong đó n là số nguyên lớn hơn 1 và n 6= 3λ, λ = 1, 2, 3, ... thì ta nhận được một lời giải cho bài toán m quân hậu. Chứng minh: Phần i) của Thiết kế B đặt các quân hậu vào các phần tử (vào các ô vuông) (1, n), (2, n+ 2), (3, n + 4), ..., (r, s), trong đó  n+2 n chẵn  2 ,  r=   n+1 , n lẻ 2       và s=   2n, n  2n − 1, n và vào các phần tử (r0 , s0 ), (r0 + 1, s0 + 2), ..., (n, n − 2), trong đó    2, n chẵn  r0 = r + 1 . và s0 =  1, n  lẻ  chẵn  lẻ  , 7 Phần ii) của Thiết kế B đặt các quân hậu vào các phần tử (2n, n + 1), (2n − 1, n − 1), (2n − 2, n − 3), ..., (p, q), trong đó   3n chẵn   2, n    p=    3n + 1  , n lẻ 2 và q=   1, n  2, n  chẵn  ,  lẻ và vào các phần tử (p0 , q 0 ), (p0 − 1, q 0 − 2), (p0 − 2, q 0 − 4), ..., (n + 1, n + 3), trong đó p0 = p − 1 và q0 =   2n − 1, n  2n, n chẵn lẻ   .  Rõ ràng, phần i) đặt mỗi quân hậu vào mỗi phần tử của n hàng đầu tiên, với cột được đánh số chẵn (nếu n là chẵn)hoặc với cột được đánh số lẻ (nếu n là lẻ). Phần ii) đặt mỗi quân hậu vào mỗi phần tử của n hàng còn lại với cột được đánh số lẻ (nếu n là chẵn) hoặc với cột được đánh số chẵn (nếu n là lẻ). Do đó, mỗi hàng và cột có một và chỉ một quân hậu. Đường chéo trội được sử dụng trong phần i) được đánh số bởi 2n−[2(k − 1) + n]+ k = n − k + 2, 1 ≤ k ≤ r, và 2n − [2(k 0 − 1) − n] + k 0 = 3n − k 0 + 2, r0 ≤ k 0 ≤ n. Rõ ràng, vì số lớn nhất của tập đầu tiên là n − 1 + 2 = n + 1 và số nhỏ nhất trong tập thứ hai là 3n − n + 2 = 2(n + 1), nên những số này là duy nhất. Đường chéo trội trong phần ii) được đánh số bởi 2n − {2n + 1 − [2(l − 1) + n]} + 2n + 1 − l = 3n + l − 2, 1 ≤ l ≤ 2n + 1 − p và 2n − {2n + 1 − [2(l0 − 1) − n]} + 2n + 1 − l0 = n + l0 − 2, 2n + 1 − p0 ≤ l0 ≤ n. Rõ ràng, vì số nhỏ nhất trong tập đầu tiên là 3n + 1 − 2 = 3n − 1 và số lớn nhất trong tập thứ hai là n + n − 2 = 2(n − 1), nên chúng là duy nhất. Giả sử rằng một quân hậu ở phần i) có cùng đường chéo trội với một quân hậu ở 8 phần ii). Khi ấy ta có (1) n − k + 2 = 3n + l − 2, (3) 3n − k 0 + 2 = 3n + l − 2, (2) n − k + 2 = n + l0 − 2, (4) 3n − k 0 + 2 = n + l0 − 2. Phương trình (1) suy ra k + l = 4 − 2n, nhưng vì số nhỏ nhất k + l chỉ có thể là 2, nên điều này không thể xảy ra vì n lớn hơn 1. Phương trình (2) suy ra k + l0 = 4, và số nhỏ nhất k + l0 sẽ là   n+6 n chẵn   2 ,        n+5  , n lẻ. 2 Phương trình (3) suy ra k 0 + l = 4, và số nhỏ nhất k 0 + l sẽ là   n+6 n chẵn   2 ,         n+5 , n lẻ. 2 Như vậy, phương trình (2) và (3) chỉ có thể thỏa mãn khi n = 2 hoặc n = 3. Giá trị n = 3 bị loại theo giả thiết của Đinh lý. Với n = 2, ta có r = 2 và 2n + 1 − p = n. Vì vậy r0 = r + 1 > n và 2n + 1 − p0 = 2n + 2 − p > n. Do đó cả k 0 và l0 đều không tồn tại. Phương trình (4) suy ra k 0 + l0 = 2n + 4, nhưng số lớn nhất k 0 + l0 không vượt quá 2n. Chứng tỏ không xảy ra trường hợp hai quân hậu có cùng đường chéo trội. Đường chéo phụ được sử dụng trong phần i) được đánh số bởi k+2(k−1)+n−1 = n + 3k − 3 với 1 ≤ k ≤ r, và k 0 + 2(k 0 − 1) − n − 1 = −n + 3k 0 − 3 với r0 ≤ k 0 ≤ n. Đường chéo phụ trong phần ii) được đánh số bởi 2n+1−l+2n+1−2(l−1)−n−1 = 3n−3l+3) với 1 ≤ l ≤ 2n+1−p, và 2n+1−l0 +2n+1−2(l0 −1)+n−1 = 5n−3l0 +3 với 2n + 1 − p0 ≤ l0 ≤ n. Giả sử hai quân hậu cùng nằm trên đường chéo phụ. Ta có (5) n + 3k − 3 = −n + 3k 0 − 3, (8) −n + 3k 0 − 3 = 3n − 3l + 3, (6) n + 3k − 3 = 3n − 3l + 3, (9) −n + 3k 0 − 3 = 5n − 3l0 + 3, n + 3k − 3 = 5n − 3l0 + 3, (10) 3n − 3l + 3 = 5n − 3l0 + 3. hoặc (7) 9 Phương trình (5) suy ra 2n = 3(k 0 − k), nên k 0 − k phải là số chẵn, tức là k 0 − k = 2α, α = 1, 2, 3, .... Khi đó 2n = 3(2α), n = 3α, là những giá trị bị loại. Tương tự, phương trình (10) trở thành 2n = 3(l0 − l), l0 − l = 2α, n = 3α. Phương trình (6) suy ra 2n = 3(k + l − 2), nên k + l − 2 phải là chẵn, tức là k + l − 2 = 2α, α = 1, 2, 3, ... Khi đó 2n = 3(2α), n = 3α, là những giá trị bị loại theo giả thiết của Định lý. Phương trình (7) suy ra 4n = 3(k + l0 − 2), nên k + l0 − 2 phải là số chẵn, nên k + l0 − 2 = 4α, α = 1, 2, 3, ... Khi đó 4n = 3(4α), n = 3α, là những giá trị bị loại theo giả thiết của Định lý. Tương tự, phương trình (8) trở thành 4n = 3(k 0 + l − 2), k 0 + l − 2 = 4α, n = 3α. Cuối cùng, từ phương trình (9) suy ra 6n = 3(k 0 + l0 − 2), 2n = k 0 + l0 − 2. Nhưng giá trị lớn nhất k 0 + l0 − 2) là 2n − 2, nên hai quân hậu không thể nằm trên cùng một đường chéo phụ. Trước khi xét Thiết kế C, ta cần chứng minh hai Bổ đề sau. Bổ đề 1.1.3. Thiết kế A không đặt quân hậu nào vào đường chéo chính. Chứng minh: Đường chéo chính có i = j. Giả sử một quân hậu trong Thiết kế A nằm ở đường chéo chính. Khi ấy hoặc là (1) k = 2k với mọi 1 ≤ k ≤ n, hoặc là (2) 2n + 1 − l = 2n + 1 − 2l với mọi 1 ≤ l ≤ n. Phương trình (1) suy ra k = 0, mâu thuẫn với k ≥ 1. Tương tự, phương trình (2) suy ra l = 0, mâu thuẫn với l ≥ 1. Do đó quân hậu không nằm trên đương chéo chính khi áp dụng Thiết kế A. Bổ đề 1.1.4. Thiết kế B không đặt quân hậu nào vào đường chéo chính. Chứng minh: 10 Chứng minh tương tự như Bổ đề 1. Giả sử rằng có một quân hậu ở phần i) trong Thiết kế B ở đường chéo chính. Khi ấy (1) 2(k − 1) + n = k với mọi 1 ≤ k ≤ n, hoặc (2) 2(k 0 − 1) − n = k 0 với mọi r0 ≤ k 0 ≤ n. Từ phương trình (1) suy ra k = 2 − n. Nhưng n > 1 nên k ≤ 0, mâu thuẫn với k ≥ 1. Phương trình (2) suy ra k 0 = n + 2, mâu thuẫn với k 0 ≤ n. Do đó, không có quân hậu nào trong phần i) nằm ở đường chéo chính. Giả sử có một quân hậu trong phần ii) nằm ở đường chéo chính. Khi ấy (3) 2n + 1 − [2(l − 1) + n] = 2n + 1 − l với mọi 1 ≤ l ≤ 2n + 1 − p, hoặc (4) 2n + 1 − [2(l0 − 1) − n] = 2n + 1 − l0 với mọi 2n + 1 − p0 ≤ l0 ≤ n. Phương trình (3) suy ra l = 2 − n. Nhưng n > 1, suy ra l ≤ 0, mâu thuẫn với l ≥ 1. Phương trình (4) suy ra l0 = n + 2, mâu thuẫn với l0 ≤ n. Do đó, không có quân hậu nào trong phần ii) nằm ở đường chéo chính. Bổ đề được chứng minh. Định lý 1.1.5. Lời giải bài toán m quân hậu cho ma trận m + 1 × m + 1 sẽ nhận được khi thực hiện Thiết kế C cho ma trận m × m, sau khi đã thực hiện thiết kế A hoặc Thiết kế B cho ma trận ấy. Chứng minh: Thiết kế C tạo ra duy nhất một hàng thứ m + 1 mới và một cột thứ m + 1 mới và đặt quân hậu vào vị trí (m + 1, m + 1). Hơn nữa, nó tạo ra một đường chéo phụ mới chỉ chứa phần tử (m + 1, m + 1), do đó bảo toàn số đường chéo phụ. Đường chéo chính của ma trận m + 1 × m + 1 có thể là sự mở rộng của đường chéo chính của ma trận m × m. Nhưng các Bổ đề 1 và 2 cho thấy đường chéo này rỗng (không chứa quân hậu nào). Do đó, số các đường chéo trội cũng được bảo toàn. Định lý được chứng minh. Ba Thiết kế trên bỏ qua một số giá trị của m, nhưng Định lý sau cho lời giải bài toán m quân hậu sau khi áp dụng các Thiết kế A, B và C. 11 Định lý 1.1.6. Bài toán m quân hậu là giải được với mọi m ≥ 4 nhờ các Thiết kế A,B, hoặc C. Chứng minh: Thiết kế A có thể áp dụng với mọi số chẵn m, ngoại trừ các số dạng m = 2(3λ + 1), λ = 0, 1, 2, ..., hay (1) m = 6λA − 4 λA = 1, 2, 3, · · · . Thiết kế B có thể áp dụng cho các số m chẵn trừ các số dạng m = 2(3λB ) (2a) m = 6λB λB = 1, 2, 3, · · · , và (2b) m = 2 Trường hợp đặc biệt, phương trình (2b), bị loại do n = 1 bị loại trong Định lý 2. Cuối cùng, Thiết kế C thỏa mãn với m lẻ mà m − 1 có thể giải được bằng Thiết kế A hoặc Thiết kế B. Giả sử M 0 là tập các số nguyên m0 > 1 có tính chất là cấu trúc A, B, hoặc C không giải được ma trận m0 × m0 . Mọi số chẵn m0 ε của tập M 0 phải bị loại đồng thời theo cả A và B, suy ra (3) 6λA − 4 = m0 ε = 2, hoặc (4a) 6λA − 4 = m0 ε = 6λB (4b) λA − 2 = λB 3 với cặp số nguyên λA và λB nào đó. Phương trình (4) không thể thoả mãn vì λ0 s là số nguyên. Phương trình (3) thoả mãn chỉ khi λA = 1, do đó m0 ε = 2 chỉ là phần tử chẵn của M 0 . Với mọi phần tử lẻ của M 0 , thí dụ, m0o , bị loại từ Thiết kế C, thì phần tử chẵn m0o − 1 bị loại từ cả A và B. Nhưng ta thấy rằng chỉ có số chẵn bị loại từ A và B là 12 m0 ε = 2, do đó chỉ có số lẻ trong M 0 là m0o = 3. Như vậy, M 0 chỉ chứa hai số nguyên 2 và 3. Định lý được chứng minh. 1.2 Bài toán quân mã đi tuần Mục này trình bày Bài toán quân mã đi tuần, dựa theo tài liệu tham khảo [1]. 1.2.1 Tìm hiểu về bài toán quân mã đi tuần Trong bàn cờ vua quân mã có thể di chuyển từ ô này sang ô kia là hai ô thuộc một hình chữ nhật kích thước 2 × 3 hoặc 3 × 2 ở hai góc đối diện của hình chữ nhật ấy. Trên Hình 1.1 quân mã có tất cả 8 bước đi hợp lệ. Ở những vị trí khác số bước đi của Hình 1.1: quân mã có thể ít hơn. Vấn đề được đặt ra như sau: Tìm đường đi của quân mã qua tất cả các ô của bàn cờ vua, mỗi ô chỉ một lần. Trường hợp 1: Nếu quân mã trở về ô xuất phát thì ta có một đường đi khép kín. Trường hợp 2: Nếu quân mã không trở về ô xuất phát thì ta có một đường đi mở. Ta sẽ gọi đường đi khép kín của quân mã là một chu trình Hamilton, còn một đường đi mở của quân mã là một lộ trình Hamilton của quân mã trong bàn cờ. Như vậy, bài toán quân mã đi tuần đòi hỏi: Tìm một lộ trình Hamilton (hay một chu trình Hamilton) của quân mã trong bàn cờ. 13 Đây là một bài toán không dễ. Một lời giải đầu tiên (một chu trình Hamilton) được Euler tìm ra năm 1759 và Vandermonde tìm ra năm 1771. Đến nay, bằng cách sử dụng máy tính, người ta đã tìm ra nhiều lời giải khác. Warnsdorff đã nghĩ ra một phương pháp khá độc đáo giúp tìm ra một đường đi mở của quân mã (một lộ trình Hamilton). A. J. Sohwenk đã mở rộng bài toán cho mọi bàn cờ m × n ô. Ông đã chứng minh rằng: Một bàn cờ m × n ô (m ≤ n) không có chu trình Hamilton khi và chỉ khi: +) m và n đều lẻ; +) m = 1, 2, 4; +) m = 3 hoặc m = 4, 6, 8. 1.2.2 Phương pháp Warnsdorff tìm lộ trình Hamilton Phương pháp Warnsdorff tìm lộ trình Hamilton trong bàn cờ như sau. Xuất phát từ một ô bất kỳ và luôn di chuyển đến ô dính với số lượng ít nhất những ô chưa được dùng đến. Hai ô dính nhau là hai ô có chung ít nhất một đỉnh. Trên Hình 1.2 ô số 1 dính với ba ô (số 2, 4, 5) ô số 2 dính với 5 ô (số 1, 4, 5, 6, 3) ô số 5 dính với 8 ô (số 1, 2, 3, 4, 6, 7, 8, 9). Phương pháp Warnsdorff áp dụng cho bàn cờ 5 × 5 (25 ô) như sau: Xuất phát từ ô trung tâm của bàn cờ (Hình 1.2). Từ ô 1 có 8 cách đi như trên Hình 1.1. Chọn một ô, thí dụ ô số 2. Từ ô số 2 chỉ còn hai cách đi, ta phải đi đến ô 3 (chỉ dính với 5 ô chưa dùng, đến ô khác không nằm trên biên thì dính với 7 ô chưa dùng). Từ ô 3 phải đi đến ô 4, từ ô 4 đến ô 5, 6,. . . , 15. Từ ô 15 có hai cách đi như nhau (đến một ô dính với 2 ô chưa dùng), ta chọn ô 16 từ đây ta phải đi tiếp đến ô 17 rồi 18. Từ ô 18 có hai cách đi như nhau, ta chọn ô 19. Từ đây chỉ có cách đi tiếp đến các ô 20, 21, 22, 23, 24. . . và kết thúc ở ô 25. Ta có được một lộ trình Hamilton trong bàn cờ 5 × 5. Trên Hình 1.4 ta có 3 bước đi được chọn (trong các bước đi thỏa mãn yêu cầu của phương pháp Warnsdorff) được đánh dấu bằng ba mũi tên. Lần ngược từ ô 25 trở lên đến ô 18 nếu từ ô 18 ta chọn ô 25, thì sau đó ta sẽ đi tiếp đến các ô 24, 23, 22, 21, 20 và kết thúc ở ô 19, ta vẫn được một lời giải. 14 Hình 1.2: Nếu từ ô 15 ta đến ô 16 như Hình 1.3, từ đó đến các ô 19, 20, 21,... và kết thúc ở ô 23, những còn hai ô 24 và 25 chưa đi tới. Chú ý rằng trong trường hợp này có thể đi ngược lại từ 1 đến 24 rồi 25. Do đó ta có một lộ trình Hamilton xuất phát từ ô 25 và kết thúc ở ô 23 như trên Hình 1.3. Hình 1.3: 15 Hình 1.4: Đối với bàn cờ lớn hơn, thí dụ, bàn cờ vua 8 × 8, việc áp dụng phương pháp Warnsdorff khó hơn. 1.2.3 Một số phương pháp tìm chu trình Hamilton trong bàn cờ Cạnh biên và chu trình biên của bàn cờ Bàn cờ m × n ô (m ≤ n) với đường đi của quân mã có thể coi như một graph (đồ thị) có các đỉnh là tâm các ô của bàn cờ và các cạnh là các bước đi của quân mã. Sau đây, ta sẽ coi các đỉnh của graph là đỉnh của các ô vuông trong một hình chữ nhật (m − 1) × (n − 1) ô, các cạnh của graph (các bước đi của quân mã) là các đường chéo của hình chữ nhật 1 × 2 hoặc 2 × 1 ô, nghĩa là vị trí và di chuyển quân của quân mã như trong bàn cờ tướng.