rilarfer wrote: Grid the plane forming an infinite board. In each cell of this board, there is a lamp, initially turned off. A permitted operation consists of selecting a square of \(3\times 3\), \(4\times 4\), or \(5\times 5\) cells and changing the state of all lamps in that square (those that are off become on, and those that are on become off). (a) Prove that for any finite set of lamps, it is possible to achieve, through a finite sequence of permitted operations, that those are the only lamps turned on on the board. (b) Prove that if in a sequence of permitted operations only two out of the three square sizes are used, then it is impossible to achieve that at the end the only lamps turned on on the board are those in a \(2\times 2\) square. $\color{blue}\boxed{\textbf{a) Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ With the $4\times 4$ we can change the state to a $4\times 12$ and with the $3\times 3$ we can make a $1\times 12$ change state without altering the other cells. With the $5\times 5$ you can change the state to a $10\times 15$ and with the $3\times 3$ we can make a $1\times 15$ change state without altering the other cells Now removing the $1\times 12$ from $1\times 15$ we obtain that we can change the state to a $1\times 3$ without altering the other cells Now removing these $1\times 3$ to $4\times 4$ we obtain that we can change the state of a cell without changing the state of other cells Note that this is enough to prove the statement$_\blacksquare$ $\color{blue}\rule{24cm}{0.3pt}$

hectorleo123 wrote: $\color{blue}\boxed{\textbf{a) Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ With the $4\times 4$ we can change the state to a $4\times 12$ and with the $3\times 3$ we can make a $1\times 12$ change state without altering the other cells. With the $5\times 5$ you can change the state to a $5\times 20$ and with the $4\times 4$ we can make a $1\times 15$ change state without altering the other cells Now removing the $1\times 12$ from $1\times 15$ we obtain that we can change the state to a $1\times 3$ without altering the other cells Now removing these $1\times 3$ to $4\times 4$ we obtain that we can change the state of a cell without changing the state of other cells Note that this is enough to prove the statement$_\blacksquare$ $\color{blue}\rule{24cm}{0.3pt}$ How do you go from $5\times 20$ to $1\times 15$ with $4\times 4$? We have $5\cdot 20\equiv 0\pmod 4$ but $1\cdot 15\not \equiv 0\pmod 4$. A possible fix is to obtain a $1\times 20$, then do $1\times 20-1\times 12=1\times 8$, then $1\times 12-1\times 8=1\times 4$. The same moves rotated give a $4\times 1$, so you can finish subtracting those from the $5\times 5$.

Ianis wrote: hectorleo123 wrote: $\color{blue}\boxed{\textbf{a) Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ With the $4\times 4$ we can change the state to a $4\times 12$ and with the $3\times 3$ we can make a $1\times 12$ change state without altering the other cells. With the $5\times 5$ you can change the state to a $5\times 20$ and with the $4\times 4$ we can make a $1\times 15$ change state without altering the other cells Now removing the $1\times 12$ from $1\times 15$ we obtain that we can change the state to a $1\times 3$ without altering the other cells Now removing these $1\times 3$ to $4\times 4$ we obtain that we can change the state of a cell without changing the state of other cells Note that this is enough to prove the statement$_\blacksquare$ $\color{blue}\rule{24cm}{0.3pt}$ How do you go from $5\times 20$ to $1\times 15$ with $4\times 4$? We have $5\cdot 20\equiv 0\pmod 4$ but $1\cdot 15\not \equiv 0\pmod 4$. A possible fix is to obtain a $1\times 20$, then do $1\times 20-1\times 12=1\times 8$, then $1\times 12-1\times 8=1\times 4$. The same moves rotated give a $4\times 1$, so you can finish subtracting those from the $5\times 5$. fixed up

It's posible to prove the part b of this problem in general with bxb squares and cxc squares.

SebasLuna17 wrote: It's posible to prove the part b of this problem in general with bxb squares and cxc squares. How?

credits:

Let $a<b<c$ be positive integers. If only with the operations of $b\times b$ and $c\times c$, then it is impossible to obtain only a square of $a\times a$ with its lamps on. Proof: We will prove it by contradiction, suppose that it is possible by meands of a series finite operations $T$ to leave on only the lamps of a square of $a\times a$. Since the operations of $T$ are infinite then the number of cells affected(define an affected cell as a cell to which at least one operation has been applied) is alfo finite, so we can endose the affected cells in a large enough $n\times m$ board, also note that in this way the operations will be applied only to squares inside the board. On this $n\times m$ board apply the classic diagonal coloring whit $b$ colors, say $1,2,\ldots,b$. Now let us define the state of a row of the $n\times m$ board as good if in that row the number of cells of color $i$ whit lit lamps has the same parity as the number of cells of color $j$ whit lamps lit, for all $i,j\in \{1,2,\ldots,b\}$, otherwise we will say that the row is bad. Let's note that applying a $b\times b$operation does not change the state of any row, however we need that after applying the operations of $T$ we have bad rows while all the others are good rows, but the only way to change the state of one row is with $c\times c$ operations. Also note that if $c$ is a multiple of $b$ then with $c\times c$ operations it would not be possible to change the state of a row either and since all the ros are initially good it would be impossible to achieve what was said before, leading to a contradiction. Suppose then that the operations of $c\times c$ can change the state of at least one row, furthermore $T$ will have at least one operation of $c\times c$ and therefore $m,n\geq c >a.$ Let the rows of the board be $f_1,f_2,\ldots,f_n$. Let $f_k,f_{k+1},\ldots,f_{k+a-1}$ also be the rows that contain the final square of $a\times a$ that will remain with the lamps on. Sean $C_i$the set of operations(which could be empty) of $c\times c$ of $T$ that star at $f_i$ and end at $f_{i+c-1}$, for each $i\in\{1,\ldots,n+1-c\}$. Let us also see that the operation $C_i$ if equally affects the $c$ rows if affects. We will say that $C_i$ is applicable if by only applying $C_i$ then the rows over which $C_i$ was appliedthey do not change state. Lemma 1: If the rows $f_1,\ldots,f_i$ are finally good(that is,after applying the operations of $T$ they are good) then $C_1,\ldots,s_i$ (of before if there are not enough rows) are applicable. Proof: We will prove it by induction on $i$, let's see that $i=1$ is true, since if the row $f_i$ is finally good, as we know the operations of $b\times b$do not affect the state of any row, so we concentrate on the operations of $c\times c$, now the only operations on $c\times c$ that affect $f_1$ are on $C_1$, so the operations of $C_1$ do not change state to $f_1$ which was initially good, this implies that $C_1$ as a whole(that is, taking it as a single operation) changes state the same number of cells of each color $1,2,\ldots, b$ modulo 2 in $f_1$, in the same way for the other rows that if affects, and for this is true that $C_1$ is applicable. Now for the inductive step, suppose that $i=l$ satisfies Lemma 1 and now se prove $i=l+1$. Let $f_1,\ldots,f_{l+1}$ be the rows that will finally be good, then we know from the inductive hypothesis that $C_1,\ldots,C_l$ are applicable, hten in row $l+1$ we see that the only operations of $c\times c$ that affect a $f_{i+1}$ are $C_{l-c+2},\ldots,C_l+1$ in case $l\geq c-1$ and are $C_1,C_2,\ldots,C_{l+1}$ in case $l<c-1$, in both cases all the operations that affect $f_{l+1}$ are applicable except $C_{l+1}$(which remains to be tested), let's see then that by applying all the operations that affect $f_{l+1}$ except $C_{l+1}$, then $f_{l+1}$ will not change state so it will continue to be a good row, finally when applying the operations of $C_{l+1}$ it is known that $f_{l+1}$ will continue to be good, so $C_{l+1}$ as a whole changes state the same number number of cells of each color $1,2,\ldots, b$ module 2 in $f_{i+1}$, in the same way for the other rows that it affects, and for this reason it is true that $C_{l+1}$ is applicable. Therefore the induction is complete.$\square$ Lemma 2: if the rows $f_n,\ldots, f_j$ are finally good then $C_{n+1-c},\ldots,C_{j+1-c}$(or earlier if there are not enough rows)are applicable. Proof: It is enough to consider Lemma 1 by rotating the board $180^{\circ}$ and thus concludes the proof.$\square$ With these lemmas proven, we will now prove $C_1,\ldots,C_n+1-c$ are applicable. I obeserved that since $f_1,\ldots,f_{k-1}$(we assume $k\neq 1$, since if $k=1$ then the final square of $a\times a$ with lamps on would be on an edge and we can assume without loss of generality that is on the lower edge if it is on an edge) are finally good then by Lemma 1 $C_1,\ldots,C_{k-1}$ are applicable. If $k-1> n+1-c$ we prove what we wanted, in case $k-1 <n+1-c$ we would have that $k+a-1 < n+a-c+1\leq n$ so we can apply the Lemma 2 now having the rows $f_n,\ldots,f_{k+a}$ that will finally be good we can affirm that $C_{n+1-c},\ldots,C_{k+1+a-c}$ are applicable, then as $k+1+a-c\leq k-1$ it proves again what we wanted. We see then that $C_1,\ldots,C_{n+1-c}$one by one we will observe that in the en the states of the rows do not change, that is, we have applied all the operations of $c\times c$ resulting in the end that the states of the rows do not change, as they were initially good, the will continue to be so and we have already seen that if this happens, the requesta cannot be achieved since the operations of $b\times b$ will not change the state of the rows, finally remaining that when performing all the operations of $T$ that all the rows will be good, contrary to that we assumed, thus proving what was requested. $\blacksquare$

Ianis wrote: SebasLuna17 wrote: It's posible to prove the part b of this problem in general with bxb squares and cxc squares. wo How? My friend translates my solution and there is. If you find some error or something not specific in the solution I would like you tell me. Anyone remark is welcome.

MathSaiyan wrote:

I think this doesn't work because (as far as I know) you can't evaluate polynomials over $\mathbb{Z}_2$ at elements of $\mathbb{C}$.

Ianis wrote: MathSaiyan wrote:

I think this doesn't work because (as far as I know) you can't evaluate polynomials over $\mathbb{Z}_2$ at elements of $\mathbb{C}$. But you can evaluate polynomials over $\mathbb{Z}_2$ at elements over the algebraic closure of $\mathbb{Z}_2$.