$m\times n$ grid is tiled by mosaics $2\times2$ and $1\times3$ (horizontal and vertical). Prove that the number of ways to choose a $1\times2$ rectangle (horizontal and vertical) such that one of its cells is tiled by $2\times2$ mosaic and the other cell is tiled by $1\times3$ mosaic [horizontal and vertical] is an even number.
Problem
Source: Iran MO Third Round C2
Tags: combinatorics, rectangle, Parity
08.09.2022 18:22
Count the parity from 2 x 2 mosaic perspective: every mosaic has 8 edges, we call an edge bad, if it meets another mosaic or it meets nothing. Clearly the answer is the number of good edges. However every mosaic meets nothing at an even number of edges and when 2 mosaics meet, every mosaic loses the same amount of good edges, hence the total parity of good edges doesn’t change.
08.09.2022 19:56
What a joke !!
17.09.2022 11:27
We call any segment which is an edge of at least 1 unit square on the grid; a "segment *" an we call a segment* a border if the 2 squares it's adjacent to, are tiled by 2 distinct mosaics(These 2 mosaics can be either the same kind or from different kinds). We call the segment*s which are adjacent to just 1 unit square(the ones on the margin of the grid)borders too. Lemma1:An even number of borders on the margin of the grid are adjacent to a 2x2 mosaic. Proof:Consider the set S={(2x2 mosaic(A),border(B))| Border (B) is on the margin of the mxn grid and the square this border is an edge of, is tiled by 2x2 mosaic(A)} |S|=The number of such borders(#) On the other hand each 2x2 mosaic is the first component in even number of elements of S; divide the 8 segment*s on its margin into 4 groups;each group is an edge(two segment*s); a segment* is a desired border if and only if the other segment* on it's group is a desired one,so the claim is proved. Since any 2x2 mosaic is the first component of even number of elements in S; |S| is even and by (#); we deduce the number of the desired borders is even and the lemma's proof is done. Now, consider the set M={(2x2 mosaic(A), mosaic(B),border(C)) | Border(C) is a border between mosaics A and B} Borders on the margin of the grid, and borders between two 1x3 mosaics are the third component of 0 elements of M and borders between two 2x2 mosaics are the third component of 2 elements of M(2 ways to set the first component from two 2x2 mosaics),hence: |M|=(mod2)the number of borders between a 2x2 and a 1x3 mosaic; call such borders "good" borders. And also for any 2x2 mosaic as the first component and any segment* on the margin of it as the third component; the second component is uniquely obtained;except if the segment* chosen is the second component of an element in S; and for such segment*s it's impossible to determine the second component(such that the obtained element becomes an element of M)hence if the number of 2x2 mosaics used is a: |M|=8a-|S| which is an even number according to lemma1 so the number of good borders is an even number. Now we prove the number of ways of choosing a 2x1 rectangle; whose squares are in a 2x2 mosaic and a 1x3 mosaic is equal to the number of good borders. For each 2x1 rectangle there is exactly 1 segment* in it; pair any 2x1 rectangle to the segment* in it.each desired rectangle, pairs to a good border and vice versa; so the problem's proof is complete.
17.09.2022 23:58
Shayan-TayefehIR wrote: What a joke !! Rather than being rude, can you point out the flaw in my solution?
18.09.2022 12:17
R8kt wrote: Shayan-TayefehIR wrote: What a joke !! Rather than being rude, can you point out the flaw in my solution? There is a misunderstanding :// I didn't mean that your solution is joke :/// My react was for the problem which is weird for Iran P2 combinations , your sol is totally correct.
22.09.2022 21:59
Solved with HakNx Write the number $1$ in each unit square tiled by $2 \times 2$ tiles and $0$ in $3 \times 1$ tiles respectively. For any possible domino sum up all the numbers on the unit squares covered by that domino and add all the sums together, call this sum $S$. Let $N$ be the number of $1$'s on the edges excluding the corners. Double count from each unit squares perspective and notice that $S \equiv N (mod 2)$. Claim: $N$ is even. Proof: Investigate the 2 cases when $2 \times 2$ tiles are on the edge but do not contain any corners and the case when a $2 \times 2$ contains a corner unit square, in each case each $2 \times 2$ adds exactly $2$ 1's making the total even. Now notice that this sum $S$ is equal to the number of neigboring edges between $2 \times 2$ 's and $3 \times 1$'s, which finishes the problem.