only proved a), I think my proof is correct. I proved by doing "move"s(every time you meet a distasteful tiling, you turn the direction of that 4 cells' tiling), after each move, you will get a completely new arrangement of tiling.(For this part, I suppose if an arrangement will appear twice, then let it be the initial arrangement, now I put 1 counter in the 4 cells after each move, which means after some moves all the cells will have an even number of counters in it. Since we never do "move" at the same 4 cells continuously, every time there will be a new cell which the counter turns from 0 to 1. Eventually it will get to the 4 corner cells. But it's obvious that the 4 corner cells can only be moved at most once. Which means there will always be some cells with odd counters in it. Which means no arrangement will appear twice). After each move, the number of distasteful tilings may change or not, but the point is if it never gets to 0, it means it will always be a possible "next move", which means there will be a new arrangement. Since the total arrangement number is limited, the number of distasteful tilings have to get to 0 after some moves.

That's what I did, but I said that every 2x2 square cannot be "moved" back to its original position, so if some specific 2x2 square is distasteful, it can never be distasteful again, similarly with any other 2x2 square. So therefore, this process must be finite, and eventually it will become tasteful.

Had anyone solved part b?

This is a bit hard to explain without a picture, but I'll try anyways. Solution by Paul Christiano.

Basically, the only way to tile them tastefully was to start in the middle and layer the other tiles outward, if you know what I mean. I also tried to prove that was the only way by doing l W G l G W and showing that there was no possible way to create a square corner while avoidind distaste. The way to tile them was: l W G l W G l W G l... (2 rows if needed) in the middle. When you add an outer layer, they are staggered, so there is no possible distaste since there are no 2 x 2 squares. Kinda hard to explain w/o picture.

The solution seems good. Thanks! By the way, had Paul Christiano solved every single problem? If so then he may get perfect! wow!

Paul was a senior last year. He's at MIT now, so I assume he was just trying the problems for fun. The solution seems nice, but I don't understand the part about the forced squares and the diagonal.

I have a very neat existence proof: Choose a number $ r>1$. Assign to the tile with lower left corner at $ (a,b)$ the weight $ (-r)^{a+b}$. Shade the squares with positive weight, noting that they are at locations with $ a+b$ even. Sum the weights of all tiles, multiplied by $ 1$ for those in horizontal dominos and $ -1$ for those in vertical dominos. A $ 2\times 2$ distasteful block with lower left corner at $ a+b$ contributes $ -r^{a+b}(r-1)^2$, while its tasteful counterpart gives $ r^{a+b}(r-1)^2$. There are finitely many possible sums, and finitely many tilings, so some tiling has a maximal sum. If this maximum had any distasteful blocks, we could reverse them to increase the sum. This doesn't happen, so the maximum is tasteful tiling. - JSteinhardt: I'm not at all convinced that that argument handles irregular grids. If that "upper left" tile isn't uppermost, we may be able to escape- in particular, if the tile one spot up and one to the right is in the grid, we can put a vertical tile there. Then that tile might not even be a corner...

Very elegant proof. But does it address part b)?

No, it doesn't. The method doesn't rule out two local maxima. I've been working on part (b); so far I can say a lot about the structure of a minimal counterexample, but I can't rule it out completely. Uniqueness is false if we allow holes in the middle, by the way.

So I guess I forgot to add in a few lemmas that I thought weren't needed, but now I realize you do. Essentially if there is anything that is adjacent to only one other square then there is only one possible way that you can place a tile to cover that square, so we can rule out all those cases. Then if we consider the top row and go as far left as possible we can safely apply the same argument as before from that square. EDIT: Nevermind I see your objection, if I do that then my WLOG is no longer appropriate because I've broken symmetry.

I think I've made the breakthrough I needed.

