MathDB

Given positive integers

m

and

n \ge m

, determine the largest number of dominoes (

1\times2

2 \times 1

rectangles) that can be placed on a rectangular board with

m

rows and

2n

columns consisting of cells (

1 \times 1

squares) so that: (i) each domino covers exactly two adjacent cells of the board; (ii) no two dominoes overlap; (iii) no two form a

2 \times 2

square; and (iv) the bottom row of the board is completely covered by

n

dominoes.

2