That was also Germany TSTST Day 2, #3.

Anyway it's easy.The idea is to find a coloring such that every S tetromino has even number of colored cells inside and Z tetromino an odd number of colored cells. Then the result would easily follow. There is an example of such coloring. 000100010001000 011101110111011 001110111011101 001000100010001 000100010001000 011101110111011

111011101110.... 011101110111... 1011101110111... 11011101110111... Another example of such a coloring.

May we rotate the tetraminos? If we can, I`m not sure these colorings work.

And if we can`t here is another coloring: 1 2 3 4 1 2 3 4....... 4 1 2 3 4 1 2 3...... 3 4 1 2 3 4 1 2...... 2 3 4 1 2 3 4 1 ......

Rotation is certainly allowed, and that coloring doesn't work. (Neither does JackXD's, for that matter. CostaAzzurra's is close, but has a typo in the first column.) The key here is that we can turn an S into a Z or vice versa by exchanging a tile with one separated by a vector of $(\pm 2,\pm 2)$. That means that for us to have a meaningful difference, tiles separated in that way must always be of different colors. A coloring that has single-color diagonals, in either direction, can't possibly work. Here's my coloring - similar to CostaAzzurra's, but with slightly different choices of alignment. Also, much prettier: [asy][asy]pair Y0=(0,0); pair A0=(1,0); pair B0=(2,0); pair C0=(3,0); pair D0=(4,0); pair E0=(5,0); pair F0=(6,0); pair G0=(7,0); pair H0=(8,0); pair Y1=(0,1); pair A1=(1,1); pair B1=(2,1); pair C1=(3,1); pair D1=(4,1); pair E1=(5,1); pair F1=(6,1); pair G1=(7,1); pair H1=(8,1); pair Y2=(0,2); pair A2=(1,2); pair B2=(2,2); pair C2=(3,2); pair D2=(4,2); pair E2=(5,2); pair F2=(6,2); pair G2=(7,2); pair H2=(8,2); pair Y3=(0,3); pair A3=(1,3); pair B3=(2,3); pair C3=(3,3); pair D3=(4,3); pair E3=(5,3); pair F3=(6,3); pair G3=(7,3); pair H3=(8,3); pair Y4=(0,4); pair A4=(1,4); pair B4=(2,4); pair C4=(3,4); pair D4=(4,4); pair E4=(5,4); pair F4=(6,4); pair G4=(7,4); pair H4=(8,4); pair Y5=(0,5); pair A5=(1,5); pair B5=(2,5); pair C5=(3,5); pair D5=(4,5); pair E5=(5,5); pair F5=(6,5); pair G5=(7,5); pair H5=(8,5); pair Y6=(0,6); pair A6=(1,6); pair B6=(2,6); pair C6=(3,6); pair D6=(4,6); pair E6=(5,6); pair F6=(6,6); pair G6=(7,6); pair H6=(8,6); pair Y7=(0,7); pair A7=(1,7); pair B7=(2,7); pair C7=(3,7); pair D7=(4,7); pair E7=(5,7); pair F7=(6,7); pair G7=(7,7); pair H7=(8,7); pair Y8=(0,8); pair A8=(1,8); pair B8=(2,8); pair C8=(3,8); pair D8=(4,8); pair E8=(5,8); pair F8=(6,8); pair G8=(7,8); pair H8=(8,8); //Grid points defined fill(A1--Y1--Y0--A0--cycle, red); fill(C4--A4--A5--Y5--Y2--A2--A1--B1--B3--C3--cycle, red); fill(C8--Y8--Y6--A6--A5--B5--B7--C7--cycle, red); fill(E1--D1--D0--E0--cycle, red); fill(G4--E4--E5--D5--D3--C3--C2--E2--E1--F1--F3--G3--cycle, red); fill(G8--D8--D7--C7--C6--E6--E5--F5--F7--G7--cycle, red); fill(H3--G3--G2--H2--cycle, red); fill(H7--G7--G6--H6--cycle, red); fill(A2--Y2--Y1--A1--cycle, green); fill(A6--Y6--Y5--A5--cycle, green); fill(E2--C2--C3--B3--B1--A1--A0--D0--D1--E1--cycle, green); fill(E6--C6--C7--B7--B5--A5--A4--C4--C3--D3--D5--E5--cycle, green); fill(D8--C8--C7--D7--cycle, green); fill(H2--G2--G3--F3--F1--E1--E0--H0--cycle, green); fill(H6--G6--G7--F7--F5--E5--E4--G4--G3--H3--cycle, green); fill(H8--G8--G7--H7--cycle, green);//Coloring the cells draw(Y0--Y8); draw(A0--A8); draw(B0--B8); draw(C0--C8); draw(D0--D8); draw(E0--E8); draw(F0--F8); draw(G0--G8); draw(H0--H8); draw(Y0--H0); draw(Y1--H1); draw(Y2--H2); draw(Y3--H3); draw(Y4--H4); draw(Y5--H5); draw(Y6--H6); draw(Y7--H7); draw(Y8--H8);//Grid lines [/asy][/asy] Numbering from $(0,0)$ in the lower left, we color square $(x,y)$ red if $y-x\equiv 0\mod 4$ and $y\equiv 0,1\mod 4$ or if $y-x\not\equiv 0\mod 4$ and $y\equiv 2,3\mod 4$. The coloring is periodic mod $4$ in each direction, so testing the number of red and green tiles in an S-tetromino or a Z-tetromino requires only sixteen cases for each orientation. For wide S-tetrominoes, index them by their lower left corner tile. If that tile is $(1,0)$ or $(2,0)$, all four tiles are green. If it's $(0,2)$ or $(3,2)$, all four tiles are red. If it's one of the other twelve cases, two of the tiles are red and two are green. For tall S-tetrominoes, index them by their lower right corner tile. If that tile is $(3,0)$ or $(3,3)$, all four tiles are green. If it's $(1,1)$ or $(1,2)$, all four tiles are red. If it's one of the other twelve cases, two of the tiles are red and two are green. For wide Z-tetrominoes, index them by their upper left corner tile. If that tile is $(0,1)$, $(1,1)$, $(2,1)$, $(3,1)$, $(1,2)$, $(2,2)$, $(1,4)$, or $(2,4)$, three of its tiles are green and one is red. If it's one of the other eight cases, one is green and three are red. For tall Z-tetrominoes, index them by their lower left corner tile. If that tile is $(1,0)$, $(2,0)$, $(3,0)$, $(2,1)$, $(2,2)$, $(3,1)$, $(3,2)$, or $(3,3)$, three of its tiles are green and one is red. If it's one of the other eight cases, one is green and three are red. In all cases, S-tetrominoes have an even number of red tiles and Z-tetrominos have an odd number of red tiles. A polygon P that can be tiled with S-tetrominoes thus contains an even number of red tiles, and any tiling of it using S- and Z- tetrominoes uses an even number of Z-tetrominoes.

