Câu hỏi 88
Cho $k$ là một số nguyên dương. Cô bé và nhà ảo thuật trên cầu vượt chơi một trò chơi. Ban đầu, cô bé đặt $N = 2^k$ quả bóng phân biệt thành một hàng ngang trên bàn và úp mỗi quả bóng bằng một chiếc cốc. Ở mỗi lượt, cô bé chọn hai chiếc cốc, sau đó nhà ảo thuật có thể đổi chỗ hai quả bóng trong hai cốc đó, hoặc làm động tác giả để bóng trong hai cốc giữ nguyên. Cô bé không thể phân biệt qua động tác của nhà ảo thuật xem đó có phải động tác giả hay không, và cũng không nhìn thấy bóng trong các cốc trước và sau động tác.
Sau $M = k \times 2^{k-1}$ lượt, nhà ảo thuật mở tất cả các cốc để cô bé kiểm tra quả bóng trong từng cốc. Nếu lúc đó cô bé có thể xác định chắc chắn nhà ảo thuật có làm động tác giả hay không ở mỗi lượt trong $M$ lượt, thì cô bé thắng. Chứng minh rằng cô bé có chiến lược thắng.
Sau $M = k \times 2^{k-1}$ lượt, nhà ảo thuật mở tất cả các cốc để cô bé kiểm tra quả bóng trong từng cốc. Nếu lúc đó cô bé có thể xác định chắc chắn nhà ảo thuật có làm động tác giả hay không ở mỗi lượt trong $M$ lượt, thì cô bé thắng. Chứng minh rằng cô bé có chiến lược thắng.