Flipping L's

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Flipping L's

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2023 C1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#1 h Jul 17, 2024, 12:15 PM • 2 Y

Y by OronSH, peace09

Let $m$ and $n$ be positive integers greater than $1$ . In each unit square of an $m\times n$ grid lies a coin with its tail side up. A move consists of the following steps.

select a $2\times 2$ square in the grid;
flip the coins in the top-left and bottom-right unit squares;
flip the coin in either the top-right or bottom-left unit square.

Determine all pairs $(m,n)$ for which it is possible that every coin shows head-side up after a finite number of moves.

Thanasin Nampaisarn, Thailand

This post has been edited 1 time. Last edited by MarkBcc168, Jul 24, 2024, 4:00 PM
Reason: author

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1745 posts

OronSH

#2 h Jul 17, 2024, 12:15 PM • 3 Y

Y by peace09, ihatemath123, Funcshun840

We claim the answer is $3\mid mn.$

For the construction, the idea is that it is possible to flip a $3\times 1$ rectangle, with the following steps:

$[asy] size(10cm); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle); draw((5,0)--(8,0)--(8,2)--(5,2)--cycle); draw((10,0)--(13,0)--(13,2)--(10,2)--cycle); draw((15,0)--(18,0)--(18,2)--(15,2)--cycle); draw((3.5,1)--(4.5,1),Arrow); draw((8.5,1)--(9.5,1),Arrow); draw((13.5,1)--(14.5,1),Arrow); filldraw((7,0)--(8,0)--(8,2)--(6,2)--(6,1)--(7,1)--cycle,gray); draw((7,0)--(8,0)--(8,2)--(6,2)--(6,1)--(7,1)--cycle,linewidth(1.5)); filldraw((11,0)--(12,0)--(12,2)--(13,2)--(13,1)--(11,1)--cycle,gray); draw((11,0)--(13,0)--(13,1)--(12,1)--(12,2)--(11,2)--cycle,linewidth(1.5)); filldraw((15,1)--(18,1)--(18,2)--(15,2)--cycle,gray); draw((16,0)--(17,0)--(17,2)--(15,2)--(15,1)--(16,1)--cycle,linewidth(1.5)); draw((1,0)--(1,2)); draw((6,0)--(6,2)); draw((11,0)--(11,2)); draw((16,0)--(16,2)); draw((2,0)--(2,2)); draw((7,0)--(7,2)); draw((12,0)--(12,2)); draw((17,0)--(17,2)); draw((0,1)--(3,1)); draw((5,1)--(8,1)); draw((10,1)--(13,1)); draw((15,1)--(18,1)); [/asy]$
Then if $3\mid mn,$ it is possible to cut the rectangle into $3\times 1$ strips and flip all of them. (This doesn't run into space issues since $m,n\ge 2.$ )

To show this is necessary, color the cell $(x,y)$ with the remainder when $2x+y$ is divided by $3.$ Then each move flips one cell of each color, and thus the number of heads-up coins of each color must always have the same parity. Thus we show that for $3\nmid mn$ there exist two colors that appear different-parity numbers of times.

To do this, first cut the rectangle into four pieces, three of which have at least one side length divisible by $3$ and the fourth has both dimensions $<3.$ An example is as shown:
$[asy] size(7cm); draw((0,0)--(7,0)--(7,5)--(0,5)--cycle); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((5,0)--(5,5)); draw((6,0)--(6,5)); draw((0,1)--(7,1)); draw((0,2)--(7,2)); draw((0,3)--(7,3)); draw((0,4)--(7,4)); draw((-1,2)--(8,2),linewidth(2)); draw((1,-1)--(1,6),linewidth(2)); label("0",(0,0),dir(44)*2.9); label("1",(0,1),dir(44)*2.9); label("2",(0,2),dir(44)*2.9); label("0",(0,3),dir(44)*2.9); label("1",(0,4),dir(44)*2.9); label("2",(1,0),dir(44)*2.9); label("0",(1,1),dir(44)*2.9); label("1",(1,2),dir(44)*2.9); label("2",(1,3),dir(44)*2.9); label("0",(1,4),dir(44)*2.9); label("1",(2,0),dir(44)*2.9); label("2",(2,1),dir(44)*2.9); label("0",(2,2),dir(44)*2.9); label("1",(2,3),dir(44)*2.9); label("2",(2,4),dir(44)*2.9); label("0",(3,0),dir(44)*2.9); label("1",(3,1),dir(44)*2.9); label("2",(3,2),dir(44)*2.9); label("0",(3,3),dir(44)*2.9); label("1",(3,4),dir(44)*2.9); label("2",(4,0),dir(44)*2.9); label("0",(4,1),dir(44)*2.9); label("1",(4,2),dir(44)*2.9); label("2",(4,3),dir(44)*2.9); label("0",(4,4),dir(44)*2.9); label("1",(5,0),dir(44)*2.9); label("2",(5,1),dir(44)*2.9); label("0",(5,2),dir(44)*2.9); label("1",(5,3),dir(44)*2.9); label("2",(5,4),dir(44)*2.9); label("0",(6,0),dir(44)*2.9); label("1",(6,1),dir(44)*2.9); label("2",(6,2),dir(44)*2.9); label("0",(6,3),dir(44)*2.9); label("1",(6,4),dir(44)*2.9); [/asy]$
Now the three rectangles with a side divisible by $3$ can be tiled by $3\times 1$ rectangles, and thus have the same number of each color.

Thus it suffices to check rectangles with side lengths $<3:$ the $1\times 1$ and $2\times 1$ have one $0$ and zero $1$ s, the $1\times 2$ has one $0$ and zero $2$ s, and the $2\times 2$ has two $0$ s and one $1.$

Thus each of these has two colors with different parities, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#3 h Jul 17, 2024, 12:15 PM • 10 Y

Y by Snark_Graphique, peace09, OronSH, Modesti, Zsnim, mathleticguyyy, GoodMorning, jrpartty, Bonime, Want-to-study-in-NTU-MATH

I love generating functions.

The answer is $3\mid mn$ .

Work in the polynomial ring $\mathbb F_2[x,y]$ . We represent a configuration by the polynomial in the set
$S = \left\{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} x^iy^j : a_{ij}\in\mathbb F_2\right\} \subset\mathbb F_2[x,y],$ where for a configuration with polynomial $\textstyle{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} x^iy^j}$ , the cell $(i+1,j+1)$ is head if $a_{ij}=0$ and tails otherwise.

