комбинаторика - Расстановка слонов

Рассмотрим все диагонали доски, включая те, которые состоят из одной клетки. Они все параллельны одному из двух направлений, и для каждого из таких направлений диагоналей имеется ровно $%19$%. Из этого следует, что более $%19$% слонов разместить требуемым образом нельзя. Более того, нельзя разместить и $%19$%, так как в этом случае каждая диагональ будет занята одним слоном, и тогда на двух угловых диаметрально противоположных клетках будет по слону, но это невозможно.

Итак, $%18$% -- это максимально возможное количество слонов. Из сказанного выше вытекает, что на противоположных угловых клетках (1,1) и (10,10), в координатной записи, слон стоит ровно один. (Напомним, что каждая из этих клеток у нас считается диагональю.) Далее, рассмотрим две диагонали, параллельные тому же направлению, то есть клетки (1,2), (2,1) и (9,10), (10,9). На каждой из них имеется ровно один слон (без этого не достичь числа $%18$%). Заметим, что центры этих четырёх клеток расположены в вершинах прямоугольника. Допустим, что слон стоит на (1,2). Тогда ни на (2,1), ни на (9,10) слона нет. Значит, он должен присутствовать на (10,1) -- клетке, центрально симметричной (1,2). А если слон был на (2,1) вместо (1,2), то второй слон в этом прямоугольнике будет на (10,9).

Далее рассматриваем прямоугольник, образованный клетками (1,3), (3,1), (10,8), (8,10). На диагонали, соединяющей первые две клетки, есть слон, и он стоит на одной из этих клеток, так как его нет на (2,2). Эта клетка находится под боем слона с (1,1) или (10,10). Аналогичный вывод верен для пары центрально симметричных клеток. Следовательно, здесь возможны ровно два случая: слоны расположены либо на (1,3), (10,8), либо на (3,1), (8,10).

Далее рассуждаем аналогично. Для клеток (1,4), (4,1), (10,7), (7,10) рассматриваем такой же прямоугольник. И здесь снова на диагонали, соединяющей первые две клетки, есть один слон, и стоять он должен с краю. На клетке (2,3) его бьёт уже выставленный слон с поля (1,2) или (9,10), и то же касается поля (3,2). Здесь слоны будут либо на (1,4), (10,7), либо на (4,1), (7,10).

Таким образом, все слоны выстраиваются на границе доски. В каждом из прямоугольников они могут стоять двумя способами, и выбор одного из двух таких способов ни на что не влияет. Среди рассматриваемых нами прямоугольников есть также два "вырожденных". Первый из них был рассмотрен в начале, и он состоит из одной диагонали, идущей из (1,1) в (10,10). Второй -- это диагональ из (1,10) в (10,1). Здесь тоже осуществляется выбор из двух вариантов -- на какой именно конец мы ставим слона.

Таким образом, ответ равен $%2^k$%, где $%k$% -- число рассматриваемых прямоугольников. (У нас для каждого такого прямоугольника, включая "вырожденные", есть выбор ровно из двух вариантов.) Легко понять, что каждый прямоугольник содержит ровно одну клетку нижней горизонтали, то есть $%k=10$%.

Ответ: $%2^{10}=1024$% способа.