Those fake pictures were a pain, but it's unreadable without something. Does anyone know a better (longer) horizontal dash symbol in $ \text{\LaTeX}$? [Added in edit] krakola45 wrote: ...but I said that every 2x2 square cannot be "moved" back to its original position, so if some specific 2x2 square is distasteful, it can never be distasteful again Not true. In large polygons, many of the distasteful blocks will return; in a $ 2n\times 2n$ square, it takes $ n+8\binom{n+1}{3}=\frac{n(8n^2+6n-8)}{6}$ moves to go from the worst arrangement (no tasteful $ 2\times 2$ blocks) to the best, or half that from a random tiling to the tasteful tiling on average. The average number of times each $ 2\times 2$ block is moved is proportional to the linear size, and a block in the middle can move twice in something as simple as a $ 4\times 4$ board. I have a feeling that a lot of people are wrong in subtle ways, and didn't solve as much of this problem as they thought.

Jmerry, I think you need to be more rigorous on what you mean by "some lower left corner." Some polygons don't have a "lower left corner." Do you mean the square for which $ a+b$ is a minimum?

The definition of a lower left corner: any square in the polygon for which neither the square directly below nor the square directly to the left is in the polygon. Every polygon must have at least one, and some polygons have many. Minimizing $ x+y$ would make the argument simpler, though. In that case, we can't keep going down in case (b).

Whoa, looks like you've used a similar approach to my original one, but I was not satisfied with the casework involved.

The first two parts look good. The hamster will get confused when it runs into the middle of a tasteful block- remember, those are really just the same as distasteful blocks except for coloring. That idea also needs an argument that there are no tasteful blocks inside.

Ahh, but it misses all of those because of how rhythmically it is running. If you set the first step correctly, it should exactly be a question of whether there is a distasteful block obstructing it every time, and there should be no problems.

Lol hamsters... if only I had the liberty not only to write a boilerplate proof in the given time but also to add humor to it...

I see now. The specific fix: go horizontally if the tile to the upper right is shaded, and vertically if it's unshaded. You can enter the middle of a distasteful block that way, but not a tasteful block. Yongyi781 wrote: Lol hamsters... if only I had the liberty not only to write a boilerplate proof in the given time but also to add humor to it... Well, we're not working in real time here. The last time I actually competed in the USAMO was 2000, and I first saw these problems Thursday morning.

azjps wrote: We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $ x = a$ or $ y = b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner. [asy][asy]size(100); pathpen = linewidth(2.5); void chessboard(int a, int b, pair P){ for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle); } chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12)); /* draw lines */ D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy][/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully. b) Prove that such a tasteful tiling is unique. Can any chessboard polygon with even size bigger or equal to 4 be tiled uniquely tastefully?

A polygon in the shape of a "T" Tetris piece can't be tiled with dominoes at all.

Weirdly, a shape consists of a 3*3 square without the central square doesn't have unique tiling. AAC B C BDD BAA B C DDC I don't think this is a polygon in strict definition. But obviously any correct proof needs to address this.(i.e. contains some argument regarding to no "holes" inside) Anyone notice this?

The assumption that the polygon has no internal gaps is critical to the proofs that do "suppose there are two tilings, take a 'cycle' of dominoes on which they differ, and get a contradiction using the interior."

Here's (hopefully?) another proof for uniqueness. (I'm sure it's similar in spirit to other things above, so sorry for reviving if it's a bit redundant. Most of it is just setting up for the last few paragraphs.)

Edit: OK so I was looking at these necessary and sufficient conditions for domino tilings to exist (since I thought they could simplify my roundabout way above), and it seems that Thurston's height function (which applies to chessboard polygons here; see section 4 here) provides a very natural setting for this problem (it's pretty close to what probability1.01 did, but I guess more unified), since it embodies the notion of path orientation really well (in any path with height changing $+1\pmod{4}$ from one vertex to the next, the color of the square on the left remains the same). The idea is that if we set the height function to be 0 at some arbitrary point on the boundary, then there's a unique "maximal" tiling, which must be tasteful. For more details, refer to this paper, which also explores a lot further (if you can't access it most of the ideas are here).

@mathcool2009: the chessboard polygon need not be a rectangle.

