Maths Olympiad Prep

Library / /78 of 144

Combinatorics Difficulty 8.3 Shortlist Find the answer

Let n n and k k be positive integers such that 12n<k23n. \frac{1}{2} n < k \leq \frac{2}{3} n. Find the least number m m for which it is possible to place m m pawns on m m squares of an n×n n \times n chessboard so that no column or row contains a block of k k adjacent unoccupied squares.

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

Solution

Let n n and k k be positive integers such that 12n<k23n \frac{1}{2}n < k \leq \frac{2}{3}n . Our goal is to find the least number m m for which it is possible to place m m pawns on an n×n n \times n chessboard such that no column or row contains a block of k k adjacent unoccupied squares.

### Analysis:
1. Chessboard Structure:
The chessboard is n×n n \times n , meaning it contains n2 n^2 squares.

2. Occupied Squares and Condition:
The condition states that in any row or column, there should not be k k consecutive unoccupied squares. Hence, each row or column must be interrupted by pawns frequently to avoid these consecutive spaces.

### Strategy to Satisfy the Conditions:
The strategy is to divide each row and each column evenly with pawns such that no k k adjacent unoccupied squares appear.

### Steps to Place Pawns:
1. Rows Consideration:
- For each row of length n n , identify the longest possible block of consecutive squares we can have without placing a pawn, which is <k < k .

2. Calculation for Rows:
- If there are n n squares in a row, we need to ensure that every possible group of k k or more squares has at least one pawn.
- If d=nk d = n - k , the placement of pawns should break the row such that each break occurs before a block gets as long as k k . This requires a pawn after every k1 k - 1 squares.
- Number of necessary divisions (pawns) in a row = nk\left\lceil \frac{n}{k} \right\rceil.
- Maximum possible value of these divisions due to edge adjustments will lead to 2(nk) 2(n-k) , accounting for rows and the similar applies to columns.

3. Effective Placement:
- Optimize so that if each row is broken into nk \left\lceil \frac{n}{k} \right\rceil blocks, ensuring all adjustments for bordering overlaps lead to the conclusion of needing 4(nk) 4(n-k) pawns in total, considering both rows and columns.

Therefore, the least number m m of pawns needed to ensure the chessboard satisfies the conditions is:

4(nk) \boxed{4(n-k)}

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.