Đề thi THPT Quốc gia môn Toán năm 2015, De thi thu THPT Quoc Gia nam 2015

You are here: Home »

Like VNMATH on FACEBOOK để ủng hộ VNMATH.

Các bài toán thú vị liên quan đến cờ

VNMATH.COM 15 tháng 9, 2014 , 0

Cờ vua và cờ tướng là những trò chơi trí tuệ lâu đời, được ưa chuộng khắp thế giới. Đây là trò chơi dành cho hai người, dựa trên chiến thuật và chiến lược hợp lý cho từng bước đi. Đây còn là niềm cảm hứng để tạo ra những phát minh trong toán học của nhiều thế hệ.

Lịch sử cờ vua, cờ tướng

Có nhiều giả thuyết khác nhau về nguồn gốc của hai loại cờ này. Nhiều quốc gia cho rằng họ là nơi phát minh ra cờ vua trong dạng phôi thai nào đó. Phổ biến nhất thì người ta tin rằng cờ vua có nguồn gốc từ Ấn Độ, tại đó nó được gọi là chaturanga (saturanga) và có lẽ ra đời vào khoảng thế kỷ 6. Trò chơi này khi lan dần sang phía tây thì trở thành cờ vua như ngày nay (vào khoảng thế kỷ thứ VI) và khi lan dần sang phía đông thì thành cờ tướng (khoảng thế kỷ thứ VII)

Một thuyết khác cho rằng cờ vua sinh ra từ trò chơi tương tự của cờ Trung Quốc, hoặc ít nhất là từ tổ tiên của cờ tướng, là môn đã tồn tại ở Trung Quốc kể từ thế kỷ 2 TCN. Joseph Needham và David Li là hai trong số nhiều học giả theo thuyết này.

Cờ vua sau đó được phổ biến về phía tây tới châu Âu và về phía đông tới Nhật Bản, sinh ra các biến thể trên đường đi của nó. Từ Ấn Độ nó đã tới Ba Tư, ở đây các thuật ngữ của nó được phiên âm sang tiếng Ba Tư và tên gọi của nó đổi thành chatrang.

Chàng trai trẻ Ba Tư đang chơi cờ với hai người theo đuổi
Từ Ba Tư nó đi vào thế giới Hồi giáo, tại đây tên gọi của các quân cờ chủ yếu vẫn giữ các dạng Ba Tư trong thời kỳ Hồi giáo ban đầu của nó. Tên gọi của nó trở thành shatranj, được phiên theo tiếng Tây Ban Nha là ajedrez và trong tiếng Hy Lạp là zatrikion, nhưng trong phần lớn các nước châu Âu khác nó được thay thế bằng phiên bản Ba Tư của từ shāh = "vua".

Cờ vua cũng như cờ saturanga, mỗi quân cờ đều có hình khối rõ ràng để phân biệt, khác với cờ tướng chỉ có chữ trên những khối giống nhau. Điều sáng tạo ở bàn cờ tướng là sự xuất hiện quân pháo, là quân muộn nhất trên bàn cờ vì tới thế kỷ thứ VII, pháo mới được phát minh và đưa vào sử dụng trong chiến tranh. Cũng ở cờ tướng, hai quân cờ là vua và sĩ chỉ ở trong cấm cung, thể hiện nét văn hóa theo quan niệm của người phương Đông.

Về mặt toán học, ở mỗi bước đi, số lượng cách đi là rất lớn. Người chơi cần tính trước khả năng đối thủ sẽ đi bước tiếp theo như thế nào và lựa chọn cho mình thuật toán tối ưu để đi. Trò chơi được cho là khó vì ngay cả những người chơi giỏi nhất cũng khó tính toán được hết các khả năng.

Các câu chuyện toán học thú vị về cờ

