40-я Международная Математическая OлимпиадаРумыния, Бухарест, 1999 год

В квадрате клетчатой бумаги размером $n\times n$ клеток, где $n$ — четное число, отмечены $N$ клеток таким образом, что каждая клетка квадрата (отмеченная или неотмеченная) имеет хотя бы одну отмеченную соседнюю клетку. (Соседними считаются клетки, имеющие общую сторону.) Определите наименьшее возможное значение $N$.