Problem

Source: 2024 CWMO P4

Tags: grid, combinatorics



Given positive integer $n \geq 2$. Now Cindy fills each cell of the $n*n$ grid with a positive integer not greater than $n$ such that the numbers in each row are in a non-decreasing order (from left to right) and numbers in each column is also in a non-decreasing order (from top to bottom). We call two adjacant cells form a $domino$ , if they are filled with the same number. Now Cindy wants the number of $domino$s as small as possible. Find the smallest number of $dominos$ Cindy can reach. (Here, two cells are called adjacant if they share one common side)