Một bài toán phức tạp
Có $n$ ngọn đèn $L_{0},L_{1},...,L_{n-1}(n>1)$ được đặt trên $1$ đường tròn.Ta dùng $L_{n+k}$ đẻ chỉ $L_{k}$.Ở mọi thời điểm,mỗi đèn có thể sáng hoặc bị tắt.Ban đầu tất cả đều sáng
Ta biểu thị các bước $s_0,s_1,...$ như sau :tại bước $s_i$ nếu $L_{i-1}$ đang tắt thì ta đổi chiều trạng thái của $L_i$ còn nếu $L_{i-1}$ đang sáng thì không làm gì cả
CMR
- Tồn tại số nguyên dương $M(n)$ sao cho sau $M(n)$ bước thì tất cả đèn đều sáng
- Nếu $n=2^k$ thì ta có thể chọn $M(n)=n^2-1$
- Nếu $n=2^{k+1}$ ta có thể chọn $M(n)=n^2-n+1$
Bài viết đã được chỉnh sửa nội dung bởi barcavodich: 02-06-2013 - 22:30