MathLabs

Bài 6

Có nn đèn L0,…,Ln−1L_0,\ldots,L_{n-1} trên một vòng tròn, trong đó n>1n>1 và Ln+k=LkL_{n+k}=L_k. Ở bước sis_i, nếu Li−1L_{i-1} sáng thì đổi trạng thái LiL_i, còn không thì không làm gì. Ban đầu mọi đèn đều sáng. Chứng minh (a) tồn tại số nguyên dương M(n)M(n) sao cho sau M(n)M(n) bước mọi đèn lại sáng; (b) nếu n=2kn=2^k, có thể lấy M(n)=n2−1M(n)=n^2-1; (c) nếu n=2k+1n=2^k+1, có thể lấy M(n)=n2−n+1M(n)=n^2-n+1.
Bước 1 trên 5: Mã hóa các đèn
Bước trướcBước tiếp
Hiểu nôm na

Cập nhật tuần tự khiến mỗi đèn phụ thuộc đèn trước đã cập nhật.

xi∈F2x_i\in\mathbb F_2
Phân tích chi tiết

Đặt xix_i là 1 khi LiL_i sáng và 0 khi tắt. Đổi trạng thái là cộng 1 trong trường hai phần tử. Sau một lượt đầy đủ, các giá trị mới thỏa y0=x0+xn−1y_0=x_0+x_{n-1} và yi=xi+yi−1y_i=x_i+y_{i-1} với ii từ 1 đến n−1n-1.