Q4 Matemática  (EGMO 2018)

Um dominó é uma peça de $1\times 2$ ou $2\times 1$. Seja $n\ge 3$ um inteiro. Os dominós são colocados em um tabuleiro $n\times n$ de forma que cada dominó cubra exatamente duas células do tabuleiro e os dominós não se sobreponham. O valor de uma linha ou coluna é o número de dominós que cobrem pelo menos uma célula dessa linha ou coluna. A configuração é chamada balanceada se existir algum $k\ge 1$ tal que cada linha e cada coluna tenha um valor de $k$. Prove que existe uma configuração balanceada para cada $n\ge 3$ e encontre o número mínimo de dominós necessários em tal configuração.