Cover the terrace with "slashed" tiles

Question

Peter has a rectangular terrace with integer sides. He plans to tile this terrace, with the ultra-modern 'slashed tiles". Each tile is a $2\times 1$ rectangle, with a diagonal, called its "slash". A tile can be rotated or reflected.

$\qquad\qquad\qquad\qquad\qquad\qquad$

But there's a catch: if two there are two tiles such that their slashes meet at a common point, the whole terrace will blow up.

$\qquad$

For example, the configuration on the left is OK, but in the configuration on the right, the two slashes meet at a point (circled in red), which is not allowed.

Moreover, Peter wishes that each of the four corners of his terrace must be the endpoint of some slash.

Question: Is it possible to tile the terrace according to his wishes, without breaking/ overlapping tiles/ cheating or blowing it up?

---

_{Source: Tournament of Towns.}

Answer 1

It is

Impossible

as demonstrated by this image:

Consider the above image, where dots indicate the endpoints of slashes, and the red lines are edges of the terrace. First, we will prove that there exist tiles (2) and (3) such that a short side of (2) and a long side of (3) touch the same edge, with them sharing an intersection. We will also prove that these tiles are arranged such that their intersection at the wall does not contain an endpoint from either tile.


Start with Tile (1), defined as the tile touching the bottom right corner. We can assume the orientation of this tile without loss of generality, since we know it has an endpoint in that corner, and the two such options are mirror images of each other across the diagonal of the terrace. Now, imagine that there are no horizontal tiles that touch the right side edge of the terrace - in this case, all the vertical tiles along this edge must be in the same orientation to avoid touching endpoints. But this would preclude there from being a tile in the upper right that had an endpoint in that upper right corner. Thus, we know that there exists some tile such that it is horizontal, and touches the right edge of the terrace. Let (2*) stand for the first such tile found when going from bottom to top. We do not, as of yet, know its orientation - the slash could go either direction.


If this tile (2*) had its endpoints in the bottom left and upper right, then it and the title below it - a tile we know shares orientation with tile (1) - would fit the restrictions we originally set out to prove existed. (2*) would be horizontal and against the edge while touching some tile (3*) in the same orientation as (1) which is vertical and against the edge, and neither would have an end point at the intersection. Thus (2*) would be (2) in the diagram, and (3*) would be (3).

If this is not the case, then the only possible orientation for (2*) is with endpoints in the top left and bottom right. In this case, we know that (2*) is not the topmost tile, because it couldn't have an endpoint in the upper right corner. We also know that there must be some vertical tile above (2*) - if it were horizontal tiles all the way up, they'd all have to be in the same orientation. But we know even further - if the first vertical tile above (2*) on the right edge is in the same orientation as 1, then there must be another horizontal tile above it, following the same reasoning that deduced the existence of (2*) from (1). The result of all this is that there must be some horizontal tile above (2*), such that it shares orientation with (2*) and is immediately below a vertical tile which does not share an orientation with (1). Call these tiles (2) and (3) respectively. (3) may or may not be a corner tile; it's irrelevant.


We have now found our tiles which fit the original description - either (2*) and the tile below it sharing an orientation with (1), or another such pair above it, are (2) and (3). The notable features are all shown in the original picture - (2) is a horizontal tile with endpoints in the upper left and bottom right, while (3) is a vertical tile with endpoints in the upper right and bottom left - they also both touch each other and the right hand edge (where neither has an endpoint).


Next, observe that tile (4) is the only safe tile that can touch the corner created by (2) and (3). Both vertical tiles and the other horizontal orientation would both touch an endpoint of (2) or (3). So, given that (2) and (3) exist, (4) must exist, because that space above (2) would need to be filled in somehow.


But the same logic demonstrates that (5) must exist, as the only legal tile that can fit below (4). And then (6) must exist as well! You can probably see where this is going - there can never be a left hand edge to our terrace, because the row containing (2) and the row above it must both contain horizontal tiles, offset by one, off into infinity. Given the terrace to be of integer (finite) size, this is a contradiction. Thus tiles (2) and (3) can't exist, which means tile (1) can't exist, which means we can't tile our terrace at all. Sucks to be Peter!

Answer 2

I suggest another proof to a more generalized question.
I.e. We could omit the restriction that a tile in the terrace should be of size $2 \times 1$ and assume any size. also, omit the restriction that the terrace sides should be of integer lengths.

Thus we could rephrase the question:

"Peter has a rectangular terrace with integer sides . He plans to tile this terrace, with the ultra-modern 'slashed tiles". Each tile is a 2×1 rectangle with a diagonal, called its "slash". A tile can be rotated or reflected."

But there's a catch: the case that two tiles such that their slashes meet at a common point is not allowed.

prove that all slashes in the terrace have the same orientation. i.e. there can be only 2 cases:

1. all slashes have end point in the upper left corner in each rectangle or
2. all slashes have end point in the upper right corner in each rectangle

this is a stronger statement then the original statement because it yields that exactly 2 opposite corners of the 4 corners of the terrace have slash endpoints.

Proof:

I will prove that every two adjacent tiles have the same slash orientation. this will prove indeed the theorem, because the whole terrace could be built from adjacent tiles.

By adjacent tiles I mean 2 tiles which have a common edge or part of their edge is common.

Assume we have 2 adjacent tiles red and green. as in this figure.

in the figure the common segment between those tiles is colored yellow. We now consider the longest segment in the terrace tilling that contains the yellow segment. this segment is the horizontal segment in the figure between the 2 blue nodes labeled a and b in the figure.

• define rectangles$_1$ to be the rectangles above the segment $ab$ which have edges along the segment $ab$.
• define rectangles$_2$ to be the rectangles below the segment $ab$ which have edges along the segment $ab$.
• define $V_1$ to be the set of all the vertices of rectangles$_1$ that resides on segment $ab$
• define $V_2$ to be the set of all the vertices of rectangles$_2$ that resides on segment $ab$.

notice that in the figure here:

• all common vertices of $V_1$ and $V_2$ are colored blue.
• all vertices of $V_1$ but not in $V_2$ are colored red.
• all vertices of $V_2$ but not in $V_1$ are colored green.

Define $D_1,D_2$ the endpoints of slashes on segment $ab$ by:

• $D_1$ is the set of all vertices which are the lower end point of a slash in rectangles$_1$.
• $D_2$ is the set of all vertices which are the upper end point of a slash in rectangles$_2$.

Now its easy to see that the number of vertices in $D_1$ is the number of vertices in $V_1$ minus 1, or in set notation $|D_1|=|V_1|-1$. (this is because $|D_1|$ equals the number of rectangles in rectangles$_1$ which is the number of vertices in $V_1$ minus 1.) Similarly, $|D_2|=|V_2|-1$

From here its not hard to prove that either:

1. $a\in D_1$ and $b\in D_2$. and its not hard to prove that in this case all slashes in rectangles$_1$ and rectangles$_2$ are upper-right to bottom-left. In particularly, the adjacent rectangles we started with have the same slash orientation. or

2. $a\in D_2$ and $b\in D_1$. and its not hard to prove that in this case all slashes in rectangles$_1$ and rectangles$_2$ are upper-left to bottom-tight. In particularly, the adjacent rectangles we started with have the same slash orientation.