1
$\begingroup$

Let $2n\times 2n $ board. I cover it with dominoes $1\times 2$ s.t. every cell is adjacent exactly one cell coverd by a domino. I have to find the maximal number of dominoes that can be placed in this way.

I think that the number is $\frac { n\cdot (n+1)}{2} $. I succeed for $n\in \lbrace 1, 2, 3 \rbrace $ and I try to prove it by induction.

It's right my answer?

2 cells are adjacent if they share a common side

$\endgroup$
  • 3
    $\begingroup$ What do you mean by "every cell is ad[j]acent exactly one cell cover[e]d by a domino"? $\endgroup$ – Dr. Mathva Apr 9 at 10:12
  • $\begingroup$ @Dr. Mathva I added this information $\endgroup$ – Problemsolving Apr 9 at 10:26
  • $\begingroup$ It may be easier to solve the problem by induction on a $2n\times2m$ board instead. $\endgroup$ – P. Quinton Apr 9 at 10:39
  • $\begingroup$ @P. Quinton It's my answer right? $\endgroup$ – Problemsolving Apr 9 at 10:47
  • $\begingroup$ I think that it's is problem 2 form EGMO 2019 (first contest was yesterday). See here artofproblemsolving.com/community/… $\endgroup$ – richrow Apr 10 at 18:50
5
$\begingroup$

To show it is possible to place $n(n+1)/2$ dominoes, generalize the domino placements below.

enter image description here

To prove this is optimal, given a placement of dominoes, let

  • $x$ be the number of interior dominoes,
  • $y$ be the number of dominoes with both halves on the border,
  • $z$ be the number of dominoes with one half on the border and the other in the interior.

Note that a perimeter domino covers $4$ perimeter squares, and a half-interior domino covers at least three perimeter squares. Since there are $4(2n-1)$ perimeter squares total, we must have $$ 4y+3z\le 4(2n-1). $$ Furthermore, an interior domino covers $8$ squares, a border domino not on the corner covers $6$ squares, an a half-interior domino covers $7$ squares. There are at most $4$ corner dominoes, which each cover one fewer square. Therefore, $$ 8x+6y+7z\le 4n^2+4 $$ Putting this all together, we get \begin{align} x+y+z &=\frac18(8x+6y+7z)+\frac1{16}(4y+7z)-\frac{5}{16}z \\&\le \frac18(4n^2+4)+\frac1{16}(4(2n-1)) \\&= \frac12n(n+1)+\frac{1}{4} \end{align} Finally, since $x+y+z$ is an integer, we further conclude that $$x+y+z\le \left\lfloor\frac12n(n+1)+\frac14\right\rfloor=\frac12n(n+1).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.