Here's a similar polynomial solution to Aiscrim

In case anybody thinks the colouring solution (with two colours) is completely magical, I just want to point out that it isn't too hard to come up with once you have the mindset that the problem could potentially be solved with such a colouring. Basically, once we fix the colours of any $2\times 2$ square, the colours of all the other squares in our grid are uniquely determined. It turns out that it doesn't matter how you colour your $2\times 2$ square - any colouring will lead to a colouring that works to solve the problem. So once you colour it, observe when the colouring of the grid becomes periodic, which must be the case by a Pigeonhole argument.

Consider the generated structure below, along with the surrounding air to form a 4x4 block: It is easy to see, through a finite case check, that if one tesselates the plane with this shape in a gridlike fashion, then all S-tetrominoes have an even number of dirt blocks, and all Z-tetrominoes have an odd number. Thus, if P can be tiled with S-tetrominoes, it must have an even number of dirt blocks and hence we must always use an even number of Z-tetrominoes.

Solution with Alex_z_Awesome. Say that $P$ can be tiled with only $H_S$ horizontal $S$-tetrominoes and $V_S$ vertical $S$-tetrominoes. Furthermore say that $P$ can be tiled with $h_S$ horizontal $S$-tetrominoes, $v_S$ vertical $S$-tetrominoes, $h_Z$ horizontal $Z$-tetrominoes, and $v_Z$ vertical $Z$-tetrominoes. Now consider the following two colorings that we tessellate across the grid: [asy][asy] unitsize(0.3cm); picture p1, p2; for (int i = 0; i < 10; ++i) { for (int j = 0; j < 10; ++j) { fill(p1, box((i, j), (i + 1, j + 1)), ((i + floor(j/2)) % 2 == 0) ? black : white); fill(p2, box((i, j), (i + 1, j + 1)), ((i - j) % 4 == 0) ? black : white); } } for (int i = 0; i <= 10; ++i) { draw(p1, (i, 0)--(i, 10)); draw(p1, (0, i)--(10, i)); draw(p2, (i, 0)--(i, 10)); draw(p2, (0, i)--(10, i)); } add(p1); add(shift((15, 0))*p2); [/asy][/asy] Work in $\mathbb F_2$. Consider the number of total number of black squares in $P$. It's easy to see that by the in the first coloring, horizontal $S$ and $Z$-tetrominoes contain $0$ black squares, and vertical $S$ and $Z$-tetrominoes contain $1$ black square. It follows that $V_S = v_s + v_z$. Now in the second coloring, horizontal $S$ and vertical $Z$-tetrominoes contain $0$ black squares, and horizontal $Z$ and vertical $S$-tetrominoes contain $1$ black square. It follows that $V_S = v_s + h_z$. Now adding the two gives $h_z + v_z = 0$, as desired. $\blacksquare$

