Во время соревнования, что неудивительно, зная мои математические способности, не придумал идею для задачи D. Как уже было отмечено в других сообщениях, оптимальным в большинстве случаев будет ответ "солдаты не могут занять больше, чем пол площадки". Здесь чудесным образом всплывает раскраска плаца на квадратики "под шахматную доску". Я не буду рассматривать более "логичные" решения этой задачи, вроде паросочетания в двудольном графе; моя цель — доказать, прежде всего самому себе, что для больших досок нельзя изобрести ничего лучшего.

Заметим закономерность: каждый солдат (С) может "атаковать" (по аналогии с шахматами) до 8 клеток включительно:

-*-*-
*---*
--C--
*---*
-*-*-

Понятно, что, если он стоит на границе доски, то количество атакуемых клеток меньше.

Идея доказательства следующая: в данной расстановке, когда солдаты стоят в шахматном порядке, каждую пустую клетку, которая стоит как минимум на расстоянии 2 от края доски, атакует ровно 8 солдат. Допустим, наша расстановка не оптимальна, и какую-то пустую клетку можно атаковать аж 9-ю или более солдатами (таким образом, мы пытаемся увеличить общее количество солдат на доске). Здесь стоит остановиться и заметить, что 9-го солдата просто некуда поставить, в силу симметричности атакующих солдат и атакуемых пустых клеток (К):

-С-С-
С---С
--К--
С---С
-С-С-

Мы же не можем, не имеем права ставить двоих солдат в 1 клетку!

Так как нас интересуют только большие доски, а отношение краев доски к ее середине стремится к нулю в пределе при больших размерах досок, то можно считать, что все хорошо, мы решили, что заполнять центр доски можно и нужно в шахматном порядке. Что делать с краями — остается рамочка шириной в 2 клетки... Если нарисовать ту же шахматную расстановку для крайних клеток, то получится, что и здесь каждая пустая клетка атакована максимально возможным количеством солдат.

Это доказательство не совсем строго (даже совсем не строго). В частности, интересно, как доказать формально, что из того, что все пустые клетки атакованы по максимуму вытекает то, что больше солдат поставить нельзя. Также я не рассмотрел случаи с маленькими досками (размеры 1×x, 2×x), на которых, мягко говоря, все вышесказанное не действует.

P. S. кажется, вспомнил, где я мог видеть это доказательство... Это "Детская энциклопедия Математика". То-то я думал, что у меня дежавю с этой задачей :), а ведь открывал я эту книгу последний раз лет 6 назад.