Cho hai số nguyên $n,k$ thỏa mãn $2⩽k<n$. Trong một lễ hội, có $n$ ngọn đèn được đặt trên một vòng tròn và đánh số $1,2,\dots ,n$ theo chiều kim đồng hồ. Mỗi ngọn đèn ở một trong hai trạng thái: sáng hoặc tắt.

Trong mỗi lượt ghi, trạng thái của các ngọn đèn được giữ cố định. Một người đi quanh vòng tròn theo chiều kim đồng hồ. Khi đứng tại ngọn đèn thứ $i$, người đó ghi lại số ngọn đèn đang sáng trong $k$ ngọn đèn liên tiếp theo chiều kim đồng hồ, bắt đầu từ ngọn đèn thứ $i$; sau ngọn đèn thứ $n$ lại đến ngọn đèn thứ 1. Gọi số ghi được tại ngọn đèn thứ $i$ là $s_i$. Sau một vòng, người đó thu được bản ghi $(s_1,s_2,\dots ,s_n)$.

a) Xác định điều kiện của $n,k$ để với mọi cách bố trí trạng thái của các ngọn đèn, bản ghi $(s_1,s_2,\dots ,s_n)$ xác định duy nhất cách bố trí đó.

b) Trong suốt lễ hội, trạng thái của các ngọn đèn có thể được thay đổi tùy ý giữa các lượt ghi. Xác định số bản ghi $(s_1,s_2,\dots ,s_n)$ phân biệt có thể thu được.

Lời giải (Lim Olympic - Nghệ An TST - P7).

Quy ước các chỉ số theo modulo $n$. Với mỗi cách bố trí $x=(x_1,x_2,\dots ,x_n)$, đặt $x_i=1$ nếu đèn thứ $i$ sáng và $x_i=0$ nếu đèn thứ $i$ tắt. Khi đó $s_i=x_i+x_{i+1}+\cdots +x_{i+k-1}$.

a) Ta chứng minh điều kiện cần và đủ là $\gcd (n,k)=1$.

Trước hết, giả sử $d=\gcd (n,k)>1$. Xét cấu hình $x$ trong đó đúng các đèn có chỉ số đồng dư 1 modulo $d$ sáng, và cấu hình $y$ trong đó đúng các đèn có chỉ số đồng dư 2 modulo $d$ sáng. Trong $k$ vị trí liên tiếp, mỗi lớp đồng dư modulo $d$ xuất hiện đúng $k/d$ lần. Vì thế cả hai cấu hình đều cho $s_i=k/d$ với mọi $i$. Hai cấu hình khác nhau nhưng có cùng bản ghi, nên ta loại trường hợp này.

Ngược lại, giả sử $\gcd (n,k)=1$. Từ bản ghi, ta có $s_{i+1}-s_i=x_{i+k}-x_i$. Do $\gcd (n,k)=1$, dãy chỉ số $1,1+k,1+2k,\dots ,1+(n-1)k$ modulo $n$ đi qua tất cả các vị trí. Bắt đầu từ $x_1$ và dùng liên tiếp các đẳng thức trên, ta biểu diễn được $x_i=x_1+C_i$ với mọi $i$, trong đó mỗi $C_i$ hoàn toàn được xác định bởi bản ghi.

Thay vào $s_1=x_1+x_2+\cdots +x_k$, ta được $k{x}_1+C=s_1$, trong đó $C=C_1+C_2+\cdots +C_k$ đã biết. Vì $k>0$, giá trị $x_1$ được xác định duy nhất nên $x_1,x_2,\dots ,x_n$ cũng được xác định duy nhất.

Vậy điều kiện cần và đủ là $\gcd (n,k)=1$.

b) Đặt $d=\gcd (n,k)$, viết $n=dm$ và $k=dq$. Xét hai cấu hình $x,y$ và đặt $c_i=x_i-y_i$. Hai cấu hình cho cùng bản ghi khi và chỉ khi $c_i+c_{i+1}+\cdots +c_{i+k-1}=0$ với mọi $i$. Trừ hai đẳng thức liên tiếp, ta được $c_{i+k}=c_i$ với mọi $i$. Do đó $c_i$ không đổi trên mỗi lớp đồng dư modulo $d$.

