Chủ đề này có 2 trả lời

[reddevil1998]

Đây là một bài toán đã lâu nhưng phải công nhận là rất hay , bài này mình vừa mới làm được hôm trước với một lời giải rất đẹp(nếu bạn nào muốn biết thì mình sẽ post lên (khá dài đấy))

Bài toán:Cho $n>1$ nguyên .Cho một dãy $n$ đèn $L_{0},L_{1},...,L_{n}$ chúng có thể tắt hoặc bật, ta thực hiện một dãy hành động với Bước $1$ , Bước $2$ ,...thỏa mãn nếu $L_{j-1}$ ($j$ lấy theo mod $n$) được bật thì bước $j$ đổi trạng thái $L_{j}$(Bật thành tắt và ngược lại).Nếu $L_{j-1}$ tắt thì ở bước $j$ trạng thái các đèn không thay đổi.CM

1.Tồn tại $M(n)$ nguyên dương sao cho sau $M(n)$ bước thì tất cả các đèn bật.

2.Với $n=2^{k}$ , Cm các đèn bật sau $n^{2}-1$ bước.

3.Với $n=2^{k}+1$.Cm các đèn bật sau $n^{2}-n+1$ bước.

[quocbaolqd11]

câu a mình có 1 cách làm rất thủ công .
Đầu tiên có nhận xét là không thể đưa về cấu hình (0,0,...,0) với 0 thay cho đèn tắt và 1 thay cho đèn bật.
khi đó để tất cả đèn bật thì ta phải đưa về cấu hình sao cho chỉ có duy nhất 1 số 1 trong dãy.
Ta sẽ chỉ ra sau 1 số bước thì nó sẽ về cấu hình trên.
gọi $a_i$ là vị trí của số 1 thứ i trong dãy. Ta có: số số 1 được thêm vào trong bảng là $a_2-a_1$ số 1 nếu $a_2>a_1+1$ và giảm 1 nếu $a_2=a_1+1$.  Tiếp tục như vậy với các bộ kia. Sau khi thực hiện qua bước $n+1$ (tức là thực hiện 1 vòng mới) thì khi đó bộ $a_2-a_1$ số 1 đầu tiên $(1,1,...,1)$ sẽ giảm còn 1 nửa nếu số các số 1 trong khoảng $a_2-a_1$ số đó chẵn và $[\frac{(a_2-a_1)}{2}]+1$ nếu $(1,1,1,1,1,...)$ lẻ. Với TH lẻ thì số cuối cùng không bị đổi nên qua các bước sẽ biến tất cả các số 0 đứng sau nó thành số 1 và sẽ dừng sau khi biến đổi số 1 thành số 0 (số 1 ở đây là số 1 đầu tiên giữa 2 bộ $a_2-a_1$ với bộ $a_3-a_2$). Tiếp tục biến đổi thì bộ $(1,0,1,0,...,1,0,1,1,1,1,...)$ sẽ dần thành bộ $(1,0,0,...,0,1,0,1,0,...)$ (được như vậy là do sau khi thực hiện với $n+1$ bước đầu, ta quay lại làm hết từ đầu)  mà có 1 số chẵn cặp $1,0$, từ 1 bộ chẵn $1,0$ đó biến đổi tiếp thành được bộ $(1,1,0,0,0,0,...)$ và từ đó số số 1 giảm đi so với ban đầu. Vậy nên áp dụng nhiều lần như vậy, ta sẽ đưa về được Th chỉ có 1 số 1 trong cấu hình.
Thực ra thì dài nữa, nhưng mà thấy trâu quá nên viết vậy thôi ...
câu b, câu c hơi thâm thúy nên chưa nghĩ ra (bạn post lời giải của bạn lên được không ?).

 

Bài viết đã được chỉnh sửa nội dung bởi quocbaolqd11: 10-12-2013 - 22:52

[reddevil1998]

Uk , mình cũng mã hoá các trạng thái bật tắt như bạn là một xâu nhị phân , Ta Cm sau $n^{2}-1$ bước thì ta sẽ đạt được một dãy toàn $1$

Vì các phần tử của dãy nhị phân chỉ là $1,0$ nên ý tưởng tự nhiên là ta sẽ xét mod $2$

Goi $K_{i}$ là trạng thái dãy sau $i$ bước

$K_{i,j}$ là giá trị của đèn j ở trạng thái i$K_{n-1,j}$

Ta có CTTH của dãy $K_{i,1}$ theo mod 2$K_{i+1,1}=K_{i,0}+K_{i,1}$

Quy nạp lên ta có CTTH của $K_{i,j}$ theo mod 2 là $K_{i,j}=\sum_{t=0}^{j}K_{i,t}$

Ta xét hàm sinh của dãy $F(y)=\sum_{i=0}^{\propto }K_{i,j}y^{i}=\sum_{i=0}^{\propto }\sum_{t=0}^{j}K_{i,t}y^{i}=\frac{1}{(1-y)^{i+1}}=\sum_{i=0}^{\propto }\binom{i+j}{i}y^{i}$

Vậy ta có CTTQ của dãy $K_{i,j}=\binom{i+j}{i}$

Xét $K_{n-1,j}$$=\binom{n-1+j}{n-1}=\binom{2^{k}-1+j}{2^{k}-1} (j=1,2,...,n-1)$

với i=1,2,..,n-1 thì theo dịnh lí Lucas , ta có $K_{n-1,j}\equiv 0(mod 2)$ nên gt các đèn ở các vị trí 1,2,...,n-1 (lấy theo mod n) là 0 , còn đèn ở vị trí 0 ( theo mod n) là 1 sau $n(n-1)$ bước , còn bước cuối cùng ta chỉ việc thực hiện phép biến đổi $(1,0)\rightarrow (1,1)$ là ta có một dãy toàn 1

Câu c thì tương từ chú ý ta có biểu diễn cơ số của j theo mod 2 là $j=2^{a_{1}}+2^{a_{2}}+...+2^{a_{p}}$ , nếu xét 0<j<n-1hì ta lại dùng Lucas như trên thôi , các bạn tự nghĩ nốt nhé

Bài viết đã được chỉnh sửa nội dung bởi reddevil1998: 11-12-2013 - 14:23