Phân tích: Deceitful War

Trò chơi War tối ưu nhất của Ken

Trước tiên, hãy nghĩ về kết quả tốt nhất có thể cho Ken trong một trò chơi War. Giả sử số điểm tối đa Ken có thể giành được là \(k\); sau một hồi suy nghĩ, bạn sẽ thấy rằng Ken có thể đạt được kết quả đó nếu \(k\) khối gỗ nặng nhất của Ken được chơi theo thứ tự giảm dần đối với \(k\) khối gỗ nhẹ nhất của Naomi, cũng theo thứ tự giảm dần.

Cặp đấu chính xác đó có thể sẽ không xảy ra, và nếu không biết trọng lượng các khối gỗ của Naomi, Ken thậm chí còn không biết cặp đấu đó sẽ là gì; nhưng Ken có thể tuân theo một chiến thuật đơn giản để dù sao cũng ghi được \(k\) điểm.

Chiến thuật của Ken

Chiến thuật của Ken rất đơn giản: khi Naomi chơi một khối gỗ, Ken đánh bại nó bằng khối gỗ nhẹ nhất có thể nếu anh ấy có thể; và nếu anh ấy không thể đánh bại nó, anh ấy chơi khối gỗ nhẹ nhất của mình. Rõ ràng là việc sử dụng chiến thuật như vậy sẽ tối đa hóa khả năng chiến thắng của Ken cho các vòng tiếp theo vì Ken không chỉ giành được một điểm cho vòng này mà còn bảo tồn được các khối gỗ nặng hơn của mình cho các vòng tiếp theo.

Đoạn văn bản sau đây chứng minh rằng chiến thuật này sẽ giúp Ken giành được số điểm tối đa có thể, \(k\), bất kể Naomi làm gì.

Chứng minh

Trong chiến thuật này, để giành được \(k\) điểm, Ken muốn duy trì một bất biến: sau khi Ken đã ghi được \(i\) điểm, \(k-i\) khối gỗ nặng nhất của Ken vẫn sẽ đánh bại \(k-i\) khối gỗ nhẹ nhất của Naomi. Khi \(k-i\) bằng 0, Ken không thể giành thêm bất kỳ điểm nào nữa vì khối gỗ nặng nhất của anh ấy nhẹ hơn bất kỳ khối gỗ nào của Naomi. Do đó, nếu bất biến đó được duy trì, Ken phải có \(k\) điểm khi không còn khối gỗ nào.

Chứng minh bất biến:

Giả sử Ken đang có \(i\) điểm. Chúng ta sẽ đề cập đến các "cặp" khối gỗ sau này: Ken còn lại \(k - i\) khối gỗ nặng nhất và khối gỗ nặng thứ \(j\) còn lại của anh ấy được "ghép cặp" với khối gỗ nhẹ thứ \((k-i-j)\) còn lại của Naomi. Có ba loại khối gỗ Naomi có thể chơi:

1. Nếu Naomi chơi một khối gỗ nặng hơn tất cả các khối gỗ của Ken, nó không nằm trong số \(k-i\) khối gỗ nhẹ nhất của Naomi. Ken sẽ chơi khối gỗ nhẹ nhất của mình (khối này không nằm trong số \(k-i\) khối gỗ nặng nhất của anh ấy), và bất biến được duy trì.
2. Nếu Naomi chơi một khối gỗ nhẹ hơn một trong các khối gỗ của Ken nhưng không nằm trong số \(k-i\) khối gỗ nhẹ nhất của Naomi, Ken sẽ đánh bại nó bằng khối gỗ nặng nhất của mình — trong trường hợp đó \(k-i-1\) khối gỗ nhẹ nhất của Naomi sẽ thua \(k-i-1\) khối gỗ nặng nhất còn lại của Ken, vì không có gì thay đổi về cách các khối gỗ còn lại được ghép cặp — hoặc Ken sẽ đánh bại nó bằng một thứ gì đó nhẹ hơn, trong trường hợp đó vị trí của anh ấy rõ ràng là không tệ hơn. Dù thế nào Ken cũng có \(i+1\) điểm và bất biến được duy trì.
3. Nếu Naomi chơi một khối gỗ từ \(k-i\) khối gỗ nhẹ nhất của mình, Ken sẽ đánh bại nó bằng khối gỗ mà nó được ghép cặp, trong trường hợp đó Ken hiện có \(i+1\) điểm và \(k-i-1\) cặp còn lại được duy trì; hoặc Ken sẽ đánh bại nó bằng một thứ gì đó nhẹ hơn, trong trường hợp đó Ken rõ ràng không tệ hơn. Dù thế nào Ken cũng có \(i+1\) điểm và bất biến được duy trì.

Trò chơi War tối ưu nhất của Naomi

Như chúng ta đã thấy trong phần chứng minh ở trên, Ken có thể ép buộc số điểm tối đa có thể của mình trong trò War bất kể Naomi làm gì. Không có gì lạ khi Naomi mệt mỏi với việc chơi nó!

Trò chơi Deceitful War tối ưu nhất của Naomi

Tuy nhiên, trong Deceitful War, tình huống hoàn toàn ngược lại: như chúng ta sẽ chỉ ra trong các đoạn tiếp theo. Trong War, Ken có được các cặp đấu tốt nhất cho mình nhưng Naomi sẽ có được các cặp đấu tốt nhất cho mình trong Deceitful War.

Chiến thuật của Naomi cho Deceitful War

Có một vài chiến thuật để Naomi chơi Deceitful War một cách tối ưu. Chúng tôi trình bày một chiến thuật ở đây.
Chiến thuật của Naomi cho việc đó gần như là hiển nhiên. Giả sử \(k\) là điểm số tốt nhất Naomi có thể đạt được. Naomi có thể ghi được \(k\) điểm bằng cách ghép \(k\) khối gỗ nặng nhất của mình với \(k\) khối gỗ nhẹ nhất của Ken.

Naomi sẽ lấy khối gỗ nặng thứ \(i\) của mình và nói với Ken rằng nó nặng hơn tất cả các khối gỗ của Ken. Ken sẽ tin cô ấy và chơi khối gỗ nhẹ nhất của mình, đó là điều Naomi muốn. Bây giờ Naomi chỉ cần lặp lại quy trình chơi các khối gỗ nặng còn lại của mình từ nhẹ nhất đến nặng nhất và kích động Ken chơi khối gỗ nhẹ nhất của anh ấy từ nhẹ nhất đến nặng nhất. Sau khi Naomi ghi được \(k\) điểm, khối gỗ nặng nhất của cô ấy sẽ nhẹ hơn bất kỳ khối gỗ nào hiện có của Ken. Bây giờ, vì Naomi không thể nói dối được nữa, Naomi chơi các khối gỗ còn lại của mình mà không nói dối về khối lượng của chúng.

Kết luận

Đó là một sự đối xứng đặc biệt đẹp đẽ khi Ken có thể đạt được cách ghép cặp tối ưu của mình bằng cách phản ứng, mặc dù trung thực và không có thông tin; và Naomi có thể đảo ngược lợi thế của Ken bằng cách đánh bại khả năng phản ứng của Ken bằng sự không trung thực và thông tin hoàn hảo.

Dựa trên phân tích chính thức của Google Code Jam.