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 3 trên 5: Chứng minh sự trở lại tổng quát
Bước trướcBước tiếp
Hiểu nôm na

Tính đảo trên quỹ đạo toàn sáng cho phần (a), dù không cần nghịch đảo mọi trạng thái.

Tr(u)=u for some r>0,u=(1,…,1)T^r(u)=u\text{ for some }r>0,\quad u=(1,\ldots,1)
Phân tích chi tiết

Áp dụng đệ quy ngược cho quỹ đạo bắt đầu từ vectơ toàn 1. Cùng phép tính tổng tiền tố dựng lại duy nhất trạng thái trước trên quỹ đạo ở mỗi vòng; do đó quỹ đạo là chu kỳ, không phải đoạn quá độ. Vì chỉ có hữu hạn trạng thái, một r dương đưa về u, cho M(n)=nr cộng phần lượt dở dang thích hợp.