Ещё одна задача от А. В. Шаповалова и К. Л. Шейнерман

[Xenia1996]

В какое наибольшее число цветов можно раскрасить шахматную доску так, чтобы каждая клетка граничила по стороне хотя бы с двумя клетками своего цвета? (Каждая клетка закрашивается целиком в один цвет.)

Решить задачу для доски:

а) $8\times 8$

б) $9\times 9$

в) вывести общую формулу для доски $n\times n$

[zhekas]

$$\left(\left[\frac{n}{2}\right]\right)^2$$