Сколькими способами можно на клетчатой доске размером 10х10 расставить 18 шахматных слонов, не бьющих друг друга?

задан 17 Фев '13 21:38

изменен 17 Фев '13 23:09

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
1

Рассмотрим все диагонали доски, включая те, которые состоят из одной клетки. Они все параллельны одному из двух направлений, и для каждого из таких направлений диагоналей имеется ровно $%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$% способа.

ссылка

отвечен 17 Фев '13 23:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×717

задан
17 Фев '13 21:38

показан
1480 раз

обновлен
17 Фев '13 23:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru