Bài 5
Ốc sên Turbo đang ở hàng trên cùng của một lưới ô vuông gồm 2024 hàng và 2023 cột, muốn đi tới hàng dưới cùng. Tuy nhiên có 2022 con quái vật ẩn, mỗi hàng (trừ hàng đầu và hàng cuối) có đúng một con, không có hai con quái vật nào ở cùng một cột. Turbo thực hiện một loạt các lần thử để đi từ hàng đầu tiên tới hàng cuối cùng. Ở mỗi lần thử, Turbo chọn một ô bất kỳ ở hàng đầu tiên để xuất phát, rồi liên tục di chuyển sang một ô kề cạnh (theo phương ngang hoặc dọc). (Turbo được phép quay lại một ô đã đi qua trước đó.) Nếu Turbo đi vào một ô có quái vật, lần thử đó kết thúc và Turbo bị đưa trở lại hàng đầu tiên để bắt đầu một lần thử mới. Các con quái vật không di chuyển giữa các lần thử, và Turbo nhớ được ô nào mình đã đi qua có quái vật hay không. Nếu Turbo tới được một ô bất kỳ ở hàng cuối cùng, lần thử đó kết thúc và Turbo chiến thắng. Hãy tìm số nguyên nhỏ nhất sao cho Turbo có một chiến lược đảm bảo tới được hàng cuối cùng trong tối đa lần thử, bất kể quái vật được đặt ở đâu.
Bước 1 trên 5: Hai lần thử không bao giờ là đủ
Hiểu nôm na
Ô đầu tiên mà Turbo bước vào ở hàng 2 hoàn toàn có thể chứa quái vật, và ở lần thử tiếp theo, ô mới đầu tiên mà Turbo bước vào ở hàng 3 cũng có thể lại chứa quái vật, nên không có chiến lược cố định nào vượt qua được hai lần thất bại.
Phân tích chi tiết
Trong lần thử đầu tiên của Turbo, ngay khi anh ta bước vào hàng , đối thủ có thể đã đặt sẵn một quái vật ở đó, khiến lần thử kết thúc. Ở lần thử thứ hai, Turbo phải lần đầu tiên bước vào hàng tại một cột nào đó; đối thủ lại có thể đã đặt sẵn một quái vật ở đó. Điều này cho thấy không có chiến lược nào đảm bảo thành công trong ít hơn lần thử, vậy .