Математикадан 40-шы халықаралық олимпиада, 1999 жыл, Бухарест

Өлшемі $n\times n$ болатын тор көзді қағаз квадраттық кестесінің әрбір тордың(белгіленген немесе белгіленбеген) кем дегенде бір белгіленген көрші торы болатындай $N$ тор белгіленген, мұндағы $n$ — жұп сан. (Көршілес торлар деп қабырғалары ортақ торларды айтамыз.) $N$ санының мүмкін болатын ең кіші мәнін табыңыздар.

Комментарий/решение

В силу минимальности будем говорить что каждая клетка имеет ровно 1 закрашенную соседнюю клетку. Тогда заметим что закрашенные клетки образуют попарно различные доминошки, и отсюда можно понять что достаточно посчитать минимальное кол-во фигур которые состоят из домино и его соседей, тк за соседними клетками этих фигур тоже не могут стоят за крашеные клетки. Назовем такие фигуры как Anuar.

Раскрасим доску в два цвета так чтобы первый цвет закрашивал все края квадрата и потом так далее чтобы в конце остался квадратик 2 х 2. Закрасим именно первый цвет а второй не будем, тогда в каждой фигуре Anuar ровно 4 за крашеных клетом. Отсюда N равно кол во за крашеных клеток деленый на 4 и по индукции выводим ответ

$N = n/2 * (n/2 + 1)$