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 5 trên 5: Tính trường hợp hơn lũy thừa của 2 một đơn vị
Bước trướcBước tiếp
Hiểu nôm na

Thêm một tọa độ làm số triệt tiêu thay đổi đúng n-2.

n=2k+1⟹M(n)=n2−n+1n=2^k+1\Longrightarrow M(n)=n^2-n+1
Phân tích chi tiết

Cùng đệ quy đó, nay có thêm một tọa độ vòng nên hai đầu chồng lên nhau một lần. Phép bình phương lặp lại để lại đúng n^2-n+1 bước trên trạng thái toàn 1, sau đó mọi bit lại bằng 1. Điều này chứng minh cận thứ hai.