Покраска клеток.

[Sirion]

Окрасили бесконечный лист клетчатой бумаги, кроме квадрата $(2^n-1)\times(2^n-1)$. Вася в этом квадрате покрасил клетку, у которой ровно одна соседняя (по стороне) клетка окрашена, затем еще одну клетку, у которой теперь ровно одна соседняя клетка окрашена, и так далее. Какое наибольшее количество клеток таким образом может покрасить Вася?

[hippie]

Ответ: $\frac {2(2^n-1)(2^n-2)} 3.$

Больше клеток покрасить нельзя.
На каждом шаге полный периметр непокрашенной части увеличивается на 2. А при указанном количестве покрашенных клеток периметр непокрашенной части будет равен учетверённому числу непокрашенных клеток.

Нужная окраска строится следующим образом.
Строим 4 "отрезка" из окрашенных квадратов, соединяющих середину каждой стороны с центральной клеткой (сама центральная клетка при этом, естественно, не красится). При этом исходный квадрат разбивается на 4 меньших, размером $(2^{n-1}-1)\times(2^{n-1}-1).$ С ними поступаем точно так же. И т.д., пока не дойдём до квадратов размером $(2^1-1)\times(2^1-1),$ т.е. $1\times 1.$

[Sirion]

Воистину так.