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?
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.
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.
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.)
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:
|m \ n||2||3||4||5||6||7||8||9||10|
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.
|m \ n||2||3||4||5||6||7|
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.
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.