There are lamps in every field of $n\times n$ table. At start all the lamps are off. A move consists of chosing $m$ consecutive fields in a row or a column and changing the status of that $m$ lamps. Prove that you can reach a state in which all the lamps are on only if $m$ divides $n.$
Problem
Source:
Tags: analytic geometry, combinatorics unsolved, combinatorics
13.04.2011 00:06
restore it please
18.04.2011 21:32
Here's something which I think works. Let $S$ denote the set of numbers between $1$ and $n$ congruent to either $0$ or $1$ mod $m$. Number the rows and columns of the table from $1$ to $n$, and let $T$ denote those lamps both of whose coordinates are in $S$. If a row or column is not in $S$, a set of $m$ consecutive lamps in that row/column does not intersect $T$ at all. Otherwise, it intersects $T$ in exactly two places. It follows that switching $m$ consecutive lamps does not change the parity of the number of lamps in $T$ which are on. Since we start with all lamps on, after every step we must have an even number of lamps in $T$ which are on. But $|S|$ is odd so long as $m$ does not divide $n$, since in that case there is one more number congruent to $1$ mod $m$ than there is congruent to $0$ mod $m$ in $\{1, 2, \dots, n\}$. It follows that $|T|=|S|^2$ is also odd. So it's impossible for all the lamps in $T$ to be on at any time. This may be clearer with a picture, so here's the situation with $m=4$ and $n=6$. Note that any $4$ consecutive squares contain either no $T$'s or $2$ of them. TxxTTx xxxxxx xxxxxx TxxTTx TxxTTx xxxxxx
25.04.2014 19:21
It is trivial that if $m|n$ we can turn all the lamps on.Now,suposse that $m$ doesn't divide $n$.We can set colons from $1$ to $n$.We also do that for rows.In every field we put a number equal to $i+j-1 (mod m)$ ,where $i$ is the number of the row and $j$ is the number of the colon of the field.Let a field be $k$ type if number $k$ is written in it.Now in each move we change the status of all different types of lamps.Because $m$ doesn't divide $n$ there exists number $q$ such that $q*m<n<(q+1)*m$.That means that there will be $q$ "0" type lamps and $q+1$ "1" type lamps.Now suposse that we can turn on all the lamps.That would mean that the difference between the number of the turned off "0" type lamps and turned off "1" type lamps be $0$.At the beggining their difference is $1$.Notice that the difference in every move changes as:$+2$,$+0$,$-2$.That means that their difference will always be odd and because $0$ is even it is a contradiction,so if $m$ doesn't divide $n$ we can't turn all the lights on.