Фишки на шахматной доске

[MuwxaT_wuHauM]

На шахматной доске расставлены n фишек так, что в любом квадрате 3*3 находятся ровно 3 фишки.
a) При каком наибольшем n это возможно?
b) При каком наименьшем n это возможно?

[Equinoxe]

a)
1. Рассмотрим доску 9х9, её можно разбить на непересекающиеся квадраты 3х3, в каждом из которых, по условию, 3 фишки, выходит, максимум для 9х9 — 27
2. Теперь рассмотрим любую валидную доску 8х8, дорисуем справа и снизу рядок, чтобы превратить её в 9х9 (не обязательно валидную).
В каждом квадрате теперь <=3 фишки, т.е. если вдруг n>27, в каком-нибудь квадрате точно больше 3х фишек и получилось противоречие. Выходит, ответ <= 27.
27 достигается, например, так:

[Equinoxe]

б) Первая оценка, которую мы получим — 12, т.к. квадрат 8х8 содержит квадрат 6х6, который можно поделить на квадраты 3х3.


Пусть этот квадрат 6х6 будет самым левым верхним (синий).
Рассмотрим теперь квадрат, отмеченный зелёным. Ясно, что от синего он получит не более, чем 1 фишку (она будет на синезелёной клетке), а значит нужны как минимум ещё две. Теперь оценка — 14


Рассмотрим теперь 2 квадрата, отмеченных красным (в пересечниях с синим — фиолетовым)
Ясно, что в случае 14-ти фишек все фиолетовые должны быть покрыты. Однако тогда жёлтый квадрат должен покрыть фишками как квадрат между желтым и одним красным, так и между желтым и другим красным, что в сумме — 5 фишек, а можно лишь 3. Значит, в сумме красные квадратики синей областью можно покрыть не более чем на 4 фишки, но т.к. нужно 6 (3+3), придётся добавить ещё две в красную область, не принадлежащую синей. Растянули оценку до 16.

А вот и рисунок для 16: