Maths Olympiad Prep

Library / /15 of 37

Combinatorics Difficulty 6.6 National olympiad Find the answer

Let n3n \geq 3 be an odd number and suppose that each square in a n×nn \times n chessboard is colored either black or white. Two squares are considered adjacent if they are of the same color and share a common vertex and two squares a,ba,b are considered connected if there exists a sequence of squares c1,,ckc_1,\ldots,c_k with c1=a,ck=bc_1 = a, c_k = b such that ci,ci+1c_i, c_{i+1} are adjacent for i=1,2,,k1i=1,2,\ldots,k-1.
\\
\\
Find the maximal number MM such that there exists a coloring admitting MM pairwise disconnected squares.

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

Solution

Let n3 n \geq 3 be an odd number and suppose that each square in an n×n n \times n chessboard is colored either black or white. Two squares are considered adjacent if they are of the same color and share a common vertex. Two squares a a and b b are considered connected if there exists a sequence of squares c1,,ck c_1, \ldots, c_k with c1=a c_1 = a and ck=b c_k = b such that ci c_i and ci+1 c_{i+1} are adjacent for i=1,2,,k1 i = 1, 2, \ldots, k-1 .

We aim to find the maximal number M M such that there exists a coloring admitting M M pairwise disconnected squares.

To solve this problem, we need to consider the structure of the chessboard and the properties of the coloring. The key insight is to analyze the number of disjoint maximal monochromatic components in the board.

For a general (2m+1)×(2n+1) (2m+1) \times (2n+1) board, we can prove that the maximal number of disjoint components is given by:
M=(m+1)(n+1)+1. M = (m+1)(n+1) + 1.

This result can be established through induction and careful analysis of the board's configuration. The proof involves considering different types of configurations and using combinatorial arguments to bound the number of components.

Hence, the maximal number M M of pairwise disconnected squares in an n×n n \times n chessboard, where n n is an odd number, is:
M=(n+12)2+1. M = \left(\frac{n+1}{2}\right)^2 + 1.

The answer is: \boxed{\left(\frac{n+1}{2}\right)^2 + 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.