a) Truyền thuyết Ấn Độ về Hạt thóc và bàn cờ
Nhà vua muốn thưởng cho nhà thông thái đã phát minh ra cờ saturanga và người này đã tâu xin được thưởng như sau: Từ 64 ô vuông, đặt vào ô thứ nhất 1 hạt thóc, ô thứ hai 2 hạt thóc, ô thứ ba 4 hạt thóc, ô thứ tư 8 hạt thóc. Cứ như thế, ô sau sẽ có số hạt thóc gấp đôi ô trước, đến ô thứ 64 thì số hạt thóc là 263 và tổng số hạt thóc trên bàn cờ là 264 - 1.

Ban đầu, nhà vua vui vẻ đồng ý nhưng quan phụ trách kho sau khi tính toán đã trình lên nhà vua rằng số thóc này gấp hàng triệu lần số thóc có trong kho của nhà vua. Theo tính toán, số hạt thóc là gần 18,5 tỷ tỷ hạt, nặng khoảng 641 tỷ tấn, trong khi ngày nay, toàn thế giới mới chỉ sản xuất được khoảng 2 tỷ tấn lương thực mỗi năm. Để giúp nhà vua giữ đúng lời hứa ban thưởng, một vị quan đã hiến kế rằng nhà thông thái phải đếm từng hạt thóc khi nhận thưởng vào các ô trong bàn cờ.

Theo tính toán, nếu mỗi giây đếm được 2 hạt thóc, mỗi ngày đếm trong 12 giờ thì cần tới 290 tỷ năm mới đếm hết được số hạt thóc. Từ truyền thuyết này, một bài toán tương tự đã được nhà toán học người Ả Rập là Ibn Kallikhan đặt ra vào năm 1256.

b) Quân mã và ma phương bậc 8
Cũng liên quan đến bàn cờ, Leonhard Euler (1707 - 1783), một nhà toán học người Thụy Sĩ đã nghĩ ra cách đi quân mã trên bàn cờ vua để tạo ra một ma phương cạnh 8. Đó là một hình vuông lớn mà mỗi cạnh được chia làm 8 phần bằng nhau. Mỗi hình vuông nhỏ được viết một trong các số từ 1 đến 64, mỗi số viết đúng một lần, sao cho tổng các số trên mỗi hàng, mỗi cột và hai đường chéo của hình vuông lớn đều bằng nhau. Cách làm của Euler là chọn một ô điền số 1, rồi thực hiện các bước đi của quân mã, mỗi bước điền các số tăng dần từ 2 đến 64.

c) Bàn cờ 3x3
Dựa trên luật chơi của cờ tướng và cờ vua, nhiều loại cờ khác cũng đã ra đời. Chẳng hạn, năm 1525, một người Italia tên là Guarini di Forli đã đặt ra một câu hỏi với kiểu bàn cờ vua 3 × 3 ô, trong đó đặt hai quân mã màu đen và hai quân mã màu trắng đặt ở bốn góc của bàn cờ sao cho hai quân cùng màu thì nằm trên một hàng.
Câu hỏi mà ông đặt ra là: Sau bao nhiêu nước đi thì kết thúc trò chơi, quân mã một bên sẽ bị bên kia ăn hết? Đây là một trò chơi trí tuệ khá thú vị và đến bây giờ vẫn có nhiều người chơi. Sau này, người ta đã tính toán được chính xác số bước đi tối thiểu là 16. Tương tự ý tưởng này, người ta cũng tạo ra nhiều ván cờ mà một số quân được bày sẵn để hai bên chơi tiếp, mà ta gọi là cờ thế. Đó có thể là một ván cờ hay đã từng được chơi và ghi chép lại. Người ta dừng ván cờ ở những nước chơi gần cuối và đặt ra cờ thế để người chơi sau này tính toán các khả năng chơi tiếp của hai bên. Cờ thế có trong cả cờ vua lẫn cờ tướng và là một hình thức giải trí trí tuệ mang lại say mê cho nhiều người, đòi hỏi người chơi cần tính toán hết các khả năng, giống như những bài toán tổ hợp.

d) Bài toán 8 quân hậu. 

Lời giải bài toán 8 quân hậu

