Given natural number n. Suppose that $N$ is the maximum number of elephants that can be placed on a chessboard measuring $2 \times n$ so that no two elephants are mutually under attack. Determine the number of ways to put $N$ elephants on a chessboard sized $2 \times n$ so that no two elephants attack each other. Alternative Formulation: Determine the number of ways to put $2015$ elephants on a chessboard measuring $2 \times 2015$ so there are no two elephants attacking each othe PS. Elephant = Bishop
Problem
Source: INAMO Shortlist 2015 C1
Tags: combinatorics, Chessboard, chess
15.05.2019 01:01
Step 1: Notice that the maximum number of bishops, as $n$ is odd, is ${2014}+2=2016$ (not hard to prove, just use the fact that a $2$ by $2$ square can have at most $2$ bishops. Now to prove such a configuration exists, place the bishops at the each row and then skip a row, starting on the leftmost row, like this: : : : : : ... (imagine the spaces are blanks and dots are bishops). ). Step 2: Now for such a configuration to exist, we must cram $2$ bishops into each $2$ by $2$ square. Our claim is that there are only $2$ ways to do this, one way already being shown and the other one being the opposite of it. Now, the only way to arrange the bishops aside from vertical lines is horizontal lines (like **). It's pretty simple to prove that the horizontal arrangement will not work by considering its directly adjacent square (there would exist a $2$ by $2$ square with only $1$ bishop, hence contradiction). And finally last case is if the arrangement is like this anywhere ($:$ $:$)... again we use the same logic to prove this can't exist. Thus there must only be $2$ arrangements where $2016$ non-attacking bishops can be placed. Q.E.D.
15.05.2019 01:24
Um... An alfil can't attack any other, no matter where you place it on the board. The board needs to be at least three wide for them to be able to attack each other.