1. Bài toán

Cho một dãy gồm n đống đá, mỗi đống có một số lượng đá nhất định. Hai người chơi (A và B) lần lượt chọn lấy một đống đá ở đầu hoặc cuối dãy trong mỗi lượt. A đi trước. Trò chơi kết thúc khi không còn đống đá nào. Ai lấy được tổng số đá nhiều hơn sẽ thắng. Điều kiện:

• Số đống đá là chẵn
• Tổng số lượng đá là lẻ ( luôn có ngừoi chiến thắng)

2. Ý tương sơ khai

• Nhìn vô bài toán , ta mường tượng ngay đến việc tìm công thức chung hay dyanmic programming để lên chiến lược cho ngừoi thắng. Nhưng ko, bài toán này tiếp cận với 1 hướng dễ hơn nhiều
• Vì với điều kiệnb bài toán A luôn đi trước. Phải chăng là 1 lợi thế tuyệt đối, người xuất phát trước luôn là người có lợi thế hơn ( nhưng chưa chắc có ưu thế hơn đường dài). Làm mik nhớ đến câu *(ko liên quan lắm đâu) * :

Việc do người mưu, thành công nhờ trời

3. Phân tích và Lý thuyết

Bạn có nhận ra điều mà số ít ng thấy đc là A luôn khống chế được việc mình chỉ lấy được đống đá ở chẵn / lẻ. Tôi sẽ chứng minh cho bn:

Gọi mảng ban đầu là a0,a1,...,an−1a0,a1,...,an−1, với n chẵn.
Nếu A lấy a0 - chẵn lớn hơn, Bob chỉ còn được lấy ở chuỗi a1,...,an−1a1,...,an−1 (toàn bộ chỉ số dịch phải 1 nhưng chẵn/lẻ vẫn giữ nguyên) - 2 đầu lẻ dù B có lấy thế nào A vẫn lấy được chẵn.
Nếu A lấy an−1 - lẻ lớn hơn, chuỗi còn lại là a0,...,an−2a0,...,an−2 (chẵn/lẻ giữ nguyên) - tương tự .
Cứ sau mỗi lượt, hai đầu bị lấy đi liên tục, thứ tự chẵn/lẻ luôn bảo toàn.
A xác định chỉ cần chọn chỉ số chẵn hoặc lẻ ở lượt đầu, thì các lượt sau sẽ luôn lấy được đúng kiểu chỉ số đó dù B chọn như thế nào.

4. Kết luận

Bằng cách này, A luôn kiểm soát được toàn bộ đá ở các vị trí chẵn hoặc lẻ, do đó sẽ thắng nếu tổng đá ở nhóm mà A chọn lớn hơn. Và trong bài toán này, A luôn có thể đảm bảo chiến thắng nếu chơi tối ưu.

Vậy bài toán này: return True 😀😀😀😀.