Words are hard, but this colouring should work \begin{tabular} {c c c c c c c c c c c c} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ \end{tabular}

When you realize that all colorings are truly just algebraic manipulations ... $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{\text{This Solution doesn't need Sections.}}$ Consider the tiling of the infinite grid using $4 \times 4$ squares as following:

Note that each $S$-tetromino hits an even number of green squares and each $Z$-tetromino hits an odd number of green squares. By simple parity we are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

This problem actually has a slick motivation which I am surprised no one else has shared yet! [asy][asy]usepackage("tikz");label("\begin{tikzpicture} [scale = 1.3] %\fill[green!50!white] (1,2)--(1,4)--(2,4)--(2,3)--(4,3)--(4,2)--(3,2)--(3,0)--(2,0)--(2,1)--(0,1)--(0,2)--cycle; \fill[white!10!white] (0,0)--(0,1)--(2,1)--(2,0)--cycle; \fill[white!10!white] (2,3)--(2,4)--(4,4)--(4,3)--cycle; \fill[white!10!white,shift = {(4,0)},rotate = 90] (0,0)--(0,1)--(2,1)--(2,0)--cycle; \fill[white!10!white,shift = {(1,2)},rotate = 90] (0,0)--(0,1)--(2,1)--(2,0)--cycle; \draw[red,thick] (0.5, 0.5)--(0.5,1.5)--(1.5,1.5)--(1.5,2.5); \draw[magenta,thick] (0.7,1.3)--(1.7,1.3)--(1.7,2.3)--(2.7,2.3); \foreach \i in {0,1,2,3,4} \draw[blue,thick] (\i,0)--(\i,4); \foreach \j in {0,1,2,3,4} \draw[blue,thick] (0,\j)--(4,\j); \end{tikzpicture}");[/asy][/asy] The first thing is that the tetrominoes are differently oriented. That's the only difference. And parity is useful while dealing with different orientations. So we try to color the infinite grid with two colours such that every $S$ - tetromino covers an even number of black and white squares and every $Z$ - tetromino covers an odd number of each of them. In the configuration above, both tetrominoes are of different classes. And they share 3 common squares. So the lone squares (those are the top right and bottom left) are of different colours! Hence we get that if $(x, y)$ is black, then $(x \pm 2, y \pm 2)$ is white and vice versa. Now start filling squares (randomly colour when not forced) while following this heuristic and VOILA! You came up with a one-liner for a C4

Consider a grid, but subdivided into $4\times 4$ chunks. In each chunk, color the following eight squares black: the second square in the first row, the second through fourth squares in the second row, the first through third squares in the third row, and the third square in the fourth row, in order to create a windmill structure like this: Note that however we place an $S$-tetromino, the number of black squares covered will be even. However we place a $Z$-tetromino, the number of black squares covered will be odd. Thus, if we are able to tile $P$ with only $S$-tetrominoes then there are an even number of black squares. It follows that there must be an even number of $Z$-tetrominos in our configuration.

It's peak comedy, that's what it is. Reminiscent of 2021 ISL C6. 111111111111000000000000111111111111111111111111 111111111111000000000000111111111111111111111111 111111111111000000000000111111111111111111111111 111111111111000000000000111111111111111111111111 111111111111000000000000111111111111111111111111 111111111111000000000000111111111111111111111111 111111111111000000000000000000000000000000000000 111111111111000000000000000000000000000000000000 111111111111000000000000000000000000000000000000 111111111111000000000000000000000000000000000000 111111111111000000000000000000000000000000000000 111111111111000000000000000000000000000000000000 000000000000000000000000000000000000111111111111 000000000000000000000000000000000000111111111111 000000000000000000000000000000000000111111111111 000000000000000000000000000000000000111111111111 000000000000000000000000000000000000111111111111 000000000000000000000000000000000000111111111111 111111111111111111111111000000000000111111111111 111111111111111111111111000000000000111111111111 111111111111111111111111000000000000111111111111 111111111111111111111111000000000000111111111111 111111111111111111111111000000000000111111111111 111111111111111111111111000000000000111111111111 Tile the grid with these 4x4 chunks, and any S intersects an even number of times, any Z intersects an odd number of times. Hence by invariant, we are done. This config is motivated by xoring the following shapes: 0011 1100 0011 1100, the horizontal detector, and 1000 0100 0010 0001, the 4-coloring detector.

polynomial in combi nice

Color some cells of grid grey, as a repeating of coloring below. [asy][asy] unitsize(15); for(int x=0; x < 8; x = x + 4){ for(int y=0; y < 8; y = y + 4){ fill((x+2,y)--(x+2,y+1)--(x,y+1)--(x,y+2)--(x+1,y+2)--(x+1,y+4)--(x+2,y+4)--(x+2,y+3)--(x+4,y+3)--(x+4,y+2)--(x+3,y+2)--(x+3,y)--cycle, grey); } } for(int i = 0; i < 9; ++i){ draw((i,0)--(i,8)); draw((0,i)--(8,i)); } [/asy][/asy] Observe that any $S-$tetramino covers exactly even number of grey cells, so it does $P$. But any $Z-$tetramino covers exactly odd number of grey cells, so the conclusion follows.

This problem makes me sad. Consider the following coloring extended to the entire grid $\square \text{ } \blacksquare \text{ } \square \text{ } \square \text{ } \square \text{ } \blacksquare \text{ } \square \text{ } \square$ $\square \text{ } \blacksquare \text{ } \blacksquare \text{ } \blacksquare \text{ } \square \text{ } \blacksquare \text{ } \blacksquare \text{ } \blacksquare$ $\blacksquare \text{ } \blacksquare \text{ } \blacksquare \text{ } \square \text{ } \blacksquare \text{ } \blacksquare \text{ } \blacksquare \text{ } \square$ $\square \text{ } \square \text{ } \blacksquare \text{ } \square \text{ } \square \text{ } \square \text{ } \blacksquare \text{ } \square $ $\square \text{ } \blacksquare \text{ } \square \text{ } \square \text{ } \square \text{ } \blacksquare \text{ } \square \text{ } \square$ $\square \text{ } \blacksquare \text{ } \blacksquare \text{ } \blacksquare \text{ } \square \text{ } \blacksquare \text{ } \blacksquare \text{ } \blacksquare$ $\blacksquare \text{ } \blacksquare \text{ } \blacksquare \text{ } \square \text{ } \blacksquare \text{ } \blacksquare \text{ } \blacksquare \text{ } \square$ $\square \text{ } \square \text{ } \blacksquare \text{ } \square \text{ } \square \text{ } \square \text{ } \blacksquare \text{ } \square $ Each $Z$-tetromino covers an odd number of black squares and each $S$-tetromino covers an even number of black squares. So, $P$ contains an even number of black squares. But, of we tile $P$ using an odd number of $Z$-tetrominoes, then $P$ contains an odd number of black squares. Contradiction.

Here is a simpler algebraic solution. Consider an infinite grid, and place the polyomino $P$ on it. Since the polyomino is finite, we can call a cell below and to the left of all cells of the polyomino, and call it $(0,0)$. For any $(a,b)$, let $(a+1,b)$ be the cell to its right and $(a,b+1)$ be the cell above it. For $a,b\ge 0$, let $x^ay^b$ represent the cell $(a,b)$. For a S-tetromino that takes up squares $(a,b), (a+1,b), (a+1,b+1),(a+2,b+1)$, it represents $x^ay^b (1+x+xy+x^2y) = x^ay^b (1+x)(1+xy)$. An S-tetromino can also take up $(a,b), (a,b+1), (a+1,b+1),(a+1,b+2)$, which represents $x^ay^b (1+y+xy+xy^2) = x^ay^b (1+y)(1+xy)$. Similarly, for a Z-tetromino that takes up squares $(a,b+1), (a+1,b+1), (a+1,b),(a+2,b)$, it represents $x^ay^b (y+xy+x+x^2) = x^ay^b (1+x)(x+y)$. The other orientation gives $(1+y)(x+y)$ Let $P(x,y) = \sum_{(a,b) \text{ in } P} x^ay^b$. Since it can be tiled with S-tetrominos, say $P = \sqcup_{(c,d)\in Q_1} \{ (c,d),(c+1,d),(c+1,d+1),(c+2,d+1) \} \sqcup \sqcup_{(c,d)\in Q_2} \{ (c,d),(c,d+1),(c+1,d+1),(c+1,d+2) \}$ (this is a disjoint union and $Q\subset \mathbb{N}_{\ge 0}^2$ is a set) then $P(x,y) = \sum_{(c,d)\in Q_1} (1+x)(1+xy)x^cy^d + \sum_{(c,d)\in Q_2} (1+y)(1+xy)x^cy^d = (1+xy)((1+x)Q_1(x,y) + (1+y)Q_2(x,y))$ Similarly, when we tile $P$ with $S$ and $Z$ tetrominos, we can write $$P(x,y) = (1+xy)((1+x)R_1(x,y)+(1+y)R_2(x,y)) + (x+y)((1+x)S_1(x,y)+(1+y)S_2(x,y))$$ Hence $$(1+xy)((1+x)(Q_1-R_1)(x,y)+(1+y)(Q_2-R_2)(x,y)) = (x+y)((1+x)S_1(x,y)+(1+y)S_2(x,y))$$ (Note the number of $Z$-tetrominos we use is $S_1(1,1) + S_2(1,1)$. ) Substituting $y=-\frac 1x$ into the above yields that $(1+x)S_1(x,-x^{-1}) + (1-x^{-1})S_2(x,-x^{-1})= 0$ for all $x\in \mathbb{C}\backslash \{-1,0,1\}$. Since for $e$, $x^e((1+x)S_1(x,-x^{-1}) + (1-x^{-1})S_2(x,-x^{-1}))$ is a polynomial with infinitely many roots, it is the zero polynomial, and thus, $(1+x)S_1(x,-x^{-1}) + (1-x^{-1})S_2(x,-x^{-1})= 0$ for all $x\in \mathbb{C}\backslash \{0\}$. Substitute $x=1$ gives $S_1(1,-1)=0$, and substituting $x=-1$ gives $S_2(1,1)=0$. Thus, $2\mid S_1(1,1)+S_2(1,1)$ because $S_1,S_2\in \mathbb{Z}[x,y]$

Did not think about adding colorings after USA TSTST 2023/3 oof Color the plane as follows 0010 0100 0111 1110 Check that an S-tetromino intersects an even number of cells labeled 1 and a Z-tetromino intersects an odd number of cells labeled 1. Hence $P$ has an even number of cells labeled 1, so every tiling must have an odd number of Z-tetrominoes. $\blacksquare$

Tile the plane with $4 \times 4$ square grids and color in the $1$'s \[\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}\]with each unit in the matrix being a grid cell. Then notice that each $Z$-tetromino overlaps with an odd number of colored cells and each $S$-tetromino overlaps with an even number. Since the total number of cells in $P$ is even(tiled with $4$-unit pieces), the number of $Z$-tetrominoes must be even. (really good problem, the solution makes it look much easier than it is)

Take the interpretation over ${\mathbb Z}[x,y]$. Let vertical $S$ dominos be $S_V(x,y) = y^2 + y + xy + x$. Define $S_H, Z_V, Z_H$ similarly. Then note that $(x + y) \mid S_V, S_H$ and $(1 - xy) \mid Z_V, Z_h$. By the problem statement we get equivalently that for some polynomials $A(x,y), B(x,y), C(x,y), D(x,y)$, that \[ A \cdot S_V + B \cdot S_H = C \cdot Z_V + D \cdot Z_H \]Then this implies that $(x + y) \mid C \cdot Z_V + D \cdot Z_H$. This means that $C(1, -1) Z_V + D(1, -1) Z_H = 0$, so $C(1, 1) Z_V + D(1, 1) Z_H \equiv 0 \pmod{2}$.

Color a cell $(x,y)$ red iff $(x,y)\equiv (0,0),(0,1),(0,3),(1,0),(1,1),(1,2),(2,0),(3,1)\pmod 4$. Then S tetrominoes cover an even number of red cells, so the total number of red cells covered is red. But each Z tetromino covers an odd number of red cells, done.