Gọi giá trị của hiệu trên lớp thứ $r$ là $c_r$. Vì mỗi đoạn gồm $k=dq$ vị trí liên tiếp chứa đúng $q$ phần tử thuộc mỗi lớp đồng dư modulo $d$, điều kiện tổng bằng 0 tương đương với $c_1+c_2+\cdots +c_d=0$. Ngược lại, điều kiện này cùng với việc hiệu không đổi trên mỗi lớp đồng dư cùng cho ta điều kiện đủ để hai cấu hình cho cùng bản ghi.

Giờ ta chia các ngọn đèn thành $d$ đường ray.

Với $1\le r\le d$, đặt $X_r=(x_r,x_{r+d},\dots ,x_{r+(m-1)d})\in \{0,1{\}}^m$ là đường ray thứ $r$. Nếu một đường ray của $x$ chứa cả 0 và 1 thì bắt buộc $c_r=0$, nên đường ray đó được giữ nguyên trong $y$. Một đường ray toàn 1 chỉ có thể được giữ nguyên hoặc đổi thành toàn 0; tương tự, một đường ray toàn 0 chỉ có thể được giữ nguyên hoặc đổi thành toàn 1.

Với mỗi cấu hình $x=(x_1,x_2,\dots ,x_n)$, gọi

$$\varphi (x)=\left\{y\in \{0,1{\}}^n:y\text{ cho cuˋng bản ghi với }x\right\}.$$

Như vậy, $\varphi (x)$ là lớp gồm tất cả các cấu hình cho cùng một bản ghi với $x$, còn $|\varphi (x)|$ là số cấu hình thuộc lớp đó. Giả sử $x$ có đúng $u$ đường ray toàn 1, $v$ đường ray toàn 0 và $d-u-v$ đường ray hỗn hợp (tức có cả 0 và 1). Để thu được một cấu hình $y\in \varphi (x)$, ta chọn $j$ trong $u$ đường ray toàn 1 để đổi thành toàn 0, đồng thời chọn đúng $j$ trong $v$ đường ray toàn 0 để đổi thành toàn 1. Các đường ray còn lại được giữ nguyên. Do đó theo Vandermonde ta có

$$|\varphi (x)|=\sum _{j=0}^{\min (u,v)}{C}_u^j{C}_v^j=C_{u+v}^u,$$

Ta gán cho mỗi cấu hình $x$ trọng số $\frac{1}{|\varphi (x)|}$. Xét một lớp $\mathcal{L}$ có đúng $h$ cấu hình. Với mọi $x\in \mathcal{L}$, ta có $\varphi (x)=\mathcal{L}$, nên $|\varphi (x)|=h$. Vì thế tổng trọng số của các cấu hình thuộc $\mathcal{L}$ bằng

$$\sum _{x\in \mathcal{L}}\frac{1}{|\varphi (x)|}=h\cdot \frac{1}{h}=1.$$

Do đó, khi cộng trên tất cả các cấu hình, mỗi lớp tương đương, hay mỗi bản ghi phân biệt, được tính đúng một lần. Bởi vậy $T=\sum _{x\in \{0,1{\}}^n}\frac{1}{|\varphi (x)|}$ là số bản ghi cần tính.

Số cấu hình $x$ đúng $u$ đường ray toàn 1 và $v$ đường ray toàn 0 là $\frac{d!}{u!v!(d-u-v)!}(2^m-2{)}^{d-u-v}$ nên

$$T=\sum _{\begin{array}{c}u,v\ge 0\\ u+v\le d\end{array}}\frac{d!}{u!v!(d-u-v)!}(2^m-2{)}^{d-u-v}\frac{u!v!}{(u+v)!}=\sum _{u+v=0}^d{C}_d^{u+v}(u+v+1)(2^m-2{)}^{d-u-v}$$

Kết hợp với việc $(u+v)C_d^{u+v}=d{C}_{d-1}^{u+v-1}$ ta suy ra được

$$T=(2^m-1{)}^d+d(2^m-1{)}^{d-1}=(2^m+d-1)(2^m-1{)}^{d-1},$$

trong đó $d=\gcd (n,k)$ và $m=n/d$.

Vậy số bản ghi phân biệt có thể thu được là $T=\left(2^{n/d}+d-1\right){\left(2^{n/d}-1\right)}^{d-1}$ với $d=\gcd (n,k)$.