Международная олимпиада 2025, Саншайн-Кост (Квинсленд), Австралия, 2025 год

Рассмотрим сетку размером $2025 \times 2025$ из единичных квадратов. Матильда хочет разместить на сетке несколько прямоугольных плиток, возможно, разных размеров, так, чтобы стороны каждой плитки лежали на линиях сетки, а каждый единичный квадрат был покрыт не более чем одной плиткой.
   Определите минимальное количество плиток, которые Матильде нужно разместить так, чтобы в каждой строке и каждом столбце сетки был ровно один единичный квадрат, не покрытый ни одной плиткой.

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

выберем диагональ (1 1) (2 2) .... (n n)

эти клетки лежат в разных строках и столбцах допустим перестановка

Теперь их нужно покрыть плитками но при этом сами плитки будут покрывать и другие клетки так что надо следить чтобы осталиные тоже не покрывались и нигде не было двух покрытых клеток в одной строке или столбце

n^2 это всего клеток в сетке

диагональных клеток n

значит

клеток вне диагонали n^2-n и мы кладем на них ровно n^2-n плиток размером 1 на 1

каждая такая плитка не мешает потомучто она покрывает одну клетку вне диагонали -> в каждой строке и столбце у нас пока одна не открытая диагональная

Теперь хотим покрыть диагональные клетки так чтобы не нарушить ограничения

Если мы просто покроем каждую диагональную клетку 1 на 1 то это добавит еще n плиток и итог будет такой

n^2 -n+n=n^2

можно попробовать вместо n маленьких плиток покрыть диагонали покрыть двумя длинными плитками

Разобьем диагональ на две части

(1 1) (2 2) ..... (n-1,n-1)

Последнюю клетку (n n)

Теперь на первую часть (первые n-1 клеток) кладем одну плитку размером (n-1)(n-1) которая охватывает весь верхний квадрат

Она захватывает сразу все диагональные клетки от (1 1) до (n-1,n-1) последнюю клетку (n n) покрываем одной отдельной плиткой 1 на 1

Но теперь мы перекрыли квадрат (n-1)(n-1) а там уже стояли 1 на 1 плитки с предыдущего шага

Значит мы можем удалить все эти плитки 1 на 1 с предыдущего шага

Значит мы можем удалить все эти плитки из этого квадрата (они уже покрыты большой плиткой)

Сколько таких плиток удалилось

Внутри квадрата (n-1)^2 клеток

Мы положили туда раньше (n-1)^2-(n-1) плиток (все кроме диагонали)

Сейчас все это покрыто одной плиткой и мы экономим (n-1)^2-(n-1) плиток

Теперь сложим все

Считаем начально n^2-n

Плюс две плитки на (n n)+одна большая одна =2

Минус (n^2-1)-(n-1)= -((n^2-1)-(n-1))

итого после сложения и раскрытия скобок выйдет

n^2-n+2-n^2+3n-2=2n но это только экономия а нас интересует общее количество плиток

1 Положили n^2-n 1 на 1 плиток вне диагонали

2 Положили n плиток 1 на 1 на диагональ (по одной)

3 Потом сэкономили 3 плитки путем замен трех 1 на 1 плиток на одну 3 на 3 плитку (ключевая техническая оптимизация)

4 В сумме получается (n^2-n)+n+2n-3=n^2+2n-3

Также можно решить начав с клетки 9 × 9 и разместить отверстия на координатах (1;3), (2;6), (3;9), (4;2), (5;5), (6;8), (7;1) (8;4) (9;7) и увидим что между отверстиями у нас есть 4 квадрата с площадями 3×3 далее уже не трудно догадаться что количество плиток можно найти выражением (n-1)^2+4(n-1)=

=n^2+2n-3 это и есть ответ и он будет такой же и у сетки 2025×2025 т.к

2025=0 (mod 9) -->

2025^2=0 (mod 9^2)