Thus, each move corresponds to adding a monomial times $x+y+1$ or $x+y+xy$ into the polynomial. Therefore, a configuration can be made into all heads if and only if the corresponding polynomial is in form $P(x,y)(x+y+1) + Q(x,y)(x+y+xy)$ .

We need to determine whether the polynomial
$P(x,y) = (1+x+x^2+\dots+x^m)(1+y+y^2+\dots+y^n)$ can be written in that form. By reducing modulo $x+y+1$ , we are left to check whether $P(x,-1-x)$ is divisible by $x+(-1-x)+x(-1-x) = -(x^2+x+1)$ . This is true if and only if either $1+x+\dots+x^m$ or $1+x+\dots+x^n$ is divisible by $1+x+x^2$ , which occurs if and only if $3\mid mn$ .

This post has been edited 2 times. Last edited by MarkBcc168, Jul 17, 2024, 12:17 PM
Reason: I'm not the first post

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

#4 h Jul 17, 2024, 12:17 PM

Y by

Note that the polynomials in Markbcc's solution can also be understood as using a finite field $F = \{0, 1, \omega, \omega^2\}$ of characteristic two as weights and utilising a method similar to that of 2021 USAMO 3.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

407 posts

#5 h Jul 17, 2024, 1:42 PM • 2 Y

