0

At first all bulbs were on. At each touch the state of bulbs in that row and column is changed. If it is off the after touch it is on and if it is on then after touch it is on.

Find the minimum number of touches to off all the bulbs?

I am able to prove that the minimum number of touches if $n$ is odd is $n $. If one touches all the bulbs in top row then in that row there will be odd number of touches so all bulbs in that row will be off and as each column is touched one time bulbs win each column will also be off. But when $n $ is even the minimum number of touches is $n^2$. But i can't prove it

KReiser
  • 65,137
  • 1
    Please state the rules carefully. Presumably if you touch any bulb you change the state of all the bulbs in that row and column. If you just turn them off, you can turn off all the bulbs by touching each one in the first row, so $n$ touches suffice for any $n$. Also you should say the starting condition is all on. There is an edit button at the bottom of the question. – Ross Millikan Feb 07 '20 at 04:41
  • Can you show how to do it for n=3? – lalala Feb 07 '20 at 05:18
  • 1
    @lalala: touch every bulb in the top (or any) row (or column). This works for odd $n$. The bulbs in the top row flip $n$ times and each other bulb flips once. – Ross Millikan Feb 07 '20 at 05:26
  • Same for $n=3$ if 1st bulbe in top row touched bulbes in 1st row and 1st column is off. Then if one he touches 2nd bulbe in top row bulbes in top row is on but the bulbes in that column except that bulb is off. Then if he touches the third bulbe in that row then all the bulbes in that row is off and all bulbes in 3rd column is also iff. Hence all bulbes in that board is off –  Feb 07 '20 at 05:40

1 Answers1

2

For even $n$, for each bulb $B$ consider the parity of the number of bulbs that are on among the bulbs that change state when you touch $B$. Originally this parity is odd, in the end it should be even, and it only changes when you touch $B$. Thus you need to touch each bulb at least once.

joriki
  • 238,052
  • I did not understand what you said can you please explain it more –  Feb 07 '20 at 06:31
  • @SohamChatterjee: That will be more efficient if you tell me which part(s) you didn't understand. – joriki Feb 07 '20 at 06:36
  • What is B first of all –  Feb 07 '20 at 06:51
  • And how you are concluding that to change the parity of bulbes odd to even I need to touch all bulbes –  Feb 07 '20 at 06:53
  • @SohamChatterjee: $B$ is introduced by the phrase "for each bulb $B$". The parity argument is: The parity for each bulb only changes if you touch that bulb. The parity for each bulb has to change. Thus you have to touch each bulb. – joriki Feb 07 '20 at 07:04
  • 1
    @SohamChatterjee: Consider any bulb $B$. Touching it changes $2n-1$ bulbs (itself included). Let's call this bulb set $B^$. If you touch any bulb $X$ not in $B^$, it will switch exactly 2 bulbs in $B^$ (where the row of $X$ meets the column of $B$ and where the column of $X$ meets the row of $B$). If you touch any bulb in the row of $B$ (but not $B$ itself), it will switch exactly $n$ (an even number) of bulbs in $B^$ (namely the row $B$ is in). An analog arguments works for a bulb in the column of $B$ (but again, not $B$ itself) . – Ingix Feb 07 '20 at 09:22
  • 1
    So in all cases except touching $B$, the number of changed bulbs is even. That's the parity conserving argument: If you start with an odd number of bulbs on in $B^*$ (which you do), touching any bulb but $B$ keeps that number odd. Since in the end you want a configuration that has that number even ($0$), you must touch bulb $B$ at some time. – Ingix Feb 07 '20 at 09:22