20
$\begingroup$

There are two types of trominoes, straight shapes and L-shaped. Suppose a rectangle $R$ admits at least one tiling using trominoes, with an even number of L-trominoes.

EDIT: we do not admit ALL orientations, but only those which are constructed by starting in a box, and next box is placed to the left, or below previous box. Hence, only 2 out of the 4 possible orientations of the L-tromino is allowed. Hence, these are the four trominoes that we are allowed to use:

$$\begin{align}\newcommand{\x}{\large\blacksquare}\newcommand{\o}{\large\phantom{\square}} &\o\o\o\o\o\o\o\o\o\o\x\\[-5pt] &\x\x\o\o\o\o\x\o\o\o\x\\[-5pt] &\x\o\o\o\o\x\x\o\o\o\x\o\o\o\x\x\x \end{align}$$

Prove that every tiling of $R$ must use an even number of L-trominoes.

This smells a lot like a classical tiling problem, but unlike the classical cases (dominoes and missing corners), the situation is not to show that a tiling is impossible…. Some nice invariant is perhaps what I am looking for.

I actually know how to prove the above statement, but it requires a lot more machinery than I would like. Moreover, I am interested in a more general question, (regarding representation theory and cylindrical Schur functions, and the proof I know does not generalize to this situation), but I hope that a good proof of the above problem generalizes.

For the interested: The general setting supposes that the rectangle is a torus, and that we use $k$-ribbons, where $k$ is odd. We then want to show that the number of $k$-ribbons which occupies an even number of rows, occur an even number of times. Hence, a proof not relying on the fact that $R$ has boundaries, or heavily uses the fact that each shape has three squares, is of extra interest.

EDIT2: 2022-12-09 So, I am in the process of writing up a proof of this (and some other stuff).

Improve this question
$\endgroup$
30

1 Answer 1

Reset to default
0
$\begingroup$

Here is a start on a proof. I ask Per to finish it up.

The constraints allow me to color diagonals of the array in three distinct colors. (I choose a periodic pattern of red, green, and blue.) Two of Per's pieces remove one of each color, while the other two (because of how they orient and how I choose my diagonal coloring) cover two of one color and one of another. This imbalance should allow a parity argument for the L shaped pieces. Note this doesn't work if any of the other orientations are allowed.

Gerhard "Only Giving Half A Proof" Paseman, 2020.01.22.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm still seeing issues with this because I think of a strip of nested L pieces of one orientation spanning part of the torus. Perhaps Per has more of the picture and can use the idea of solving with this invariant anyway. Gerhard "Maybe He Can Force Herringbone" Paseman, 2020.01.22. $\endgroup$
    – Gerhard Paseman
    Jan 22, 2020 at 21:44
  • $\begingroup$ Indeed, if I use a three by three torus, I can tile it with three L shapes of the same orientation. Hopefully he can rule that and similar out. Gerhard "If Not One, The Other" Paseman, 2020.01.22. $\endgroup$
    – Gerhard Paseman
    Jan 22, 2020 at 21:47
  • 4
    $\begingroup$ Well, forget about the torus for the moment, but I am not convinced about the diagonal argument. You can have one type of L-piece, three copies with the 3 possible colorings. This is indistinguishable from three of the straight shapes. $\endgroup$
    – Per Alexandersson
    Jan 22, 2020 at 21:51
  • $\begingroup$ That is true, but if two L's are oriented in opposite fashion, there is only one configuration (up to color) that maintains equicolor balance. Gerhard "If You Look For Balance..." Paseman, 2020.01.22. $\endgroup$
    – Gerhard Paseman
    Jan 22, 2020 at 21:55
  • $\begingroup$ @GerhardPaseman. Your argument is not completely fruitless. With simple vector arithmetic it can be used to show that the numbers of the two L-shapes are congruent (mod 3). But nothing more than that. $\endgroup$
    – Yaakov Baruch
    Feb 21, 2021 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.