Международная олимпиада 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)