Европейская математическая олимпиада среди девочек (EGMO). 2018 год. Италия

Доминошка — это плитка $1 \times 2$ или $2 \times 1$. Пусть $n \geq 3$ — целое число. Доминошки размещаются на доске $n \times n$ так, что каждая доминошка закрывает ровно две клетки и доминошки не накладываются друг на друга. Весом столбца или строки назовём количество доминошек, которые накрывают по крайней мере одну клетку этого столбца или этой строки. Размещение называется сбалансированным, если найдётся число $k \geq 1$ такое, что каждый столбец и каждая строка имеют вес $k$. Для каждого $n \geq 3$ докажите, что существует сбалансированное размещение, и найдите наименьшее количество доминошек, которое необходимо для его получения.