Bài toán đặt ra là có bao nhiêu cách để đặt 8 quân hậu trên một bàn cờ vua sao cho 2 quân bất kỳ không thể “ăn” được nhau. Tổng quát hơn, năm 1850, Franz Nauck đã đưa ra bài toán với bàn cờ tương tự như cờ vua, thay 8 quân hậu bởi số n quân trên một bàn cờ là hình vuông có n × n ô. Bài toán tổng quát này được giải quyết năm 1874 bởi hai nhà toán học Gunther và Glaisher bằng cách sử dụng phương pháp định thức, một khái niệm toán học mới. Bài toán đặt ra là có bao nhiêu cách đi để từ một vị trí ban đầu của quân mã trên bàn cờ vua, di chuyển 64 bước để nó đi qua tất cả các ô trên bàn cờ và trở về vị trí ban đầu. Theo tính đối xứng, vị trí đặt quân mã ban đầu có thể là một trong 10 ô. Việc giải quyết bài toán này cùng với bài toán bảy cây cầu Konigsberg đã hình thành một lý thuyết mới trong toán học là lý thuyết đồ thị và cấu trúc liên kết. Tiếp tục phát triển trò chơi toán học theo hướng này, năm 1875, nhà toán học người Ireland là Hamilton (1805 - 1865) đã phát minh ra trò chơi icosian. Ông đưa ra trò chơi nối các đỉnh của một khối 12 mặt, mỗi đỉnh chỉ đi qua một lần, các đường nối không cắt nhau. Quá trình giải quyết bài toán này dẫn đến một lý thuyết mới được gọi là chu trình Hamilton và các khái niệm mới trong toán học như véc tơ trong hình học và luật kết hợp trong tổ hợp.

e) Bài toán mã đi tuần
Mã đi tuần (hay hành trình của quân mã) là bài toán về việc di chuyển một quân mã trên bàn cờ vua (8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần. Có rất nhiều lời giải cho bài toán này, chính xác là 26.534.728.821.064 lời giải trong đó quân mã có thể kết thúc tại chính ô mà nó khởi đầu.

Một hành trình như vậy được gọi là hành trình đóng. Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ (kể cả ô xuất phát), thì từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một nước đi. Những hành trình như vậy được gọi là hành trình mở.

Lời giải bài toán trên bàn cờ 5x5

Nhiều biến thể của chủ đề này được các nhà toán học nghiên cứu, trong đó có nhà toán học Euler. Các biến đổi có thể theo các hướng: thay đổi kích thước bàn cờ, biến thành trò chơi hai người theo tư tưởng này, giảm nhẹ các yêu cầu trên đường đi của quân mã.
Bài toán mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm đường đi Hamilton trong l‎ý thuyết đồ thị, là một bài toán NP-đầy đủ. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm chu trình hamiltonian.

Hành trình của quân mã trên nửa bàn cờ đã được giới thiệu dưới dạng thơ trong một tác phẩm tiếng Phạn.

Giải thuật đầu tiên đầy đủ cho bài toán về hành trình của quân mã là Giải thuật Warnsdorff, công bố lần đầu năm 1823 bởi H. C. Warnsdorff.

f) Trò chơi di chuyển các chiếc nhẫn trên các vòng tròn được phát minh bởi nhà toán học người Italia là Cardano (1501 - 1576). Tuy vậy, bài toán tương tự được cho là ra đời từ trước đó mấy nghìn năm nhưng chưa có lời giải. Tương truyền, bài toán này xuất phát từ một ngôi đền cổ của người Hindu. Ban đầu có ba cái cọc, trong đó có một cọc chứa 64 đĩa có kích thước khác nhau, đĩa bé nhất ở trên cùng, hai cọc kia không có gì. Mỗi lần, ta di chuyển một đĩa từ cọc này sang cọc khác sao cho đĩa được lấy là trên cùng của cọc đó và các đĩa nhỏ ở mỗi cọc luôn ở trên đĩa lớn hơn. Trò chơi kết thúc khi ta chuyển hết các đĩa từ cọc ban đầu sang một cọc khác. Đến cuối thế kỷ XIX, bài toán tổng quát của bài toán này đã được giải bởi nhà toán học người Pháp Edouard Lucas (1842 - 1891) với tên gọi bài toán Tháp Hà Nội. Đây là một bài toán kinh điển mà hầu hết các sinh viên học lập trình tin học đều phải tìm cách giải quyết. Theo như phương pháp mà ông đã tìm ra thì ở bài toán cổ trên, nếu mỗi lần di chuyển một đĩa hết 1 giây thì phải cần tới 264-1 giây mới di chuyển xong. Đây là một số có dạng giống như đáp số của bài toán số hạt thóc trên bàn cờ vua.

