Một dàn đèn LED dạng lưới tam giác đều $ABC$ có cạnh bằng $n$ (với $n\in {\mathbb{N}}^{\ast },n⋮4$) được chia thành các tam giác đều có cạnh bằng 1, mỗi nút của lưới có một bóng đèn (tham khảo hình vẽ). Mỗi đèn có hai trạng thái: bật và tắt. Ban đầu, tất cả các đèn đều ở trạng thái tắt. Kí hiệu $X_i,Y_j,Z_i$ là các đường thẳng lần lượt song song hoặc trùng với $BC$, $AB$, $AC$ chứa đúng $i$ đèn $(i=1,2,\dots ,n+1)$. Với mỗi thao tác, người ta tác động vào một trong các đường thẳng $X_i,Y_j,Z_k$ làm cho trạng thái của tất cả các đèn nằm trên đó thay đổi: đèn đang tắt sẽ bật, đèn đang bật sẽ tắt.
a) Chứng minh rằng điều kiện cần và đủ để ba đường thẳng $X_i,Y_j,Z_k$ cùng đi qua một đèn là $i+j+k=2n+3$.
b) Từ trạng thái ban đầu, hãy chỉ ra một dãy thao tác trong đó số lần tác động vào mỗi đường thẳng $X_i,Y_j,Z_k$ nhiều nhất bằng 1, đồng thời mỗi nhóm $(X_1,\dots ,X_{n+1}),(Y_1,\dots ,Y_{n+1})$ và $(Z_1,\dots ,Z_{n+1})$ đều có ít nhất một đường thẳng được tác động, để sau dãy thao tác này tất cả các đèn đều tắt.
c) Với mỗi trạng thái $H$ có thể xảy ra của dàn đèn LED, gọi $s(H)$ là số thao tác ít nhất cần thực hiện để tạo ra $H$ từ trạng thái ban đầu. Tìm giá trị lớn nhất của $s(H)$.

a) Gọi khoảng cách từ vị trí đèn led $P$ bất kì đến ba cạnh $AB,AC,BC$ lần lượt là $d_{AB}(P),d_{AC}(P),d_{BC}(P)$.
*) Chứng minh chiều thuận:
Giả sử ba đường thẳng $X_i,Y_j,Z_k$ cùng đi qua một đèn led $P$. Ta có
$$d_{BC}(P)=\frac{\sqrt{3}}{2}(n+1-i);d_{AB}(P)=\frac{\sqrt{3}}{2}(n+1-j);d_{AC}(P)=\frac{\sqrt{3}}{2}(n+1-k).$$
Mà tổng khoảng cách từ một điểm nằm trên lưới tới ba cạnh của tam giác luôn bằng $n\frac{\sqrt{3}}{2}$. Từ đó suy ra
$$\frac{\sqrt{3}}{2}(n+1-i)+\frac{\sqrt{3}}{2}(n+1-j)+\frac{\sqrt{3}}{2}(n+1-k)=n\frac{\sqrt{3}}{2}\iff i+j+k=2n+3$$
*) Chứng minh chiều đảo:
Giả sử có ba chỉ số $i,j,k\in \{1,2,\dots ,n+1\}$ thỏa mãn $i+j+k=2n+3$.
Xét hai đường thẳng $X_i$ và $Y_j$ cắt nhau tại duy nhất một điểm $P$.
$$d_{BC}(P)=(n+1-i)\frac{\sqrt{3}}{2};d_{AB}(P)=(n+1-j)\frac{\sqrt{3}}{2}$$
$$k\le n+1\Rightarrow (i+j)\ge n+2\Rightarrow d_{BC}(P)+d_{AB}(P)=\left(2n+2-(i+j)\right)\frac{\sqrt{3}}{2}\le n\frac{\sqrt{3}}{2}$$
Suy ra điểm $P$ nằm trên lưới tam giác đều. Khi đó:
$$d_{AC}(P)=n\frac{\sqrt{3}}{2}-(n+1-i)\frac{\sqrt{3}}{2}-(n+1-j)\frac{\sqrt{3}}{2}=(i+j-n-2)\frac{\sqrt{3}}{2}$$
$$=\left[(2n+3-k)-n-2\right]\frac{\sqrt{3}}{2}=(n+1-k)\frac{\sqrt{3}}{2}.$$
Suy ra $P$ nằm trên đường thẳng $Z_k$. Do đó, $X_i,Y_j,Z_k$ đồng quy tại đúng một đèn led $P$.

