Problem of the Month (June 2000)

This month we feature several problems about bent triominoes (which we will call L's) in a rectangle. We always assume that each L covers 3 grid squares of the rectangle, and the L's do not overlap.

Problem #1: How many L's will fit in an n×m rectangle?

Problem #2: How few L's can we put in an n×m rectangle so that no more will fit?

Problem #3: How few L's can we put in an n×m rectangle so that none of them can slide?

Problem #4: Two players take turns placing L's into an n×m rectangle, and whoever places the last one wins. Which player has the winning strategy?


ANSWERS

Problem #1:

Joseph DeVincentis and Philippe Fondanaiche completely solved this problem. When m or n is less than 2, clearly no L's will fit. Otherwise, mn/3 L's will fit, unless m=3 and n is odd, in which case only (mn/3 - 1) L's will fit. This is based on tiling most rectangles using 2×3 rectangles and the 5×9 rectangle below:

Brendan Owen gave some partial results, handling the cases when m or n is less than 2, and mn divisible by 6.

Problem #2:

Let F(n,m) be the fewest L's that can be placed in a n×m rectangle so that no more will fit. Also, let R(n) be the limit of F(n,m)/mn as m --> ∞.

Joseph DeVincentis and Philippe Fondanaiche conjectured the following bounds. DeVincentis managed to prove these conjectures for n≤3.

Fewest L's Needed to Block Rectangles

nF(n,m)R(n)
100
2(2m+5)/51/5
3(m+1)/21/6
42(m+1)/31/6
5m-11/5
6m1/6
7(5m+2)/45/28
8(3m-1)/23/16
9(5m+2)/35/27
102m-11/5
112m2/11
12(9n+2)/43/16

The 5×n and 7×n bounds are only good for large n. The 5×n results are based on extending the packings below:

The 7×7 is the only other rectangle (besides the 5×5) found that requires less than area/6 L's:

The 7×n results are based on joining one of these ends to repeated 7×4 rectangles:

Recently, Sasha Ravsky proved that R(n) -> 2/11 as n -> ∞. The tiling showing the upper bound is shown below. To see the lower bound, consider an mxn rectangle containing r rectangles so that no more will fit. There are four different 2×2 grids in the plane, so at least one of them contains at least p ≥ r/4 L's of the tiling. The rectangle contains at least k=(m-2)(n-2)/4 2×2 grid squares, and each 2×2 square must contain at least 2 unit squares of an L. Hence p + (2/3)(k-p) ≤ r or r ≥ (2/11)k.

He notes that this construction gives R(n) ≥ (2n-2)/(11n) for odd n. He modifies the construction to show that R(2n) ≥ 1/6, proving the values for R(4) and R(6). He also gives figures showing R(5) ≤ 8/45, R(8) ≤ 7/40, and R(10) ≤ 9/50. (He also showed R(5) ≥ 3/20.)

Problem #3:

Let S(n,m) be the smallest number of non-sliding L's that will fit inside an n×m rectangle.

Philippe Fondanaiche found S(n,n)=S(n,n-1)=n-1, and many generalizations of this, not all correct.

I can prove that S(n,2) = n/2 and S(n,3) = 2n/3. It appears that S(n,4) = 3n/4, and in general S(n,m) = (m-1)n/m for n much larger than m.

Here are the best known answers for small n and m:

Fewest Non-Sliding L's

m \ n2345678910
2122334455
3223445667
4233456678
5344457788
6345556999
745676671112
84667977813
95678911889
1057889121399

Problem #4:

This game is an impartial combinatorial game, so each position has a nim value, which is 0 if and only if the position is a second player win.

Nim Values of m × n Rectangles

m \ n234567
2120310
3201221
40101

Here are the winning moves from the 3×n and 4×n rectangles with a first player win:

Let R(n) be the nim value of an n×2 rectangle, let L(n) be the nim value of an n×2 rectangle with an extra square attached on one side, and let S(n) be the nim value of an n×2 rectangle with an extra square attached on both sides.

Nim Values of n × 2 Regions

n123456789 1011121314151617181920
R(n)012031043 30714031001
L(n)112231051 60714236401
S(n)110214051 20110234401

Is there some pattern here? What about for 3×n rectangles?

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 3/14/05.