Câu hỏi 17
(NET 2; IMO 6) Cho $n$ là một số nguyên lớn hơn $1$. Xếp thành vòng tròn $n$ bóng đèn $L_0,\ldots,L_{n-1}$, mỗi bóng có thể BẬT hoặc TẮT, ban đầu tất cả đèn đều BẬT, rồi thực hiện một dãy bước $\mathrm{Step}_0,\mathrm{Step}_1,\ldots$. Nếu $L_{j-1}$ ($j$ được lấy theo môđun $n$) đang BẬT, thì $\mathrm{Step}_j$ đổi trạng thái của $L_j$ (từ BẬT sang TẮT hoặc từ TẮT sang BẬT) nhưng không đổi trạng thái của bất kỳ đèn nào khác. Nếu $L_{j-1}$ đang TẮT thì $\mathrm{Step}_j$ không thay đổi gì. Chứng minh rằng:
(a) Có số nguyên dương $M(n)$ sao cho sau $M(n)$ bước mọi đèn lại BẬT.
(b) Nếu $n$ có dạng $2^k$ thì mọi đèn đều BẬT sau $n^2-1$ bước.
(c) Nếu $n$ có dạng $2^k+1$ thì mọi đèn đều BẬT sau $n^2-n+1$ bước.
(a) Có số nguyên dương $M(n)$ sao cho sau $M(n)$ bước mọi đèn lại BẬT.
(b) Nếu $n$ có dạng $2^k$ thì mọi đèn đều BẬT sau $n^2-1$ bước.
(c) Nếu $n$ có dạng $2^k+1$ thì mọi đèn đều BẬT sau $n^2-n+1$ bước.