b) Ta chỉ ra một dãy thao tác thỏa mãn là tác động vào tất cả các đường $X_{2m},Y_{2m},Z_{2m}$ với $1\le 2m\le n+1$ và không tác động vào các đường còn lại.
Khi đó với mỗi đèn $P$ bất kì tồn tại duy nhất bộ ba đường thẳng $X_i,Y_j,Z_k$ cùng đi qua $P$ thỏa mãn $i+j+k=2n+3$. Do $2n+3$ là số lẻ, nên trong ba số $i,j,k$ có 2 số chẵn, 1 số lẻ hoặc 3 số lẻ. Theo cách thao tác ở trên, thì đèn $P$ được tác động đúng hai lần hoặc không được tác động lần nào. Do đó trạng thái đèn $P$ vẫn là tắt.

c) Do ta cần tìm số lần tác động ít nhất và nếu ta tác động hai lần trên cùng một đường thẳng thì trạng thái của các đèn không thay đổi nên ta có thể biểu diễn tất cả các tổ hợp thao tác dưới dạng bộ
$$\left(a_1,a_2,\dots ,a_{n+1},b_1,b_2,\dots ,b_{n+1},c_1,c_2,\dots ,c_{n+1}\right),$$
trong đó mỗi phần tử $a_i,b_i,c_i$ tương ứng với thao tác được thực hiện trên các đường thẳng $X_i,Y_i,Z_i$; nhận giá trị 0 (không được tác động) hoặc 1 (được tác động).
Gọi $A$ là tập hợp tất cả các bộ $\left(a_1,a_2,\dots ,a_{n+1},b_1,b_2,\dots ,b_{n+1},c_1,c_2,\dots ,c_{n+1}\right)$. Khi đó $|A|=2^{3n+3}$.
Gọi $B$ là tập hợp tất cả các trạng thái của dàn đèn LED, trong đó mỗi trạng thái của dàn đèn LED trong $B$ được mô tả bằng một bộ $N=\frac{(n+1)(n+2)}{2}$ phần tử $\left(d_1,d_2,\dots ,d_N\right)$, trong đó mỗi phần tử bằng 0 hoặc 1 (tương ứng đèn tắt hoặc bật).
Xét ánh xạ $f:A\to B$ với $f(x)$ là phần tử thuộc $B$ thu được sau khi thực hiện $x$. Từ đây, ta quy ước phép cộng hai phần tử trong $A$ hoặc trong $B$ được tính trên từng cặp số ở vị trí tương ứng của hai phần tử đó và được tính theo modulo 2 (tức là $1+1=0+0=0$, $0+1=1+0=1$).
Ta thấy $f(x+x^{\prime })=f(x)+f(x^{\prime })$ với mọi $x,x^{\prime }\in A$.
*) Gọi $K$ là tập hợp tất cả các $x\in A$ sao cho $f(x)$ là trạng thái tất cả các đèn đều tắt. Dễ thấy tám phần tử sau đây thuộc $K$:
$$((0,0,\dots ,0),(0,0,\dots ,0),(0,0,\dots ,0))=\mathrm{id}$$
$$((0,0,\dots ,0),(1,1,\dots ,1),(1,1,\dots ,1))=a$$
$$((1,1,\dots ,1),(1,1,\dots ,1),(0,0,\dots ,0))=b$$
$$((1,1,\dots ,1),(0,0,\dots ,0),(1,1,\dots ,1))=a+b$$
$$((0,1,0,1,\dots ),(0,1,0,1,\dots ),(0,1,0,1,\dots ))=c$$
$$((0,1,0,1,\dots ),(1,0,1,0,\dots ),(1,0,1,0,\dots ))=a+c$$
$$((1,0,1,0,\dots ),(1,0,1,0,\dots ),(0,1,0,1,\dots ))=b+c$$
$$((1,0,1,0,\dots ),(0,1,0,1,\dots ),(1,0,1,0,\dots ))=a+b+c$$
Ta sẽ chứng minh tập $K$ có đúng 8 phần tử.
Giả sử $L=((a_1,a_2,\dots ,a_{n+1}),(b_1,b_2,\dots ,b_{n+1}),(c_1,c_2,\dots ,c_{n+1}))$ thuộc $K$.
Khi đó $a_i+b_j+c_k=0$ với $i+j+k=2n+3$. Bằng cách cộng thêm $a$ hoặc $b$ nếu cần thiết, ta có thể giả sử rằng $b_{n+1}=c_{n+1}=0$. Vì $a_2+b_n+c_{n+1}=a_2+b_{n+1}+c_n=0$, ta có $b_n=c_n$. Có hai trường hợp:
(a) $b_n=c_n=0$. Khi đó từ $a_3+b_{n-1}+c_{n+1}=a_3+b_n+c_n=a_3+b_{n+1}+c_{n-1}$, suy ra $b_{n-1}=c_{n-1}=0$. Tương tự ta thấy tất cả các phần tử $b_i$ và $c_i$ đều bằng 0, từ đó suy ra $L=\mathrm{id}$.
(b) $b_n=c_n=1$. Khi đó từ $a_3+b_{n-1}+c_{n+1}=a_3+b_n+c_n=a_3+b_{n+1}+c_{n-1}$, suy ra $b_{n-1}=c_{n-1}=0$. Làm tương tự ta thu được $(b_1,b_2,\dots ,b_{n+1})=(c_1,c_2,\dots ,c_{n+1})=(\dots ,1,0,1,0)$, từ đó suy ra $L=c$ hoặc $L=a+c$.
Do đó $L$ là một trong tám phần tử được liệt kê ở trên.
Như vậy, với mỗi $x\in A$ tồn tại đúng 7 phần tử $x^{\prime }$ khác thuộc tập $A$ thỏa mãn $f(x)=f(x^{\prime })$. Do đó, ta có thể phân hoạch $2^{3(n+1)}$ phần tử của $A$ thành $2^{3n}$ tập con, mỗi tập tương ứng duy nhất với một phần tử của $B$.
*) Xét mỗi tập con $S$ chứa 8 phần tử như trên:
Với mỗi phần tử $x\in S$, gọi $x_1$ là số lượng các phần tử $a_1,a_3,\dots$ bằng 1, và gọi $x_2$ là số lượng các phần tử $a_2,a_4,\dots$ bằng 1. Định nghĩa tương tự $y_1,y_2,z_1,z_2$ cho dãy $b_i$ và $c_i$. Khi đó, số thao tác tương ứng $x$ là
$$T(x)=x_1+x_2+y_1+y_2+z_1+z_2.$$
Đặt $n=4k$. Xét $x\in S$ để $T(x)$ đạt giá trị nhỏ nhất.
Dễ thấy $x+a,x+b,x+c,x+(a+b),x+(a+c),x+(b+c),x+(a+b+c)\in S$.
Ta có:
$$T(x+a)=x_1+x_2+(n+1-y_1-y_2)+(n+1-z_1-z_2)\ge T(x)=x_1+x_2+y_1+y_2+z_1+z_2$$
$$\Rightarrow n+1\ge y_1+y_2+z_1+z_2.$$
Làm tương tự ta có: $x_1+x_2+z_1+z_2\le n+1$; $x_1+x_2+y_1+y_2\le n+1$;
$$x_2+y_2+z_2\le 3k;(1)$$
$$x_1+y_1+z_2\le 3k+1;x_2+y_1+z_1\le 3k+1;x_1+y_2+z_1\le 3k+1(2)$$
Cộng vế với vế của bốn bất đẳng thức trong (1), (2) rồi chia cho 4, ta được $T\le 6k+1$.
Dấu "=" xảy ra khi $x_1=x_2=y_1=y_2=z_2=k$ và $z_1=k+1$.