Các Admin, các cao thủ cho mình hỏi bài này giải quyết thế nào? Nếu mà là bài toán Nim ăn được viên cuối cùng thì thắng thì giải được rồi. Nhưng bài này là phải ăn viên cuối cùng thì thua nên mình chưa biết giải quyết thế nào?

Game theory, part 1, section 2.5

sonpascal93 viết:

QUOTE:
Các Admin, các cao thủ cho mình hỏi bài này giải quyết thế nào? Nếu mà là bài toán Nim ăn được viên cuối cùng thì thắng thì giải được rồi. Nhưng bài này là phải ăn viên cuối cùng thì thua nên mình chưa biết giải quyết thế nào?

Bài này khá dễ, anh nên tự làm

@ronaldinho_94: Bài này mà k biết định lý Nim-Sum thì dễ cái nỗi gì.
@anh Khuê: Bài này thì lại là "ai lấy phải viên cuối cùng" thì thua (ngược so với Nim-SUm bình thường) nên em thấy hơi vướng.

@Ronaldinho_94: Dùng Grundy hay định lý Nim-Sum, bài này mà k đọc tài liệu về Game Theory thì chắc chắn k thể làm được

Bài này tên nó là Misere Nim, em tìm trên mạng nhiều lắm

Có anh nào có sách (e-book) Game Theory, share cho em với

alex_pythagore viết:

QUOTE:
Có anh nào có sách (e-book) Game Theory, share cho em với :x

http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf

@ Dành cho những bạn chưa có điều kiện tìm hiểu các tài liệu tiếng anh ở trên, sau đây là một cách hiểu của mình với bài toán misere nim:
- Trường hợp 1: không có loại kẹo nào có nhiều hơn 1 viên. Rõ ràng nếu tổng số kẹo chẵn thì John thắng còn ngược lại thì John thua.
- Trường hợp 2: có ít nhất một loại kẹo có nhiều hơn 1 viên. Ta chứng minh được là nếu ban đầu nim-sum (tức là xor của các loại kẹo) = 0 thì John thua, > 0 thì John thắng. Thật vậy, CM rằng nim-sum > 0 thì John thắng: John sẽ chơi như nim bình thường đến khi chỉ còn đúng một loại kẹo có số kẹo lớn hơn 1. Vì khi trường hợp đó xảy thì chắc chắn là đến lượt John chơi bởi vì khi đó nim-sum chắc chắn > 0. Từ đây, John sẽ lấy hết loại kẹo đó (loại còn nhiều hơn 1 viên) hoặc để lại một viên loại đó tùy sao đưa về thế thắng trong trường hợp 1 ở trên. CM nim-sum = 0 thì John thua cũng tương tự.

Thanks lightning rất nhiều