Câu hỏi 66
Cho $k$ là một số nguyên dương cố định. Một dãy hữu hạn các số nguyên $x_1, x_2, \dots, x_n$ được viết trên bảng. Pepa và Geoff chơi một trò chơi diễn ra theo các lượt như sau.
* Trong mỗi lượt, đầu tiên Pepa chia dãy hiện có trên bảng thành hai hoặc nhiều dãy con liên tiếp (tức là gồm các số đứng liền nhau). Tuy nhiên, nếu số dãy con lớn hơn 2 thì tổng các số trong mỗi dãy con phải chia hết cho $k$.
* Sau đó Geoff chọn một trong các dãy con mà Pepa đã tạo ra và xóa tất cả các dãy con còn lại khỏi bảng.
Trò chơi kết thúc khi trên bảng chỉ còn lại một số. Chứng minh rằng Pepa có thể chọn các nước đi sao cho, bất kể Geoff đi thế nào, trò chơi kết thúc sau nhiều nhất $3k$ lượt.
(Poland)
* Trong mỗi lượt, đầu tiên Pepa chia dãy hiện có trên bảng thành hai hoặc nhiều dãy con liên tiếp (tức là gồm các số đứng liền nhau). Tuy nhiên, nếu số dãy con lớn hơn 2 thì tổng các số trong mỗi dãy con phải chia hết cho $k$.
* Sau đó Geoff chọn một trong các dãy con mà Pepa đã tạo ra và xóa tất cả các dãy con còn lại khỏi bảng.
Trò chơi kết thúc khi trên bảng chỉ còn lại một số. Chứng minh rằng Pepa có thể chọn các nước đi sao cho, bất kể Geoff đi thế nào, trò chơi kết thúc sau nhiều nhất $3k$ lượt.
(Poland)