Maths Olympiad Prep

Library / /452 of 462

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Ireland

An 8×88 \times 8 square is subdivided into 6464 unit squares like a chessboard. Some of these 6464 unit squares are black, all others are white. Such a configuration is called spotty if it contains at least two black unit squares each of which shares an edge with a white unit square to its left or above it.
How many spotty configurations are there?

Solution

We will use coordinates (i,j)(i, j), 0i,j80 \le i, j \le 8, to address the vertices of the 6464 small squares so that (0,0)(0,0) is the bottom left corner. There are 2642^{64} ways to make each of the 6464 squares either black or white. Each such 'colouring' will be called a configuration.

Let a spot be a black square which shares an edge with a white square to its left or above it. We will first count the number of configurations with no spots. Note that in this case, if a square is black, then the rectangle whose diagonal connects that square with the upper left corner is entirely black. Thus the configuration will contain a connected black area in the upper left corner bounded by a wall in the shape of an Up-and-Right path connecting the corner (0,0)(0,0) with the corner (8,8)(8,8).

Such paths can be represented by a string consisting of 88 U-s and 88 R-s.
There are (168)\binom{16}{8} such strings, and so (168)\binom{16}{8} spot-free configurations.

We next count the configurations containing exactly one spot.
The spot of such a configuration cannot have a black neighbour to the right and below, because this would imply that all squares above and to the left need to be black as well.

By symmetry, it suffices to count those configurations where the single spot does not have a black neighbour to the right.
If it also does not have a black neighbour below, after removing the spot, we obtain a spot-free configuration. If it has a black neighbour below, the spot will be the top square of a column of 2\ell \ge 2 black squares. As only the top one of them is a spot, this column must be adjacent to a vertical wall of the spot-free configuration obtained by removing these \ell squares.

Figure 1

This vertical wall segment gives k(8i)1k(8-i)-1 options for placing a single spot in the grey rectangle to its right. Only the top left corner of this rectangle wouldn't give a spot.
The other option would be to add a column of <k\ell < k black squares so that the topmost of them is a spot. As seen above, these \ell squares can only be situated directly next to the wall. There are (k12)\binom{k-1}{2} ways doing so, because the column is determined by selecting its top square and its bottom square, and there are k1k-1 possible positions for these black squares in order to get a spot at the top.

The wall segment considered can be completed to an Up-and-Right path in
(i1+ji1)(15ijk7i) \binom{i-1+j}{i-1} \binom{15-i-j-k}{7-i}
ways. The two binomial coefficients count the Up-and-Right paths in the cross-hatched rectangles above. When i=0i=0 we take the first factor to be 11. Adding up the contributions from all such wall segments, we get a total of
k=18i=07j=08(i1+ji1)(15ijk7i)(k(8i)1)+2k=38i=07j=08(i1+ji1)(15ijk7i)(k12) \sum_{k=1}^{8} \sum_{i=0}^{7} \sum_{j=0}^{8} \binom{i-1+j}{i-1} \binom{15-i-j-k}{7-i} (k(8-i)-1) + 2 \sum_{k=3}^{8} \sum_{i=0}^{7} \sum_{j=0}^{8} \binom{i-1+j}{i-1} \binom{15-i-j-k}{7-i} \binom{k-1}{2}
11-spotted configurations. Note that the factor 22 in the second line accounts for the symmetry mentioned above.

For fixed kk, the factors in the first and second line can be organized carefully in a table with one row for each value of ii and one column for each value of jj, which allows one to do the sums in an orderly way, leading to a total of
16(1510)+(92)(169)8(158) 16 \binom{15}{10} + \binom{9}{2} \binom{16}{9} - 8 \binom{15}{8}
11-spotted configurations. The number of spotty configurations is therefore
264((168)+16(1510)+(92)(169)8(158))=264421278. 2^{64} - \left( \binom{16}{8} + 16 \binom{15}{10} + \binom{9}{2} \binom{16}{9} - 8 \binom{15}{8} \right) = 2^{64} - 421278.

In the above count of 11-spotted configurations, one can use the following "generalized hockey stick" formula to simplify the sums:
j=0B(A+jA)(B+CjC)=(A+B+C+1A+C+1). \sum_{j=0}^{B} \binom{A+j}{A} \binom{B+C-j}{C} = \binom{A+B+C+1}{A+C+1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.