Bài 4
Cho là một số nguyên. Có ô trên một đường tròn, mỗi ô được gán 0 hoặc 1, và một con gà trống đứng trên một ô. Lặp lại quy tắc sau: nếu gà trống đứng trên ô mang số 0, nó đổi số đó thành 1 rồi đi đến ô kế tiếp theo chiều ngược kim đồng hồ; nếu đứng trên ô mang số 1, nó đổi số đó thành 0 rồi đi đến ô cách một ô theo chiều ngược kim đồng hồ. Chứng minh rằng sau đủ nhiều thao tác, mỗi khi gà trống ở ô , nó đi đúng ba vòng quanh đường tròn rồi dừng lại ở , đồng thời mọi ô có cùng số như ngay trước ba vòng đó.
Bước 1 trên 8: Mã hóa các vòng và lần ghé ô
Phân tích chi tiết
Đánh số các ô theo chu kỳ là . Chia chuyển động vô hạn thành các vòng, mỗi vòng khi gà trống hoàn thành một lượt quanh đường tròn; gọi một ô là được dừng trong một vòng nếu gà trống tác động lên nó trong vòng đó, còn nếu không thì gọi là bị bỏ qua. Mỗi bước tiến một hoặc hai ô, nên gà trống dừng ở ít nhất một trong mọi hai ô liên tiếp.