MathDB

2

Part of 2019 EGMO

Problems(1)

Yet another domino problem

Source: EGMO 2019 Problem 2

4/9/2019
Let nn be a positive integer. Dominoes are placed on a 2n×2n2n \times 2n board in such a way that every cell of the board is adjacent to exactly one cell covered by a domino. For each nn, determine the largest number of dominoes that can be placed in this way. (A domino is a tile of size 2×12 \times 1 or 1×21 \times 2. Dominoes are placed on the board in such a way that each domino covers exactly two cells of the board, and dominoes do not overlap. Two cells are said to be adjacent if they are different and share a common side.)
combinatoricsEGMO 2019