Mã đi tuần

[chezz]

Mã đi tuần là một bài đố thú vị: đặt con Mã ở một vị trí trên bàn cờ trống trơn, liệu con Mã này có thể đi khắp được tất cả các ô / điểm bàn cờ, mỗi điểm chỉ đi một lần?

Người ta đã chứng minh đi được như vậy dù con Mã đứng ở ô bất kỳ của cờ Vua.

Chúng tôi cũng chứng minh điều tương tự với cờ Tướng: Dù xuất phát ở bất cứ điểm nào, con Mã cũng đi "tuần" được đủ 90 điểm của cờ Tướng.

Dưới đây là hai lời giải trong cờ Tướng. Vị trí xuất phát của con Mã được đánh dấu bằng hình tròn vàng.

Bài 1


Bài 2

[chezz]

Video:

[sapa2015]

Cái này không gọi là lời giải được

[chezz]

Cái này không gọi là lời giải được

Bạn nói rõ hơn được không? Vì sao lại không phải?

[kiemkhach]

Bạn nói rõ hơn được không? Vì sao lại không phải?

Ý là, lời giải ở đây là phải đưa ra cách chứng minh bằng toán học hoặc lập trình. Còn đưa ra 1 trường hợp thì mới dừng lại ở trường hợp đó thôi. Còn như kể cả đưa ra đủ kết quả của 90 trường hợp (ứng với 90 điểm xuất phát)thì đó là liệt kê, chứ cũng không gọi là chứng minh. Chứng minh là phải đưa ra 1 đường hướng giải quyết, bất kể con mã nằm ở đâu, bất kể bàn cờ dài rộng như thế nào.

[Caruri]

Cái này là dạng chứng minh sự tồn tại, chủ thớt nêu ra một định đề là tôi chứng minh là cái đó tồn tại (việc con mã ở bất kỳ điểm nào cũng nhảy được hết 90 ô) và đưa ra được sự tồn tại của nó (bằng một lời giải) thì chứng minh này đầy đủ rồi bạn.

Chứng minh sự không tồn tại mới khó, ví dụ chỉ ra rằng việc đó không thể làm được, thì không thể đưa ra ví dụ như nó tồn tại. Một bài toán nổi tiếng chỉ ra sự không tồn tại là bài toán Fermat lớn, mấy trăm năm mới chứng minh xong, dù đã chứng minh cho rất nhiều trường hợp nhỏ nhưng không thể coi là tổng quát được.

Một ví dụ khác: chứng minh loài cá vây tay còn tồn tại trên trái đất, thì chỉ cần bắt một con đem trưng ra là đủ, còn chứng minh con tê giác một sừng đã tuyệt chủng tại Việt Nam thì mới là khó.

Còn chứng minh với bàn cờ dài rộng thế nào thì là bài toán tổng quát rồi, ở đây là một bài toán cụ thể với bàn 9 x 10 chứ không phải bài tổng quát với bàn m x n. Nếu đòi chứng minh tồn tại với bàn m x n mà chỉ có đưa ra lời giải của bàn 9 x 10 thì mới là thiếu sót.

[onlylovenh]

Cái này là dạng chứng minh sự tồn tại, chủ thớt nêu ra một định đề là tôi chứng minh là cái đó tồn tại (việc con mã ở bất kỳ điểm nào cũng nhảy được hết 90 ô) và đưa ra được sự tồn tại của nó (bằng một lời giải) thì chứng minh này đầy đủ rồi bạn.

Chứng minh sự không tồn tại mới khó, ví dụ chỉ ra rằng việc đó không thể làm được, thì không thể đưa ra ví dụ như nó tồn tại. Một bài toán nổi tiếng chỉ ra sự không tồn tại là bài toán Fermat lớn, mấy trăm năm mới chứng minh xong, dù đã chứng minh cho rất nhiều trường hợp nhỏ nhưng không thể coi là tổng quát được.

Một ví dụ khác: chứng minh loài cá vây tay còn tồn tại trên trái đất, thì chỉ cần bắt một con đem trưng ra là đủ, còn chứng minh con tê giác một sừng đã tuyệt chủng tại Việt Nam thì mới là khó.

Còn chứng minh với bàn cờ dài rộng thế nào thì là bài toán tổng quát rồi, ở đây là một bài toán cụ thể với bàn 9 x 10 chứ không phải bài tổng quát với bàn m x n. Nếu đòi chứng minh tồn tại với bàn m x n mà chỉ có đưa ra lời giải của bàn 9 x 10 thì mới là thiếu sót.

Câu trả lời rất hay và chính xác. Chủ thớt đã chứng minh được mệnh đề mình đưa ra vì đặt con mã ở bất kì điểm nào trên 90 điểm của bàn cờ tướng chỉ cần đi theo hướng dẫn của chủ thớt là được. Rất thú vị.

[kiemkhach]

Cái này là dạng chứng minh sự tồn tại, chủ thớt nêu ra một định đề là tôi chứng minh là cái đó tồn tại (việc con mã ở bất kỳ điểm nào cũng nhảy được hết 90 ô) và đưa ra được sự tồn tại của nó (bằng một lời giải) thì chứng minh này đầy đủ rồi bạn.

