Câu hỏi 3
Cho $n\geq3$ là một số nguyên. Có $n$ ô nằm trên một đường tròn và mỗi ô được gán số $0$ hoặc $1$. Một con gà trống đứng trên một trong các ô đó và lặp lại các thao tác sau:
- Nếu con gà trống đứng trên một ô mang số $0$, nó đổi số của ô đó thành $1$ rồi chuyển sang ô kế tiếp theo chiều ngược kim đồng hồ.
- Nếu con gà trống đứng trên một ô mang số $1$, nó đổi số của ô đó thành $0$ rồi chuyển tới ô cách hai ô theo chiều ngược kim đồng hồ (tức ô sau ô kế tiếp).
Chứng minh rằng sau đủ nhiều thao tác, mệnh đề sau luôn đúng:
Nếu con gà trống đang ở ô $C$, thì nó sẽ đi quanh đường tròn đúng ba vòng rồi dừng lại tại $C$. Hơn nữa, mọi ô sẽ mang đúng số mà nó đã mang ngay trước khi con gà trống bắt đầu đi ba vòng đó.
- Nếu con gà trống đứng trên một ô mang số $0$, nó đổi số của ô đó thành $1$ rồi chuyển sang ô kế tiếp theo chiều ngược kim đồng hồ.
- Nếu con gà trống đứng trên một ô mang số $1$, nó đổi số của ô đó thành $0$ rồi chuyển tới ô cách hai ô theo chiều ngược kim đồng hồ (tức ô sau ô kế tiếp).
Chứng minh rằng sau đủ nhiều thao tác, mệnh đề sau luôn đúng:
Nếu con gà trống đang ở ô $C$, thì nó sẽ đi quanh đường tròn đúng ba vòng rồi dừng lại tại $C$. Hơn nữa, mọi ô sẽ mang đúng số mà nó đã mang ngay trước khi con gà trống bắt đầu đi ba vòng đó.