2015
Problem - 2616
Alice places down $n$ bishops on a $2015\times 2015$ chessboard such that no two bishops are attacking each other. (Bishops attack each other if they are on a diagonal.)
- Find, with proof, the maximum possible value of $n$.
- For this maximal $n$, find, with proof, the number of ways she could place her bishops on the chessboard.
We claim that the maximum number of bishops that can be placed in this fashion on an $n$-by-$n$ chessboard is $2(n- 1)$. First, notice that in any unoccupied squares, no more than two bishops can attack that square, or else by pigeonhole, two bishops can attack one another.
Furthermore, a corner square can be attacked by at most one bishop, and since we wish to maximize the number of bishops, there will be at most two unoccupied corner squares. Thus, if there are $k$ bishops, the number of possible attacks is at most $2(n^2-k)-2$.
Now, each bishop can attack at least $n-1$ squares, with equality holding iif\u000b the bishop lies on the outer boundary of the chessboard. Thus, if there are $k$ bishops, then we have the inequality:
$$k(n-1)\le 2(n^2-k)-2$$
$$k\le \frac{2n^2-2}{n + 1}$$
$$= 2(n - 1)$$
As desired. Now, note that equality holds iif\u000b each bishop can attack exactly $(n-1)$ squares, which means all the bishops must be on the outer boundary of the chessboard. We can divide these square into groups: for any $I$, the squares $(1,i)$, $(i,1)$, $(2015, 2015-i+1),(2015-i+1; 2015)$ form a group.
Clearly, at most half of the squares in each group can be occupied, so to achieve equality, half the squares in each group must be occupied. It is easy to see that there is exactly two ways to select the occupied squares within each group. Furthermore, the bishops in a group cannot attack those in another group. Thus, the selections are independent.
Since there are 2015 groups, one for each $1\le\ i\le 2015$, there are a total of $2015$ ways to place the bishops, so our answer is $2 + 2015 = 2017$ .