Chứng minh sự không tồn tại mới khó, ví dụ chỉ ra rằng việc đó không thể làm được, thì không thể đưa ra ví dụ như nó tồn tại. Một bài toán nổi tiếng chỉ ra sự không tồn tại là bài toán Fermat lớn, mấy trăm năm mới chứng minh xong, dù đã chứng minh cho rất nhiều trường hợp nhỏ nhưng không thể coi là tổng quát được.

Một ví dụ khác: chứng minh loài cá vây tay còn tồn tại trên trái đất, thì chỉ cần bắt một con đem trưng ra là đủ, còn chứng minh con tê giác một sừng đã tuyệt chủng tại Việt Nam thì mới là khó.

Còn chứng minh với bàn cờ dài rộng thế nào thì là bài toán tổng quát rồi, ở đây là một bài toán cụ thể với bàn 9 x 10 chứ không phải bài tổng quát với bàn m x n. Nếu đòi chứng minh tồn tại với bàn m x n mà chỉ có đưa ra lời giải của bàn 9 x 10 thì mới là thiếu sót.

Rõ ràng bạn bị nhầm lẫn rồi. đề bài là "dù đặt con mã xuất phát ở vị trí nào nó cũng nhảy hết bàn cờ"
Bài này rõ ràng là chứng minh sự không tồn tại, sao lại coi là chứng minh sự tồn tại được. Rõ ràng có những 90 trường hợp bắt đầu. như vậy phải có 90 lời giải cho mỗi cách đặt điểm xuất phát.
Chưa tính đến bài toán mở rộng như trên tôi đề cập, chỉ xét riêng bài toán bàn cờ tướng, thì rõ ràng không thể coi đây là chứng minh sự tồn tại được.
Đặt con mã xuất phát ở vị trí (7, 1) rồi đưa ra lời giải thì chỉ đúng khi nó xuất phát ở điểm (7, 1)
và không thể dựa vào đó để khẳng định rằng nếu xuất phát ở (1, 1) thì cũng sẽ có lời giải.

Trừ khi đề bài là "tìm ít nhất 1 cách sao cho con mã đi hết bàn cờ n x m" => lúc đó mới được coi là bài toán chứng minh sự tồn tại. Cũng giống như việc chứng minh 10 quả trứng trong rỏ toàn là trứng gà (tương đương với việc 90 trường hợp xuất phát, trường hợp nào cũng có lời giải) khác hoàn toàn với việc chứng minh có ít nhất 1 quả trứng gà trong rỏ (tương đương với việc chứng minh có ít nhất 1 cách trong 90 cách xuất phát thỏa mãn đề bài).

Hoặc là giữ nguyên đề bài nhưng tìm được cách nào đó mà sao cho từ vị trí kết thúc, con mã có thể nhảy đến vị trí bắt đầu của nó bằng 1 bước nhảy => lập thành 1 vòng tròn => con mã ở vị trí nào cũng vậy => thỏa mãn đề bài. Nhưng mà như 2 cách giải của tác giả đưa ra thì cả 2 cách thì điểm bắt đầu và kết thúc đều cách xa nhau.

[kiemkhach]

Câu trả lời rất hay và chính xác. Chủ thớt đã chứng minh được mệnh đề mình đưa ra vì đặt con mã ở bất kì điểm nào trên 90 điểm của bàn cờ tướng chỉ cần đi theo hướng dẫn của chủ thớt là được. Rất thú vị.

Vẫn còn nhiều bạn nhầm lẫn nặng thế này -> khó đỡ.
Đặt mã ở vị trí (7, 1) và đưa ra câu trả lời => chỉ đúng với điểm (7, 1)
Nhưng liệu có còn đúng khi đặt ở các vị trí khác ??? có còn đúng khi bàn cờ là m x n ???
Chứng minh là hướng đến việc đúng hoàn toàn, rồi tổng quát hóa bài toán lên, chứ không có chuyện cảm tính mơ hồ.
Việc đưa ra 1 2 đáp án (ứng với 1 2 điểm xuất phát) nó chỉ là liệt kê thôi.

[onlylovenh]

Vẫn còn nhiều bạn nhầm lẫn nặng thế này -> khó đỡ.
Đặt mã ở vị trí (7, 1) và đưa ra câu trả lời => chỉ đúng với điểm (7, 1)
Nhưng liệu có còn đúng khi đặt ở các vị trí khác ??? có còn đúng khi bàn cờ là m x n ???
Chứng minh là hướng đến việc đúng hoàn toàn, rồi tổng quát hóa bài toán lên, chứ không có chuyện cảm tính mơ hồ.
Việc đưa ra 1 2 đáp án (ứng với 1 2 điểm xuất phát) nó chỉ là liệt kê thôi.

Mình thấy bạn mới là người nhầm lẫn nặng, hãy nhìn hình số 2, vị trí kết thúc có thể nhảy đến vị trí bắt đầu, suy ra nó có thể đi vòng tròn quanh 90 điểm của bàn cờ dù đặt ở bất kì điểm nào chứ ko phải 1 hay 2 điểm như bạn nói. Hãy nhìn và nghĩ thật kĩ trước khi phản biện áp đặt người khác. Thân.