Câu hỏi 84
Một hàng đèn $n$ được dán nhãn từ trái sang phải với các số $1$ đến $n$, trong đó $n$ là một số nguyên * lẻ *. Mỗi đèn có một công tắc, nếu được nhấn, sẽ chuyển nó từ TẮT sang BẬT hoặc BẬT sang TẮT; Tuy nhiên, các công tắc chỉ có thể được nhấn theo các quy tắc sau: Công tắc
(a) 1 có thể được nhấn bất cứ lúc nào;
(b) Công tắc $k \in \{2, \dots, n\}$ có thể được nhấn nếu và chỉ khi đèn $(k-1)$ đang bật và tất cả các đèn $l \lt (k-1)$ (nếu có) đều tắt. Ban đầu tất cả các đèn đều sáng. Chứng minh rằng số lần tối thiểu các công tắc phải được nhấn để tắt tất cả các đèn là $$
\frac{2^{n+1} - 1}{3}
$$
(a) 1 có thể được nhấn bất cứ lúc nào;
(b) Công tắc $k \in \{2, \dots, n\}$ có thể được nhấn nếu và chỉ khi đèn $(k-1)$ đang bật và tất cả các đèn $l \lt (k-1)$ (nếu có) đều tắt. Ban đầu tất cả các đèn đều sáng. Chứng minh rằng số lần tối thiểu các công tắc phải được nhấn để tắt tất cả các đèn là $$
\frac{2^{n+1} - 1}{3}
$$