Processing math: 100%

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


Дано целое число n>1. Доску n×n раскрасили шахматным образом в белый и черный цвет. Фигурой назовем любой непустой набор различных клеток доски. Фигуры F1 и F2 назовем подобными, если F1 можно получить из F2 с помощью поворота относительно центра доски на угол кратный 90 и параллельного переноса. (Любая фигура подобна самой себе.) Фигуру F назовем связной, если для любых клеток a,bF найдется последовательность клеток c1,,cmF такая, что c1=a, cm=b, а также ci и ci+1 имеют общую сторону для каждого 1im1. Найдите наибольшее возможное значение k такое, что для любой связной фигуры F, состоящей из k клеток, найдутся фигуры F1,F2 подобные F, что в F1 белых клеток больше, чем черных, а в F2 белых клеток меньше, чем черных. ( Зауытхан А. )
посмотреть в олимпиаде

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

  6
11 месяца 6 дней назад #

Понятно что для четных n ответ n21.

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

  0
21 дней 12 часов назад #

cycf(a,b,c)=f(a,b,c)+f(b,c,a)+f(c,a,b)

cyca2b=a2b+b2c+c2a