Y by Zsnim, isomoBela

The answer is all pairs $(m,n)$ such that $3\mid mn$ .

To see why the others don't work, label the cells of the grid as $(i,j)$ for $1\leq i\leq m$ and $1\leq j\leq n$ (with the bottom left corner being $(1,1)$ ), and write $(i-j)\pmod 3$ in each of them. A move flips one coin of each residue, but as there are $\lfloor mn/3 \rfloor$ cells with one residue and $\lceil mn/3\rceil = \lfloor mn/3\rfloor+1$ with another, we get that the number of moves must be both even and odd for all coins to show heads, which is impossible.

We now show a construction for all grids $m\times n$ where $3\mid mn$ . We can partition every such grid into multiple $2\times 3$ , $3\times 2$ , and $3\times 3$ subgrids by dividing the initial grid into rectangular strips $3\times n$ or $m\times 3$ . Now, each such strip can be cut into $2\times 3$ or $3\times 2$ rectangles if the larger side is even, and such rectangles and one $3\times 3$ if it's odd. Therefore proving the statement for the grids $2\times 3$ , $3\times 2$ , and $3\times 3$ suffices.

For brevity, call $L_{i,j}$ the set of cells $\{(i,j), (i+1, j), (i, j+1)\}$ , and $R_{i+1,j+1}$ the set of cells $\{(i+1,j), (i,j+1), (i+1, j+1)\}$ . For $2\times 3$ , switching $L_{1,1}$ and $R_{2,3}$ works. Similarly, for $3\times 2$ , switching $L_{1,1}$ and $R_{3,2}$ does the job. For $3\times 3$ , we have the slightly more convoluted combination of moves $L_{1,1}+L_{1,2}+L_{2,1}+R_{2,2}+R_{3,3}$ which suffices. This completes the solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6 posts

Zsnim

#6 h Jul 17, 2024, 5:31 PM • 1 Y

Y by Zvn

We claim that the solution is all pairs $(m,n)$ for which $3|mn$

The construction for $3|mn$ is the same as posts above.

Consider the following coloring of the board:

https://imgur.com/l0OL2u6

Description of the coloring (in case the image does not work):

We will color the board in 3 colors along the diagonals going upwards from left to right. Notice that in this coloring we have that, no matter which three squares we pick, we will always pick three squares with a different color.

Now, if $3 \nmid mn$ then one of the colors will be of a different quantity than the other two (it will be $1$ more or $1$ less than the other colors), hence the quantity of one color will be of different parity than the other two.

Claim: If the quantity of some color is uneven, then flipping all tails to heads on that color will take an uneven number of moves.

Assume we have m squares colored with color A and m is uneven. To turn one single coin from tails to heads it takes an uneven amount of moves performed on that coin so summing up m uneven numbers we get an uneven number, hence the claim is true

Claim: If the quantity of some color is even, then flipping all tails to heads on that color will take an even number of moves.

The proof is very similar to the proof given above.

Because we got that the number of moves must be both even and odd (because we have both parities for the quantities of colors), we got a contradiction. Hence, it must be that $3|mn$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

Jack_w

#7 h Jul 17, 2024, 7:17 PM

Y by

