Разделы 
Дополнительно
Задача по математике - 506
2014-06-08 
Клетки шахматной доски размером $n \times n$, где $n$ - четное число, большее 2, раскрашены $n^{2}/2$ красками так, что каждой краской окрашены ровно две клетки. Доказать, что на доске можно расставить $n$ ладей так, чтобы они стояли на клетках разного цвета и не били друг друга.
Решение:
Заметим, что на доске размером $m \times m$ можно расставить $m$ не бьющих друг друга ладей ровно $m!$ способами, поскольку на первой горизонтали ладью можно расположить $m$ способами, затем на второй - $(m - 1)$ способами и т.д., наконец, на последней – единственным способом. Пусть утверждение задачи неверно. Тогда, если доска раскрашена, как указано в условии задачи, то для любой расстановки не бьющих друг друга ладей какие-то две из них стоят на клетках одного цвета. Следовательно, число $n!$ всех таких расстановок не превосходит $(n^{2}/2)(n - 2)!$, поскольку пару ладей можно расставить на клетках одного цвета не более чем $n^{2}/2$ способами, а затем остальные $n – 2$ ладьи - $(n - 2)1$ способами. Итак, имеем оценку $n! \leq (n^{2}/2) (n - 2)!$, откуда $n – 1 \leq n/2$, т. е. $n \leq 2$, что противоречит условию.
Клетки шахматной доски размером $n \times n$, где $n$ - четное число, большее 2, раскрашены $n^{2}/2$ красками так, что каждой краской окрашены ровно две клетки. Доказать, что на доске можно расставить $n$ ладей так, чтобы они стояли на клетках разного цвета и не били друг друга.
Решение:
Заметим, что на доске размером $m \times m$ можно расставить $m$ не бьющих друг друга ладей ровно $m!$ способами, поскольку на первой горизонтали ладью можно расположить $m$ способами, затем на второй - $(m - 1)$ способами и т.д., наконец, на последней – единственным способом. Пусть утверждение задачи неверно. Тогда, если доска раскрашена, как указано в условии задачи, то для любой расстановки не бьющих друг друга ладей какие-то две из них стоят на клетках одного цвета. Следовательно, число $n!$ всех таких расстановок не превосходит $(n^{2}/2)(n - 2)!$, поскольку пару ладей можно расставить на клетках одного цвета не более чем $n^{2}/2$ способами, а затем остальные $n – 2$ ладьи - $(n - 2)1$ способами. Итак, имеем оценку $n! \leq (n^{2}/2) (n - 2)!$, откуда $n – 1 \leq n/2$, т. е. $n \leq 2$, что противоречит условию.
