Maths Olympiad Prep

Library / /93 of 106

Combinatorics Difficulty 8.8 Shortlist Find the answer

A site is any point (x,y)(x, y) in the plane such that xx and yy are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to 5\sqrt{5}. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest KK such that Amy can ensure that she places at least KK red stones, no matter how Ben places his blue stones.

*

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

Solution

Let us consider the problem where Amy and Ben take turns placing stones on a 20x20 grid consisting of sites (x,y)(x, y) where xx and yy are integers between 1 and 20 inclusive. Amy's condition for placing a red stone is that the distance between any two red stones is not equal to 5\sqrt{5}. This occurs specifically when the coordinates of two stones differ by 2 in one coordinate and 1 in the other, which are equivalent to the vector differences (±2,±1)(\pm 2, \pm 1) or (±1,±2)(\pm 1, \pm 2).

The goal is to find the maximum number KK such that Amy can ensure placing at least KK red stones regardless of Ben's move choices. Our task requires an arrangement that avoids any pair of red stones being placed at a distance of 5\sqrt{5}.

### Strategy

An efficient strategy is to place stones such that any two stones are more than 5\sqrt{5} units apart. We focus on constructing a checkerboard pattern, exploiting the grid nature.

1. To prevent placing red stones at a distance of 5\sqrt{5}, consider only placing red stones on sites where both coordinates, xx and yy, are either both odd or both even.

2. This choice ensures that the difference (±2,±1)(\pm 2, \pm 1) or (±1,±2)(\pm 1, \pm 2) cannot align two red stones with the distance of 5\sqrt{5}, since these would require parity mismatches in both coordinates.

3. Constructing the grid in this way, one subset of the grid (say, all sites with both coordinates odd) will contain no nearby red stones to violate the distance rule.

### Calculation

- Each 20x20 grid contains 400 total sites.
- The number of odd-odd sites is equal to the number of even-even sites since both are 202×202=10×10=100\frac{20}{2} \times \frac{20}{2} = 10 \times 10 = 100.

Amy can guarantee placing at least 100 red stones because whenever she uses only odd-odd or even-even sites, each site choice naturally keeps all pairs in the valid configuration.

Thus, the greatest KK such that Amy can guarantee at least KK stones is:

100 \boxed{100}

This solution represents a strategic positioning allowing Amy to always utilize the entire set of sites based on parity distinctions, ensuring Ben’s choices will not interfere with her minimum KK target.

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.