Isaac has a large supply of counters, and places one in each of the $1 \times 1$ squares of an $8 \times 8$ chessboard. Each counter is either red, white, or blue. A particular pattern of colored counters is called an arrangement. Determine whether there are more arrangements which contain an even number of red counters, or more arrangements which contain an odd number of red counters. (Note that 0 is an even number.)
I solved this problem using a recurrence relation: laying out the chessboard squares in a straight line, counting the number of ways to do it for any number of squares, and coming up with closed-form formulae: $$e_n = \frac{3^n + 1}{2} \\ o_n = \frac{3^n - 1}{2}$$ where $n$ is the number of squares, $e_n$ counts even reds, $o_n$ counts odd reds.
However, the two quantities differ only by 1. This seems significant to me, because I cannot intuitively see why: I tried to come up with a 'bijection' sort of approach to the problem, which perhaps would say "for all arrangements with an even number of red counters, there is a unique one with an odd number of red counters, but hey, we have precisely one we can't account for". I tried doing this by various means, like flipping colors, counting sub-boards, etc. but didn't get anything. Can you find a bijection/mapping which makes intuitive sense?
Consider a fixed placement of white counters on the chessboard; the remaining squares must be occupied by red or blue counters.
Claim: For a given placement of white counters, there are just as many arrangements with an even number of red counters as with an odd number of red counters.
Proof: Pick a square that is not occupied by a white counter. Flipping the counter on that square between red and blue gives the desired bijection.
OOPS!! There is one exception! If ALL the squares are occupied by white counters, then there is only one possible arrangement, and it has an EVEN number of red counters!!