|
Nhặt sỏi! Có 2 đống m và n viên sỏi. Hai người lần lượt lấy một số viên sỏi từ 1 trong 2 đống hoặc cùng một số viên từ cả hai đống. Ai không đi tiếp được là thua. Khi nào người thứ 1 (hoặc người thứ 2) có chiến thuật thắng? |
Hic, chắc chắn cóa sự nhầm lẫn ở đây, theo mình hiểu thì người thứ nhất bốc m+n viên trong 2 đống thì người 2 thua chắc Edit Xin lỗi mình nhầm |
Lại hiểu nhầm đề rồi! Nếu muốn lấy từ cả hai đống thì phải lấy hai đống như nhau: Ví dụ cùng lấy 3 viên ở mỗi đống chẳng hạn! |
Xét tập S gồm các cặp m,n như sau M N 1 2 3 5 4 7 6 10 8 13 9 15 11 18 ......... Trong đó, hiệu n-m là các số tự nhiên tăng dần 1 đơn vị, m là các số tự nhiên tăng dần và số nào đã xuất hiện ở N thì không xuất hiện ở M Người chơi thứ 2 sẽ thắng nếu số sỏi ở 2 đống trùng với một trong các cặp M,N của S. Ngược lại, người chơi thứ nhất thắng. Chiến thuật là đưa số sỏi trong hai đống về 1 trong số các cặp (m,n) của tập S |
Khè khè đay là bài toán về trò chơi sông Nim! Chiến thuất chơi của người 1 thắng hay thua phụ thuộc trạng thái của m và n! Sử dụng hệ nhị phân là cốt lõi của trò này! PS:Nếu m=n thì người 1 thắng rùi!:) |
Nhân tiện noía về trò chơi Nim có 1 phần chiến thuật trò chơi mình cũng muốn trao đổi đó là : Bản chất của 1 trò chơi bốc sỏi Nim là tìm tính chất của bộ (k,m,n) sao cho với mọi cách bốc sỏi thành bộ (k,m,n), tính chất này mất đi và từ 1 bộ kô có tính chất này sau 1 số cách bốc ta lại đưa về được bộ mới có tính chất này. Giả sử có 1 tính chất như vậy và bộ (0,0,0) là 1 bộ thỏa tính chất T đó. Khi đó người đi trước sẽ thắng nấu như bộ (k,m,n) ban đầu có tính chất này và ngược lại, người 2 sẽ thắng.Với bài toán Nim chỉ có 2 đống , tính chất T đó là m=n. Một số điều đọc được như thế. Hi vọng sẽ có những trao đổi với các bạn khác về phần này. |
Giả sử có 2 đống , 1 đống 1 viên 1 đống 3 viên. Khi đó, người thứ nhất lấy 1 viên từ đống thứ 2 ,tức bây giờ có 1 đống 1 và 1 đống 2.Khi đó thì dù người thứ 2 lấy như thế nào thì người thứ nhất vẫn thắng. Do đó, bài trên không phải là trò chơi Nim :) Trò chơi Nim nó khác tí :D Đó là mỗi người lần lượt lấy đi một số bất kì viên sỏi nào đó hoặc lấy đi tất cả một đống nào đó. Còn ở đây, có thể lấy 2 đống cùng số sỏi |
Hì mình noái cái 2 đống là trò chơi Nim cho trường hợp chỉ cóa 2 đống mà, tất nhiên nóa hok là trò chơi Nim vì trò chơi Nim cóa tới 3 đống sỏi, điều mình mún noái ở đây chính là tư tưởng để xây dựng tròa chơi này, điều mình đã đề cập :D |
Trò chơi trên có tên là Wythoff games! |
Ta có 1 dạng thứ 2 là : Ta có thể bốc 1 số viên ở 1 đống hoặc bốc ở mỗi đống 1 số viên ( khác nhau) với điều kiện là giá trị tuyệt đối của chúng $\leq 2 $ . Hỏi ai thắng ! Lần này thì có lẽ ko cần đk $m \neq n $ :) |
Bài wythoff games ban đầu ; ta tìm đc Thế thua là ( 7 thế đầu tiên ) x: 0 1 3 4 6 8 9 y: 0 2 5 7 10 13 15 n: 0 1 2 3 4 5 6 $x=[1,6.n] ; y= [1,6(n+1)] $ Cách đánh là cố gắng đối thủ đưa về thế trên và tránh những khu vực " nguy hiểm " . Tuy nhiên hình như cũng còn tùy vào trạng thái của $m;n $ |
Trích:
Cách này tớ nghĩ đúng mà nhẩy :D Bác nào thử đưa ra 1 trường hợp để bốc thử thôi (Số sỏi ít thôi ,bốc cho nhanh :D ) |
Hừm cách làm của pi.14 đúng rồi đấy! Các bạn có thể tham khảo thêm trong cuốn problem solving strategies có trong trang này! |
Chủ topic cho thử 1 vd xem nào ! :) . Đã có đc pp tìm trạng thái thua tuy nhiên lúc ứng dụng thì còn hơi lộn xộn lắm . Hay là bắt đầu là $x=11;y=18 $ ( trạng thái thua ) xem . $A $ đi trước và đang ở trạng thái thua . $A $ phải né và ko đc để $B $ đưa vào trạng thái thua khác nên A sẽ đi $x=11;y=14 $ . Anh Trình đi thử xem ; spam đi rồi dọn dẹp sau mà ! :) |
Khi đó A chắc chắn thua vì B sẽ đi tiếp đến $(4;7) $là một trạng thái thua khác. (Để chọn xem nên đưa về trạng thái thua nào thì hãy xem $y-x $ là bao nhiêu thì đưa về trạng thái thua có hiệu tương ứng, ví dụ ở đây là $3 $ thì đưa về $(4;7) $). Còn ai thắc mắc nữa không? Trích:
|
| Múi giờ GMT. Hiện tại là 07:44 AM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.