Câu hỏi 10
Trên bàn cờ $5 \times 9$ ô vuông, người ta chơi trò chơi sau. Ban đầu, một số con ếch được đặt ngẫu nhiên lên một số ô, mỗi ô chứa không quá một con ếch. Một lượt chơi gồm việc di chuyển tất cả các con ếch theo các quy tắc sau:
- Mỗi con ếch có thể được di chuyển một ô lên trên, xuống dưới, sang trái hoặc sang phải;
- Nếu một con ếch di chuyển lên hoặc xuống trong một lượt thì ở lượt kế tiếp nó phải di chuyển sang trái hoặc sang phải, và ngược lại;
- Vào cuối mỗi lượt, không ô nào chứa hai con ếch trở lên.
Trò chơi dừng lại nếu không thể hoàn thành thêm một lượt nữa. Chứng minh rằng nếu ban đầu đặt 33 con ếch lên bàn cờ thì trò chơi chắc chắn sẽ dừng lại. Chứng minh thêm rằng có thể đặt 32 con ếch lên bàn cờ sao cho trò chơi có thể tiếp diễn mãi mãi.
- Mỗi con ếch có thể được di chuyển một ô lên trên, xuống dưới, sang trái hoặc sang phải;
- Nếu một con ếch di chuyển lên hoặc xuống trong một lượt thì ở lượt kế tiếp nó phải di chuyển sang trái hoặc sang phải, và ngược lại;
- Vào cuối mỗi lượt, không ô nào chứa hai con ếch trở lên.
Trò chơi dừng lại nếu không thể hoàn thành thêm một lượt nữa. Chứng minh rằng nếu ban đầu đặt 33 con ếch lên bàn cờ thì trò chơi chắc chắn sẽ dừng lại. Chứng minh thêm rằng có thể đặt 32 con ếch lên bàn cờ sao cho trò chơi có thể tiếp diễn mãi mãi.