7
$\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{matrix} \blacksquare & \blacksquare \\ \blacksquare & \\ \end{matrix} ,\qquad \begin{matrix} \; & \blacksquare \\ \blacksquare & \blacksquare \\ \end{matrix} ,\qquad \begin{matrix} \blacksquare \\ \blacksquare \\ \blacksquare \end{matrix} ,\qquad \begin{matrix} \blacksquare & \blacksquare & \blacksquare \end{matrix} $$

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.

$\endgroup$
  • 2
    $\begingroup$ hm really? matematika-shkolnikam.ru/43.jpg $\endgroup$ – Fedor Petrov Jan 22 at 10:18
  • 3
    $\begingroup$ Also, since $3$ is prime, the sizes are $m\times n$ where one is divisible by $3$, so you always have a tiling with no L's which is even. $\endgroup$ – Ville Salo Jan 22 at 10:34
  • 2
    $\begingroup$ I guess the tag should be tiling, not tilting. $\endgroup$ – Dag Oskar Madsen Jan 22 at 10:38
  • 2
    $\begingroup$ A more general theory is due to Igor Pak, ams.org/journals/tran/2000-352-12/S0002-9947-00-02666-0/…. $\endgroup$ – Richard Stanley Jan 22 at 15:06
  • 1
    $\begingroup$ Have you looked at diagonals skewed to your pieces? (Two of the pieces occupy 2 squares of a certain diagonal direction, while the others occupy only one;alternatively,two pieces lie within two diagonals, whereas the others cross three diagonals.) Gerhard "Hoping For A New Slant" Paseman, 2020.01.22. $\endgroup$ – Gerhard Paseman Jan 22 at 20:54
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.

$\endgroup$
  • $\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 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 at 21:47
  • $\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 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 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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