The answer is $3\mid m$ or $3\mid n$ (i.e. $3\mid mn$ ). For a construction, observe that we can flip any $3 \times 2$ rectangle; then take a $3 \times 2$ rectangle and flip the L-shape in the bottom left, the L-shape one cell to the right of it, and the rotated L-shape in the bottom left to leave only the bottom row of the $3 \times 2$ flipped (look at oron's in post #2). To get the top row, just flip the whole $3 \times 2$ . Thus we can flip any $3 \times 1$ rectangle, and by reflecting everything $45^{\circ}$ , we can also flip any $1 \times 3$ rectangle. Therefore if $3 \mid mn$ we can repeatedly flip $1 \times 3$ rectangles along the rows or columns to flip the whole grid.

Also, since $m, n > 1$ , we'll always have room to choose a $3 \times 2$ or $2 \times 3$ rectangle to do this.

Now index the rows $(1, \dots, m)$ from left to right and index the columns $(1, \dots, n)$ from top to bottom. In each cell $(i, j)$ , write the value of $(i + j) \pmod3$ . Then each move flips exactly one $0$ , one $1$ , and one $2$ . So, to flip all $mn$ cells, the amount of $0$ 's, $1$ 's, and $2$ 's must be equal $\pmod 2$ . It's easy to see (say, by chopping off $3 \times k$ grids of rows and columns to leave a $2 \times 2$ or smaller) that the amount of cells labeled with each residue cannot differ by 2 or more, so they must be equal. This implies $3 \mid mn$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#8 h Jul 18, 2024, 12:10 AM

Y by

The construction is omitted cuz its silly.

We first show necessity. We want to find sols to $P(x, y)(1 + x + y) + Q(x, y)(x + y + xy) = (1 + x + \dots + x^m)(1 + y + \dots + y^n)$ over $\mathbb{F}_2$ . Note that $x^2 + x + 1$ is irreducible over $\mathbb{F}_2$ so extend our field extension to get $\mathbb{F}_2[\zeta]$ where $\zeta$ is the third root of unity.

Now, substitute $x = \zeta, y = \zeta^2$ . Then $1 + x + y = x + y + xy = 0$ , so the LHS is $0$ . Then either $\zeta$ is a root of $(1 + x + \dots + x^m)$ or $\zeta^2$ is a root of $(1 + y + \dots + y^n)$ so $3$ divides one of $m$ and $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

180 posts

dkedu

#9 h Jul 22, 2024, 6:39 AM

Y by

We claim the answer is $3\mid mn$ .

Consider the sets of diagonals formed by taking $i-j\pmod 3$ . Let there be $a,b,c$ in each of these sets of columns. We have that $a \equiv b\equiv c\pmod 2$ . However, for the whole grid to be covered, this means $a = b= c$ since the size of the set of diagonals differ by at most $1$ .

Note that $3\mid mn$ implies $3\mid m$ or $3\mid n$ . By taking the following L-shapes, we can flip any $1 \times 3$ meaning we can flip the whole grid.

$(i,j),(i+1,j),(i,j+1)$ , $(i+1,j+1), (i,j+1), (i+1,j)$ , $(i+1,j+1), (i+1,j), (i+2,j)$ flips only $(i,j), (i+1,j), (i+2,j)$ so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1272 posts

ezpotd

#10 h Oct 1, 2024, 3:48 AM

Y by

hardest c1??

I claim the answer is $3 \mid mn$ with $mn \neq 3$ .

Construction: We prove that we can achieve all heads for all $3$ by $x$ rectangles for $x > 1$ . Then we can finish by just combining such rectangles, and applying moves on them separately.

We do this by proving we can achieve $3$ by $2$ and $3$ by $3$ rectangles. Then we can finish by just combining such rectangles, and applying moves on them separately.

To make a $3$ by $2$ do the move on the squared labeled 1 in the first move and 2 in the second move.

22
12
11

To make a $3$ by $3$ do the following moves written the same way as before to get the left column completely heads and everything else tails, then do the $3$ by $2$ to get the full thing.

(1) () ()
(123) (13) ()
(2) (23) ()
Proof of necessity: Color the rectangle by the following easily generalizable coloring
.......
231231231231...
312312312312...
123123123123...

Then each operation changes the parity of the total number of heads of each color by one, thus they all have the same parity of number of heads, if $3 \nmid mn$ this will not be possible in the final scenario since they will have all heads but the colors occur with different parities.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

113 posts

#11 h Nov 23, 2024, 12:14 PM

Y by

2 way gen func nice
The answer is $3\mid mn$ . I give an algebric proof of both directions

Treat the position as a polynomial in $\mathbb{F}_2(x,y)$

We now get that each move corresponds to adding some term of the form $x^iy^j$ times $x+y+1$ or $x+y+xy$ into the polynomial(modulo 2 FTW!). Therefore, a configuration can be made into all heads if and only if the corresponding polynomial is in form $P(x,y)(x+y+1) + Q(x,y)(x+y+xy)$ .

Now we want to determine wheter
$R(x,y) = (1+x+x^2+\dots+x^m)(1+y+y^2+\dots+y^n)$ can be written in that form. If we reduce modulo $x+y+1$ , we must check that $P(x,-1-x)$ is divisible by $x+(-1-x)+x(-1-x) = -(x^2+x+1)$ . This is true iff either $x^m+\dots+x^2+x+1$ or $x^n+\dots+x+1$ is divisible by $x^2+x+1$ , which can be checked to occur if and only if $3\mid mn$ , as desired

Remark: My original solution was the combinatorial one(in terms of construction) but then I got the algebric one while trying to prove the only if direction but I only got the only if of the algebric version by substituting $(x,y)=(\omega,\omega^2)$ but then later I was told by a friend the modulo $x+y+1$ trick

This post has been edited 4 times. Last edited by quantam13, May 9, 2025, 1:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8866 posts

#12 h Dec 7, 2024, 12:29 AM

Y by

The answer is all $m, n$ such that $3 \mid m$ or $3 \mid n$ .

Bound: We color the chessboard cells red, blue, or green such that every row and column reads red, blue, green, repeating in that order. Any operation performed on the chessboard will then operate on an equal number of red, blue, and green cells.

Claim: The number of red, blue, and green cells must all be the same parity.

Proof: Assume for the sake of contradiction that there were an even number of red cells and odd number of blue cells. It follows that to flip all the coins in the blue cells, it requires an odd number of operations (as every cell should be affected an odd number of times.) But applying the same argument to the red cells, there should be an even number of operations, contradiction. $\blacksquare$

Suppose there are $r$ red cells, $b$ blue cells, and $g$ green cells in the coloring. Observe that $|r-b|$ is unaffected if we remove any three columns or three rows; so the only possible values $|r-b|$ can take are those for a $1 \times 1$ , $1 \times 2$ , or $2 \times 2$ grid. For each of these grids, $|r-b| \leq 1$ . This implies that $r=g=b$ , so the number of cells is a multiple of three.

Construction: Clearly a $3 \times 2$ square can be constructed, and a $3 \times 3$ square can be constructed as follows: place the cells in a coordinate system such that $(1, 1)$ represents the bottom-left square, and consider performing operations on

the square with bottom-left corner $(1, 1)$ , flipping that corner;
the square with top-right corner $(2, 2)$ , flipping that corner;
the square with bottom-left corner $(1, 2)$ , flipping that corner;
the square with top-right corner $(2, 2)$ , flipping that corner; and
the square with bottom-left corner $(2, 1)$ , flipping that corner.

Any $3 \times n$ grid can be divided into $3 \times 2$ and $3 \times 3$ grids, so the result follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#14 h Apr 24, 2025, 8:37 AM

Y by

Answer: $3 \mid mn$

Proof: Let's colour the board in the following colouring:

1 2 3 1 2 3 1 2 3
2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2
1 2 3 1 2 3 1 2 3
2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2

Note, that in every move one of each type of coin is flipped. Therefore, the amount of $1$ 's $2$ 's and $3$ 's initially should have been the same. This is only achieved when $3 \mid mn$ , so the bound is done.

For construction, it is easy to see we can always fit in a $2 \times 3$ rectangle. Now, the only thing we need to do is learn how to flip all the coins in a $1 \times 3$ array. This however can be done in the following way:

T T T | H H T | T H T | T T T
T T T | T H T | H T T | H H H

Hence now we are done.

This post has been edited 2 times. Last edited by zRevenant, Apr 24, 2025, 8:39 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a