A tromino is a 1 x 3 rectangle. Trominoes are placed on an n x n board. Each tromino must line up with the squares on the board, so that it covers exactly three squares. Let f(n) be the smallest number of trominoes required to stop any more being placed. Show that for all n > 0, n2/7 + hn ≤ f(n) ≤ n2/5 + kn for some reals h and k.
Solution
A tromino may be placed in n - 2 positions in each row and column, so there are 2n2 - 4n possible positions in total. Placing a tromino occupies or blocks at most 14 of these positions (5 parallel and 9 perpendicular). Hence any placement of (2n2 - 4n)/14 = n2/7 - 2n/7 trominoes will block further trominoes. So f(n) >= n2/7 - 2n/7.
If we place trominoes roughly like this:
x x x o o x x x o o x x x o o x x x o o x o x x x o o x x x o o x x x o o x x x o o o o x x x o o x x x o o x x x o o x x x o x o o x x x o o x x x o o x x x o o x x x x x o o x x x o o x x x o o x x x o o x x x x x o o x x x o o x x x o o x x x o o xit is obvious that no further trominoes are possible and the number of occupied squares is about 3n2/5. Hence the number of trominoes is about n2/5. But we need to do some tidying up in relation to edge effects.
The safe way to deal with partial trominoes at the beginning or end of rows is to pull them completely onto the board. Each complete group of five cells in a row needs a tromino, but we may need one extra at the start and one extra at the end. So [n/5] + 2 will always suffice for the row. Thus n2/5 + 2n will suffice for the board and so f(n) ≤ n2/5 + 2n.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002