Maths Olympiad Prep

Library / /77 of 116

Combinatorics Difficulty 8.6 Shortlist Find the answer

Let n2n \ge 2 be an integer. Consider an n×nn \times n chessboard consisting of n2n^2 unit squares. A configuration of nn rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer kk such that, for each peaceful configuration of nn rooks, there is a k×kk \times k square which does not contain a rook on any of its k2k^2 unit squares.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n2 n \geq 2 be an integer, and consider an n×n n \times n chessboard. We place n n rooks on this board such that each row and each column contains exactly one rook. This is defined as a peaceful configuration of rooks. The objective is to find the greatest positive integer k k such that, in every possible peaceful configuration of n n rooks, there exists a k×k k \times k sub-square on the chessboard that is completely empty of any rooks.

### Step-by-step Solution

1. Understanding the Problem:
- In a peaceful configuration, since there is exactly one rook per row and one per column, it ensures all n n rooks are placed in unique row-column intersections across the n×n n \times n board.

2. Identifying Empty Squares:
- We need to ensure every configuration allows for a square sub-board of size k×k k \times k which is void of rooks.

3. **Calculation of Maximum k k :**
- If we realize a peaceful configuration where rooks are distributed such that they occupy maximum area of the available board, each row and column combination will optimally cover the board minimally.
- The goal is maximizing k k , ensuring the largest empty k×k k \times k square still forms on any part of the board in spite of any rook configuration.

4. Using Combinatorial and Geometric Argument:
- Let’s consider placing n1 n-1 rooks. In this optimal configuration, potentially every position leading to n1 n-1 coverages leaves a square potentially of size up to
n1×n1\sqrt{n - 1} \times \sqrt{n - 1} that is free.
- For all n n positions to be filled, this sub-square will obviously be smaller in the maximal empty form.

5. Conclusion:
- Upon deriving these options and observance that the largest k×k k \times k square exists, due to nk\lceil\frac{n}{k}\rceil fraction of remaining free subset, we form:
- The greatest k k ensuring a k×k k \times k rupe-free square is presented by the integer part:
k=n1. k = \left\lfloor \sqrt{n - 1} \right\rfloor.

Thus, the greatest positive integer k k such that for any peaceful configuration, there exists a k×k k \times k sub-square devoid of rooks, is:
n1. \boxed{\left\lfloor \sqrt{n - 1} \right\rfloor}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.