Here is the proof of (a) from the official solutions, by induction: let $\mathcal P$ denote the chessboard polygon which can be tiled by dominoes. Consider a lower-left square $s$ of the polygon, and WLOG is it black (other case similar). Then we have two cases: If there exists a domino tiling of $\mathcal P$ where $s$ is covered by a vertical domino, then delete this domino and apply induction on the rest of $\mathcal P$. This additional domino will not cause any distasteful tilings. Otherwise, $s$ is covered by a horizontal domino. Again delete this domino and apply induction on the rest of $\mathcal P$. The resulting tasteful tiling should not have another horizontal domino adjacent to the one covering $s$, because otherwise we could have replaced that $2 \times 2$ square with two vertical dominoes to arrive in the first case. So this additional domino will not cause any distasteful tilings.

Here is my proof of (b): Suppose for contradiction there are two distinct tasteful tilings. Overlaying the two tilings on top of each other induces several cycles of overlapping dominoes at positions where the tilings differ. Henceforth, it will be convenient to work with the lattice ${\mathbb Z}^2$, treating the squares as black/white points, and we do so. Let $\gamma$ be any such cycle and let $s$ denote a lower left point, and again WLOG it is black. Orient $\gamma$ counterclockwise henceforth. Restrict attention to the polygon $\mathcal Q$ enclosed by $\gamma$ (include points of $\gamma$ as part of the tiling). In one of the two tilings of $\mathcal Q$, $s$ will be covered by a horizontal domino; in the other tiling $s$ will be covered by a vertical domino. We focus on the latter one. Observe that we now have a set of dominoes along $\gamma$, such that $\gamma$ points from the white point to the black point within each domino. Now impose coordinates so that $s = (0,0)$. Consider the stair-case sequence of points $p_0 = s = (0,0)$, $p_1 = (1,0)$, $p_2 = (1,1)$, $p_3 = (2,1)$, and so on. By hypothesis, $p_0$ is covered by a vertical domino. Then $p_1$ must be covered by a horizontal domino, to avoid a distasteful tiling. Then if $p_2$ is in $\mathcal Q$, then it must be covered by a vertical domino to avoid a distasteful tiling, and so on. We may repeat this argument as long the points $p_i$ lie inside $\mathcal Q$. (See figure below; the staircase sequence is highlighted by red halos.) Let $x$ denote the first point of this sequence after $p_1$ which is on $\gamma$, and WLOG that point is white (black case is similar). Let $y = p_1 = (1,0)$ so the line segment $\ell$ joining $xy$ has slope $1$ (in the black case use $y=(0,0)$ instead). Now $x$ is tiled by a vertical domino whose black point is to the right of $\ell$. But the line segment $\ell$ cuts $\mathcal Q$ into two parts, and the orientation of $\gamma$ has this path also entering from the right. This contradicts the fact that the orientation of $\gamma$ points only from white to black within dominoes. This contradiction completes the proof.

@v_Enhance how do you make those cool diagrams

Asymptote

I'm confused, isn't the first one a "distasteful tiling" as well?

awang11 wrote: I'm confused, isn't the first one a "distasteful tiling" as well? No, the color of the squares matters in the definition of the two illegal configurations.

hello everyone, I am new in this program. I love math a lot and i'm pretty good at it...sometimes. Can anyone please explain the question to me. I was lost. If a polygon is a closed figure why are it's sides situated on lines that pass through the interior of said polygon. and if it divides into unit suares why do i see 1x2 rectangles 9white and grey)?

Kalymat wrote: hello everyone, I am new in this program. I love math a lot and i'm pretty good at it...sometimes. Can anyone please explain the question to me. I was lost. If a polygon is a closed figure why are it's sides situated on lines that pass through the interior of said polygon. and if it divides into unit suares why do i see 1x2 rectangles 9white and grey)? If you are new to olympiads I would not recommend starting with a 45m problem

An unsolved idea. For each domino, place an arrow pointing from white to black, so the bad $2\times 2$ squares are all counterclockwise.