برای حل دقیق این مسئله، بیایم شبکه رو به صورت یک گراف $G = P_2 \times P_n$ در نظر بگیریم که تو اون وضعیت لامپها با یک بردار باینری $x$ در میدان $GF(2)$ نشون داده میشه. هدف ما پیدا کردن برداریه که تو معادلهٔ ماتریسی $(A+I)x = \mathbf{1}$ صدق کنه و کمترین وزن همینگ (تعداد ۱ها) رو داشته باشه. ماتریس سیستم رو میتونیم به صورت بلوکی بنویسیم که تو اون $B = L_n + I_n$ بلوکهای اصلی هستن و $L_n$ ماتریس مجاورت گراف مسیر $P_n$ هست. اگه بردار $x$ رو به دو بخش $u$ (سطر بالا) و $v$ (سطر پایین) تقسیم کنیم، به دستگاه معادلاتی میرسیم که با جمع کردنشون نتیجه میده $L_n(u+v) = 0$. این یعنی جمع دو سطر باید عضوی از هستهٔ ماتریس $L_n$ باشه. نکتهٔ کلیدی اینجاست که رفتار ماتریس $L_n$ روی میدان $GF(2)$ کاملاً به زوج یا فرد بودن $n$ بستگی داره و همین باعث ایجاد الگوهای متفاوت میشه.
اگه $n$ فرد باشه، ماتریس $L_n$ وارونپذیر نیست و هستهش شامل بردار $k = (1, 0, 1, 0, \dots, 1)^T$ میشه. تو این حالت برای اینکه معادله جواب داشته باشه، مجبوریم از این بردار هسته استفاده کنیم که باعث میشه تقارن بین سطر بالا و پایین از بین بره (یعنی $u \neq v$). با حل معادلات برای این حالت، متوجه میشیم که کمترین تعداد حرکت لازم دقیقاً برابر با تعداد ستونهای فرده. بنابراین برای تمام $n$های فرد، فرمول نهایی خیلی ساده به دست میاد:
$$ a_n = \frac{n+1}{2} $$
این فرمول برای $n=1$ مقدار ۱، برای $n=3$ مقدار ۲ و برای $n=5$ مقدار ۳ رو میده که دقیقاً با آزمایشهای شما همخوانی داره.
اما اگه $n$ زوج باشه، ماتریس $L_n$ وارونپذیره و تنها جواب معادلهٔ همگن صفره، پس حتماً باید $u=v$ باشه؛ یعنی الگوی لمس لامپها تو سطر بالا و پایین کاملاً متقارنه. تو این حالت مسئله تبدیل میشه به حل $L_n u = \mathbf{1}$. با بررسی ساختار بازگشتی جوابها، رفتار بر اساس باقیماندهٔ $n$ به پیمانهٔ ۴ مشخص میشه. اگه $n$ مضرب ۴ باشه (مثل $n=4$)، جواب به صورت یکدرمیان $(0, 1, 0, 1, \dots)$ خواهد بود و تعداد کل حرکتها دقیقاً برابر با $n$ میشه. اما اگه $n$ زوج باشه ولی مضرب ۴ نباشه (یعنی $n \equiv 2 \pmod 4$ مثل $n=2$ یا $n=6$)، ساختار جواب کمی تغییر میکنه و تعداد کل حرکتها برابر با $n+2$ خواهد شد. پس بهطور خلاصه برای $n$های زوج فرمولهای زیر رو داریم:
$$ a_n = \begin{cases} n & \text{if } n \equiv 0 \pmod 4 \\ n+2 & \text{if } n \equiv 2 \pmod 4 \end{cases} $$
این با دادههای شما هم مطابقه؛ مثلاً برای $n=2$ مقدار ۴ و برای $n=4$ هم مقدار ۴ رو نتیجه میده.
