Республиканская олимпиада по математике, 2024 год, 9 класс

Бүтін $n>1$ саны берілген. Өлшемі $n\times n$ тақтасы ақ және қара түске шахмат бояуына боялған. Фигура деп тақтаның әртүрлі ұяшықтарынан құралған бос емес жиынды айтамыз. Егер $F_2$-ні тақтаның центріне қатысты $90^\circ$-қа бірнеше рет бұрып алып, одан кейін параллель тасымалдау арқылы $F_1$ фигурасын ала алсақ, онда $F_1$ мен $F_2$ фигураларын ұқсас фигуралар деп атаймыз. (Кез келген фигура өзіне ұқсас болып есептелінеді.) Егер $F$ фигурасының кез келген екі $a,b\in F$ ұяшығы үшін $c_1 = a$, $c_m = b$ болатындай $c_1,\ldots,c_m \in F$ ұяшықтар тізбегі табылып, әрі барлық $1\le i\le m - 1$ үшін $c_i$ және $c_{i+1}$ ұяшықтарының ортақ қабырғасы болса, онда $F$ фигурасын байланысқан фигура деп атаймыз. $k$-ның қандай ең үлкен мүмкін мәнінде, $F_1$ фигурасында ақ түсті ұяшықтар саны қара түсті ұяшықтар санынан артық, ал $F_2$ фигурасында керісінше, ақ түсті ұяшықтар саны қара түсті ұяшықтар санынан кем болатындай, $k$ ұяшықтан тұратын кез келген байланысқан $F$ фигурасы үшін $F$-ке ұқсас $F_1$ және $F_2$ фигуралары табылады? ( Зауытхан А. )

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

Понятно что для четных $n$ ответ $n^2-1$.

Пусть $n$ нечетное. Тогда если $k$ хотя бы $2n-1$ тогда покроем первую строку и первый столбец. И остальные клетки просто положим так чтобы они образовали связную фигуру. Понятно что при таком складывании нельзя делать параллельные переносы. (Уточнение в условии). И понятно что при нечетном $n$ поворачивать фигуру бессмысленно. Тогда такая фигура не подходит условию. Значит $k$ меньше $2n-1$. Если $k=2n-2$ то расставим $2n-2$ клеток по первой строке и по первому столбцу без крайней клетки. Тогда у нас одинаковое количество черных и белых клеток. И при переносе каждая клетка меняет свой цвет на противоположный. Таким образом их всегда одинаковое количество. Значит $2n-2$ не подходит. Докажем что $2n-3$ подходит. Легко понять что какой-то столбец и какая-та строка будет свободной. Значит можно использовать параллельный перенос. Так как $2n-3$ нечетное то у нас количество черных и белых клеток не равно. Тогда при переносе количество белых и черных и поменяется, значит цвета что было больше станет меньше, что подходит условию.