*این پاسخ نادرست است. ضمن سپاس از @نابغه عزیز که به این موضوع در کامنتهای زیر پاسخ اشاره کردن، فقط برای این که ببینید به چه راحتی آدم میتونه یه پاسخ اشتباه بده اون رو نگه میدارم *

کافی است دقت کنیم در انتهای کار یک لامپ در صورتی روشن خواهد بود که در مجموع تعداد فردی از لامپهای هم سطر یا هم ستونش فشرده شده باشند.

روشن کردن همه لامپهای هر جدول n در n امکان پذیر هست. اگر همه لامپها را یک بار فشار دهیم (ببخشید لامپ را چطور فشار میدهند؟ به خصوص لامپ روشن!) چون هر لامپ هم سطر یا هم ستون تعداد فردی لامپ (از جمله خودش) است، همه لامپها روشن خواهند شد.

اما کمترین تعداد حرکات...

برای جدول ۱ در ۱ ، یک حرکت لازمه.

اگر جدول ۲ در ۲ بود، اون موقع در کمال تعجب لازم بود هر چهار لامپ رو فشار بدیم تا همه شون روشن بشن.

اما برای جدول ۳ در ۳ پنج حرکت کافیه: کافیه ۴ لامپ واقع در جدول ۲ در ۲ ی بالا سمت چپ رو فشار بدیم و آخر کار هم لامپ خانه پایین سمت راست جدول. مثل جدول زیر که هر عدد ۱ نشان دهنده فشردن لامپ هست:

0 1 1
0 1 1
1 0 0

اما برای حالات بزرگتر: فرض کنید موفق به این کار شدیم. تعداد لامپهای فشرده شده در هر سطر و هر ستون رو میشماریم، اگر تعداد زوجی از لامپهای یک سطر فشرده شده بود، اون سطر رو «زوج» و در غیر این صورت «فرد» مینامیم (و همین کار رو برای ستونها هم انجام میدیم). مثلا در جدول بالا سطر و ستونهای اول و دوم (از سمت چپ یا بالا) زوج هستند و سطر و ستون سوم فرد.

مسلما در خانه مشترک بین یک سطر و ستون زوج، عدد ۱ (لامپ فشرده شده) قرار داشته باشه، در غیر این صورت اون لامپ خاموش خواهد بود (چون مجموعا تعداد زوجی از لامپهای سطر و ستونش فشرده شده). به همین صورت در خانه مشترک بین یک سطر و ستون فرد هم باید عدد ۱ قرار گرفته باشه. نهایتا در خانه مشترک یک سطر فرد با ستون زوج، یا یک سطر زوج با ستون فرد باید عدد صفر بیاد.

از طرف دیگه اگر حتی یک سطر فرد داشته باشیم، باید تعداد فردی ستون فرد داشته باشیم (تا در سطر فرد تعداد فردی چراغ فشرده قرار بگیرند) و برعکس. چون تعداد سطر و ستونهای جدول زوج هست، در نتیجه تعداد فردی سطر و ستون زوج هم خواهیم داشت که این تناقض است (مثلا با داشتن تعداد فردی ستون زوج، در هر سطر زوج تعداد فردی لامپ فشرده شده قرار میگیرند).

لذا برای جدولهای زوج در زوج (مثلا ۱۰۰۰ در ۱۰۰۰) مجبوریم هیچ سطر یا ستون فردی نداشته باشیم و وقتی همه سطرها و ستونها زوج باشند، باید همه لامپها را فشار دهیم. لذا تنها جواب برای جدولهای زوج در زوج فشردن همه لامپها است.

=====

اگر تعداد سطر و ستونهای جدول فرد بود (مثلا ۱۰۰۱ در ۱۰۰۱) آن وقت $3n-4$ لامپ کافی بود. برای این کار کل خانه های دو سطر اول و ستون سمت راست، به جز سمت راست ترین خانه های دو سطر اول را می فشردیم.

0 1 1 1 1 1 ... 1 1 
0 1 1 1 1 1 ... 1 1
1 0 0 0 0 0 ... 0 0 
1 0 0 0 0 0 ... 0 0 
... 
1 0 0 0 0 0 ... 0 0