Maths Olympiad Prep

Library / /356 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

The nonnegative integer nn and a (2n+1)×(2n+1)(2 n+1) \times(2 n+1) chessboard with squares alternately colored black and white are given. For every natural number mm with 1<m<2n+11<m<2 n+1, an m×mm \times m square of the given chessboard that has more than half of its area colored in black is called a BB-square. If the given chessboard is a BB-square, find in terms of nn the total number of BB-squares of this chessboard.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Every square with an even side length will have an equal number of black and white 1×11 \times 1 squares, so it isn't a BB-square. In a square with an odd side length, there is one more 1×11 \times 1 black square than white squares, if it has black corner squares. So, a square with an odd side length is a BB-square either if it is a 1×11 \times 1 black square or it has black corners.

Let the given (2n+1)×(2n+1)(2 n+1) \times(2 n+1) chessboard be a BB-square and denote by bi(i=1,2,,n+1)b_{i}(i=1,2, \ldots, n+1) the lines of the chessboard, which have n+1n+1 black 1×11 \times 1 squares, by wi(i=1,2,,n)w_{i}(i=1,2, \ldots, n) the lines of the chessboard, which have nn black 1×11 \times 1 squares and by Tm(m=1,3,5,,2n1,2n+1)T_{m}(m=1,3,5, \ldots, 2 n-1,2 n+1) the total number of BB-squares of dimension m×mm \times m of the given chessboard.

For T1T_{1} we obtain T1=(n+1)(n+1)+nn=(n+1)2+n2T_{1}=(n+1)(n+1)+n \cdot n=(n+1)^{2}+n^{2}.

For computing T3T_{3} we observe that there are n3×3Bn 3 \times 3 B-squares, which have the black corners on each pair of lines (bi,bi+1)\left(b_{i}, b_{i+1}\right) for i=1,2,,ni=1,2, \ldots, n and there are n13×3Bn-13 \times 3 B-squares, which have the black corners on each pair of lines (wi,wi+1)\left(w_{i}, w_{i+1}\right) for i=1,2,,n1i=1,2, \ldots, n-1. So, we have

T3=nn+(n1)(n1)=n2+(n1)2 T_{3}=n \cdot n+(n-1)(n-1)=n^{2}+(n-1)^{2} \text {. }

By using similar arguments for each pair of lines (bi,bi+2)\left(b_{i}, b_{i+2}\right) for i=1,2,,n1i=1,2, \ldots, n-1 and for each pair of lines (wi,wi+2)\left(w_{i}, w_{i+2}\right) for i=1,2,,n2i=1,2, \ldots, n-2 we compute

T5=(n1)(n1)+(n2)(n2)=(n1)2+(n2)2 T_{5}=(n-1)(n-1)+(n-2)(n-2)=(n-1)^{2}+(n-2)^{2}

Step by step, we obtain

T7=(n2)(n2)+(n3)(n3)=(n2)2+(n3)2T2n1=22+11=22+12T2n+1=11=12 \begin{gathered} T_{7}=(n-2)(n-2)+(n-3)(n-3)=(n-2)^{2}+(n-3)^{2} \\ \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\ T_{2 n-1}=2 \cdot 2+1 \cdot 1=2^{2}+1^{2} \\ T_{2 n+1}=1 \cdot 1=1^{2} \end{gathered}

The total number of BB-squares of the given chessboard equals to

T1+T3+T5++T2n+1=2(12+22++n2)+(n+1)2=n(n+1)(2n+1)3+(n+1)2=(n+1)(2n2+4n+3)3 \begin{gathered} T_{1}+T_{3}+T_{5}+\ldots+T_{2 n+1}=2\left(1^{2}+2^{2}+\ldots+n^{2}\right)+(n+1)^{2}= \\ \frac{n(n+1)(2 n+1)}{3}+(n+1)^{2}=\frac{(n+1)\left(2 n^{2}+4 n+3\right)}{3} \end{gathered}

The problem is solved.

### 2.3 Geometry

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.