Chơi ô ăn quan
Tranh "Chơi ô ăn quan" của họa sĩ Nguyễn Phan Chánh
Một số loại cờ được chơi thông dụng ở Việt Nam là: cờ caro, cờ cá ngựa, cờ tỷ phú, cờ hùm, ô ăn quan... Điều đặc biệt là ô ăn quan là một trò chơi dân gian nhưng những phiên bản khác của nó thì có ở nhiều nơi trên thế giới. Xa xưa nhất, trò chơi dạng này từng xuất hiện ở Ai Cập từ cách đây hơn 3.000 năm rồi lan truyền qua Ả rập và được những người Hồi giáo mang đi nhiều nơi. Một số nơi ở Châu Á cũng có trò chơi này như Sri Lanka, Indonesia, Thái Lan, Malaysia, Philippines... Ở Việt Nam, không rõ trò chơi này xuất hiện từ khi nào. Các trò chơi tương tự ô ăn quan của Việt Nam có biến thể về luật chơi, chẳng hạn chỉ được bốc sỏi theo một chiều, hoặc bàn chơi có 12 hoặc 14 ô. Một số khác thì thay quân "quan" bởi nhiều "dân" hay bàn chơi cho 3, 4 người bằng cách vẽ hình viền tam giác, viền hình vuông.... Ô ăn quan ở Việt Nam dành cho hai người chơi. Bàn chơi có hình chữ nhật, hai bên có 5 ô, mỗi ô đựng 5 viên sỏi, tượng trưng cho 5 "dân". Hai đầu hình chữ nhật là hai viên sỏi to hơn, tượng trưng cho "quan". Mỗi "quan" bằng 5 "dân". Về cách bốc sỏi, chia sỏi và "ăn" thì luật chơi giống nhau ở tất cả các nước. Người ta cho rằng ô ăn quan là trò chơi lâu đời của Việt Nam, lấy cảm hứng từ những cánh đồng lúa nước. Tích xưa kể lại, ông Mạc Hiển Tích (đỗ Trạng nguyên năm 1086) từng viết một tác phẩm bàn về cách tính toán trong trò chơi này, trong đó ông đã đề cập đến số âm. Vì tác phẩm nay đã không còn nên chúng ta chưa rõ ông đã viết như thế nào. Ta biết ô ăn quan là một trò chơi đếm số dạng tổ hợp, người chơi cần tính toán, lựa chọn cách chơi hợp lý để giành điểm cao hơn cho mình. Mỗi cách lựa chọn lại ra một bài toán tổ hợp mới. Tiếc là đến nay, chưa có bài viết hay nghiên cứu nào của các nhà toán học về những khả năng chơi khác nhau của trò chơi này. Trong khi, cờ vua hay cờ tướng thì đã được coi như một môn thể thao trí tuệ, khoa học và được nghiên cứu khá nhiều.

Còn tiếp...

Về VNMATH.COM

VNMATH hoạt động từ năm 2008 với slogan Trao đổi để học hỏi, Sẻ chia để vươn lên. Hiện nay VNMATH.COM là trang web Toán học có lượt truy cập lớn nhất Việt Nam.

Chia sẻ bài viết này


Bài viết liên quan

Không có nhận xét nào :

Để lại Nhận xét