I have joined a course and we are given the following questions, I am still a beginner btw.
Find the maximum number of 2×1 dominoes that can be placed on an 8 × 9 chessboard if six of them are placed as shown. A domino peace might be placed horizontally or vertically.
I tried to solve it and what I got that the maximum number of dominoes is 28 but how can I really be sure ?
I read somewhere on the internet that there is some sort of an algorithm to follow that will give you the maximum number of dominoes but is using it considered a valid answer ?
and how can I generalize ?
what are the strategies and tactics should I use to solve similar questions and any resources would be helpful !
Thanks
Consider what happens if you break this apart into two triangles of base and height equal to $7$ units, the triangle formed at the upper left and the triangle formed at the lower right.
Within the triangle, color the spaces as you would a checkerboard, alternating between black and white. There are $16$ black spaces (two of which at the border touching another available spot) and only $12$ white spaces or vice versa.
Even if the two available spaces at the border are used along with spaces beyond the border, that leaves $14$ black spaces with only $12$ available white spaces in the triangle. As every domino must cover exactly one black and one white space, that means that there will be at least two unused spaces for each side.
Even if we happen to use every other space as efficiently as possible, we will have at least two unused spaces per side for a total of four unused spaces overall for a theoretical maximum number of dominoes being $\left(8\times 9 - 4\right)/2 = 34$ which if we don't include the six already placed dominoes would yield $28$ potential additional dominoes we could place.
Since we have shown that this is an upper bound on the number of dominoes possible to place, all that remains is to show that it is actually achievable such as in this arrangement.
Therefore, the total number of dominoes we can place on this board is indeed $34$ if we count the six already placed or $28$ if we do not.