Personally Attacked by Squares in a Bathroom

Question

Well, this is a bit of a mess!

Your bathroom has a rectangular floorspace of size $xn$ by $yn$, where $x, y, n$ are all positive integers, and now that you've removed those ghastly yellow and purple tiles, you need to redo the entire floorspace.

You love thin rectangles, so you've ordered a huge batch of 1 by $n$ rectangular tiles, and you're going to use these to tile the entire floorspace (in this highly unrealistic bathroom, apparently toilets, drains, baths and showers don't affect the area you need to tile).

Can you tile your bathroom floor completely without any overla - of course you can, that wouldn't be puzzling at all, would it? In fact, you made quick work of the tiling and have already tiled your bathroom floor.

But you've noticed, that in your tiling, somewhere in your room there is an $n * n$ square which completely contains exactly $n$ tiles of the same orientation.

(Here's an example visual, with $n = 6$.)

(Ugh, squares)

You don't like squares, so you try to tile it again without making an $n*n$ square. But you fail. Again and again. You feel like this is a personal attack. From squares.

Now, is it possible to tile your bathroom floor completely, with no overlaps, and no partial tiles, such that there exists no $n*n$ square?

Answer 1

We will use:

Proof by contradiction.

So,

By way of contradiction, assume there exists a floor tiling without an $n\times n$ square.

Then,

Without loss of generality, assume the floor tile in the top-left corner is placed vertically (looking from above). Like this:

So,

we must have at most $n-1$ tiles placed vertically along the top edge in a row. Then, the tile in this corner (next image) must be placed horizontally:

Aha! Now,

continuing down the side of the last vertical tile, we have at most $n-1$ horizontal tiles. Then the tile in this corner (next image) must be placed vertically again:


We know that this corner exists, because there are $\le n-1$ horizontal tiles, of width $1$, taking up at most $n-1$ rows, but the vertical tiles take $n$ rows.

But then,

We can use some induction-y stuff (I'm not going to write it out formally), but it is easy to see that every time you put $\le n-1$ tiles, there will be another corner. This is because the last tiles you placed were $n$ rows/columns long and $\le n-1$ tiles could only take up at most $n-1$ rows/columns, so you have to place another tile to fill the corner.

But since the corner moves by at least $1$ row/column each step from the tile we have to place, the corner moves out of your bathroom and the tiles stick out of the bathroom, which is not allowed. Contradiction.

Q.E.D.